詳解C/C++高精度算法的簡單實現(xiàn)
前言
由于上一章《C/C++ 高精度（加減乘除）算法實現(xiàn)》是基于工程項目考慮實現(xiàn)的，也做了一定的優(yōu)化，實現(xiàn)過程較為復(fù)雜。不利于移植和使用，且比較難以理解，時間一長代碼也容易忘記，所以重新編寫了一個簡化的版本，方便以后需要時拷貝使用。
一、基本原理
1、存儲方式
采用數(shù)字記錄高精度數(shù)字，數(shù)組的第一個元素存儲數(shù)據(jù)長度，比如記錄數(shù)字為1024示例如下：
2、計算方式
采用模擬立豎式計算，比如加法的計算流程，如下圖所示1024+9000：
這里只給出加法的計算說明，其他的以此類推，減法與加法基本一致。乘法和除法略有不同，通過示例圖表示也復(fù)雜，還不如通過代碼去理解，本質(zhì)的方法就是模擬筆算的立豎式計算。
二、輔助方法
1、字符串轉(zhuǎn)高精度
長度記錄在數(shù)組第一個元素中
/// <summary>
/// 通過字符串初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]字符串首地址</param>
static void loadStr(int* a,const char* value)
{
//記錄長度
a[0] = strlen(value);
for (int i = 1; i <= a[0]; i++)
a[i] = value[a[0] - i] - '0';
}
2、整型轉(zhuǎn)高精度
/// <summary>
/// 通過無符號整型初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]整型值</param>
static void loadInt(int* a, uint64_t value)
{
for (size_t i = 1; i < 8096; i++)
{
a[i] = value % 10;
value /= 10;
if (!value)
{
//記錄長度
a[0] = i;
return;
}
}
}3、比較
/// <summary>
/// 比較兩個高精度數(shù)的大小
/// </summary>
/// <param name="a">[in]第一個數(shù)</param>
/// <param name="b">[in]第二個數(shù)</param>
/// <returns>1是a>b,0是a==b,-1是a<b</returns>
static int compare(int* a, int* b)
{
if (a[0] > b[0])return 1;
if (a[0] < b[0])return -1;
for (int i = a[0]; i > 0; i--)
if (a[i] > b[i])return 1;
else if (a[i] < b[i])return -1;
return 0;
}
4、打印
/// <summary>
/// 打印輸出結(jié)果
/// </summary>
static void print(int* a) {
if (!a[0])
printf("0");
for (int i = a[0]; i > 0; i--)
printf("%d", a[i]);
}
三、算法實現(xiàn)
原理就不做具體介紹了，四種計算的核心都是模擬立豎式計算。
1、加法
為了保證代碼相對簡單，當(dāng)b長度較小時可能會做一些多余的計算，不影響結(jié)果。
/// <summary>
/// 加法(累加)
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="b">[in]加數(shù)</param>
static void acc(int* a, int* b)
{
int len = a[0] > b[0] ? a[0] : b[0];
memset(a + a[0] + 1, 0, (len - a[0] + 1) * sizeof(int));
memset(b + b[0] + 1, 0, (len - b[0] + 1) * sizeof(int));
for (int i = 1; i <= len; i++) {
int temp = a[i] + b[i];
a[i] = temp % 10;
a[i + 1] += temp / 10;
}
if (a[len + 1])a[0]++;
}2、減法
/// <summary>
/// 減法(累減)
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被減數(shù)，被減數(shù)必須大于等于減數(shù)</param>
/// <param name="b">[in]減數(shù)</param>
static void subc(int* a, int* b) {
memset(b + b[0] + 1, 0, (a[0] - b[0]) * sizeof(int));
for (int i = 1; i <= a[0]; i++)
{
int temp = a[i] - b[i];
a[i] = temp;
if (temp < 0)
{
//借位
a[i + 1] -= 1;
a[i] += 10;
}
}
//記錄長度
for (int i = a[0]; i > 0; i--)
if (a[i])
{
a[0] = i;
return;
}
a[0] = 0;
}3、乘法
/// <summary>
/// 乘法
/// </summary>
/// <param name="a">[in]被乘數(shù)</param>
/// <param name="b">[in]乘數(shù)</param>
/// <param name="c">[out]結(jié)果，數(shù)組長度必須大于等于aLen+bLen+1</param>
static void mul(int* a, int* b, int c[]) {
c[a[0] + b[0]] = 0;
memset(c, 0, sizeof(int) * (a[0] + b[0] + 1));
for (int i = 1; i <= a[0]; i++)
{
int j;
int d = 0;
//被乘數(shù)的一位去乘以乘數(shù)的每一位
for (j = 1; j <= b[0]; j++)
{
int temp = a[i] * b[j] + c[j + i - 1] + d;
c[j + i - 1] = temp % 10;
d = temp / 10;
}
if (d)
{
c[j + i - 1] = d;
}
}
//記錄長度
for (int i = a[0] + b[0]; i > 0; i--)
if (c[i])
{
c[0] = i;
return;
}
}4、除法
采用了升階+減法實現(xiàn)
/// <summary>
/// 除法
/// 依賴減法subc
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="c">[out]商，數(shù)組長度大于等于aLen-bLen+1</param>
/// <param name="mod">[out]余數(shù)，數(shù)組長度大于等于aLen</param>>
/// <param name="temp">[in]臨時緩沖區(qū)，由外部提供以提高性能，數(shù)組長度大于等于aLen-bLen+1</param>
static void divi(int* a, int* b, int* c, int* mod, int* temp) {
//相差的階數(shù)
int digit = a[0] - b[0] + 1;
memcpy(mod, a, (a[0] + 1) * sizeof(int));
memset(c, 0, sizeof(int) * (digit + 1));
memset(temp, 0, sizeof(int) * digit);
while (digit)
{
//升階
memcpy(temp + digit, b + 1, sizeof(int) * b[0]);
temp[0] = b[0] + digit - 1;
//減法
while (compare(mod, temp) != -1)
{
subc(mod, temp);
c[digit]++;
}
digit--;
}
//記錄長度
for (int i = a[0] - b[0] + 1; i > 0; i--)
if (c[i])
{
c[0] = i;
return;
}
}四、使用示例
1、加法
計算累加
int main() {
int64_t n;
int num[1024];
int num2[1024];
std::cin >> n;
loadInt(num, 0);
for (int64_t i = 1; i <= n; i++)
{
loadInt(num2, i);
acc(num, num2);
}
print(num);
return 0;
}
結(jié)果：
2、減法
兩個任意n位數(shù)的減法，數(shù)字1大于數(shù)字2。
int main()
{
int a1[8096], a2[8096];
std::string s1, s2;
std::cin >> s1 >> s2;
loadStr(a1, s1.c_str());
loadStr(a2, s2.c_str());
subc(a1, a2);
print(a1);
return 0;
}結(jié)果：
#數(shù)字1
752425289999999999999652142141414141414146666676667677682324000001302461646520
#數(shù)字2
587891851201874512000000000154515100202121555555555555555555555545477910232111
#計算結(jié)果
164533438798125487999652141986899041212025111121112122126768444455824551414409
3、乘法
計算階乘
int main() {
int64_t n;
int num[8192];
int num2[8192];
int num3[8192];
int* p1 = num;
int* p2 = num3;
std::cin >> n;
loadInt(num, 1);
for (int64_t i = 1; i <= n; i++)
{
loadInt(num2, i);
mul(p1, num2, p2);
int* temp = p1;
p1 = p2;
p2 = temp;
}
print(p1);
return 0;
}結(jié)果：
#階乘數(shù)
1000
#計算結(jié)果
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
4、除法
給定兩個非負整數(shù)A，B，請你計算 A / B的商和余數(shù)。
int main()
{
int a1[8096], a2[8096], c[8096], mod[8096], temp[8096];
std::string s1, s2;
std::cin >> s1 >> s2;
loadStr(a1, s1.c_str());
loadStr(a2, s2.c_str());
divi(a1, a2, c, mod, temp);
print(c);
std::cout << std::endl;
print(mod);
return 0;
}
結(jié)果：
#被除數(shù)
12458848948151231366666666666666665454545123156415641561231561213648
#除數(shù)
88484851521548496564154848456486789
#商
140802055198308817458997123299946
#余數(shù)
25178368711335236611547594127800254
總結(jié)
以上就是今天要講的內(nèi)容，本文提供的是較為簡化的實現(xiàn)，且每個方法基本是獨立的，可單獨拿來使用，用法也比較簡單，由于采用數(shù)組第一個元素存儲長度，接口就變得很簡潔，使用起來也方便了很多。
到此這篇關(guān)于詳解C/C++高精度算法的簡單實現(xiàn)的文章就介紹到這了,更多相關(guān)C/C++高精度算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++函數(shù)指針的學(xué)習(xí)教程,講到了函數(shù)指針的定義及把指針作為函數(shù)參數(shù)進行傳遞的用法,需要的朋友可以參考下2016-04-04
基于epoll的多線程網(wǎng)絡(luò)服務(wù)程序設(shè)計
這篇文章主要為大家詳細介紹了基于epoll的多線程網(wǎng)絡(luò)服務(wù)程序設(shè)計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
C++語言的模板技術(shù)包括函數(shù)模板和類模板，模板技術(shù)是一種代碼重用技術(shù)，函數(shù)和類是C++語言中兩種主要的重用代碼形式，這篇文章主要介紹了C++函數(shù)模板和類模板,需要的朋友可以參考下2022-07-07
這篇文章主要為大家詳細介紹了C++實現(xiàn)簡單班級成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
動態(tài)內(nèi)存是相對靜態(tài)內(nèi)存而言的。所謂動態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動態(tài)內(nèi)存是指在堆上分配的內(nèi)存，而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存，本文帶你深入探究C語言中動態(tài)內(nèi)存的管理2022-02-02
在小游戲的制作中時常常會要用到隨機數(shù)，這篇文章就來和大家談?wù)凜++中這個所謂的“隨機”。文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-11-11
C++實現(xiàn)LeetCode(92.倒置鏈表之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(倒置鏈表之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要給大家介紹了關(guān)于C++之a(chǎn)ssert推薦用法及注意事項的相關(guān)資料,assert 是一個預(yù)處理宏,用于在運行時檢查表達式是否為真,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了++ 設(shè)計模式的基本原則，主要的目標是實現(xiàn)最終目的，高內(nèi)聚，低耦合，開放封閉原則類的改動是通過增加代碼進行的，感興趣的小伙伴可參考下面文章的具體內(nèi)容2021-09-09
簡要解讀C++的動態(tài)和靜態(tài)關(guān)聯(lián)以及虛析構(gòu)函數(shù)
這篇文章主要介紹了簡要解讀C++的動態(tài)和靜態(tài)關(guān)聯(lián)以及虛析構(gòu)函數(shù),析構(gòu)函數(shù)在C++編程中平時并不是太常用,需要的朋友可以參考下2015-09-09