C/C++高精度(加減乘除)算法的實現(xiàn)
更新時間：2022年12月15日 10:46:53 作者：CodeOfCC
高精度的算法，一般的方式是用一個很長的數(shù)組去記錄數(shù)據(jù)，數(shù)組的每一位記錄固定位數(shù)的數(shù)字，記錄順序是低位到高位。本文將通過實例為大家介紹下高精度算法的實現(xiàn)，感興趣的可以了解一下
前言
C/C++基本類型做算術(shù)運算時長度有限，但也基本滿足大部分場景的使用，有時需要計算大長度數(shù)據(jù)就有點無能為力了，比如1000的階乘結(jié)果就有2000多位，用基本類型是無法計算的。
高精度的算法，一般的方式是用一個很長的數(shù)組去記錄數(shù)據(jù)，數(shù)組的每一位記錄固定位數(shù)的數(shù)字，記錄順序是低位到高位。計算方式則通常采用模擬立豎式計算。計算方式有一些優(yōu)化方法，比如FFT快速傅里葉變換優(yōu)化乘法，牛頓迭代優(yōu)化除法。
本方法采用的，是上述的一般方式，用數(shù)組從低到高位記錄數(shù)據(jù)，計算方式采用模擬立豎式計算。
一、必要的參數(shù)
1、計算位數(shù)
需要設(shè)定數(shù)組每個元素記錄的位數(shù)即計算的進制（十進制、百進制、千進制）。計算位數(shù)越大，計算性能越好，在32/64位程序中，位數(shù)的范圍可以是[1,9]。
2、計算進制
與計算位數(shù)直接對應(yīng)，比如1位等于10進制，2位等于百進制。
3、數(shù)組類型
根據(jù)計算位數(shù)定義能裝載數(shù)據(jù)的整型，盡量不浪費空間又不溢出，比如2位以內(nèi)可以用int8，4位可以用int16等。
代碼實現(xiàn)如下：
#include<stdint.h>
#include<stdio.h>
//計算位數(shù)，范圍[1,9]
#define NUM_DIGIT 9
//數(shù)組類型
#if NUM_DIGIT<=0
static_assert(1, "NUM_DIGIT must > 0 and <=9");
#elif NUM_DIGIT <=2
#define _NUM_T int8_t
#elif NUM_DIGIT <=4
#define _NUM_T int16_t
#elif NUM_DIGIT <=9
//NUM_DIGIT在[5,9]時用int32就可以裝載數(shù)據(jù)，但是實測發(fā)現(xiàn)用int32在32位程序中，對除法性能有影響，用int64反而正常，這是比較奇怪的現(xiàn)象。
#define _NUM_T int64_t
#else
static_assert(1, "NUM_DIGIT must > 0 and <=9");
#endif
//計算進制
static const size_t _hex = NUM_DIGIT == 1 ? 10 : NUM_DIGIT == 2 ? 100 : NUM_DIGIT == 3 ? 1000 : NUM_DIGIT == 4 ? 10000 : NUM_DIGIT == 5 ? 100000 : NUM_DIGIT == 6 ? 1000000 : NUM_DIGIT == 7 ? 10000000 : NUM_DIGIT == 8 ? 100000000 : NUM_DIGIT == 9 ? 1000000000 : -1;
#define _MIN_NUM_SIZE 30/NUM_DIGIT
上述代碼只要設(shè)置NUM_DIGIT(計算位數(shù))就可以，其他值（計算進制、數(shù)組類型）都會自動生成。
二、輔助函數(shù)
1、初始化函數(shù)
由整型、字符串初始化高精度數(shù)組的方法。
2、比較函數(shù)
比較兩個高精度數(shù)的大小等于。
3、輸出函數(shù)
將高精度數(shù)組打印輸出。
代碼實現(xiàn)如下：
/// <summary>
/// 通過字符串初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]字符串首地址</param>
/// <param name="len">[in]字符串長度</param>
/// <returns>數(shù)據(jù)長度</returns>
static size_t initByStr(_NUM_T* a, const char* value, size_t len)
{
size_t shift = 10;
size_t i, j, k = 0, n;
n = len / NUM_DIGIT;
for (i = 0; i < n; i++)
{
a[i] = (value[len - k - 1] - '0');
for (j = 1; j < NUM_DIGIT; j++)
{
a[i] += (value[len - k - j - 1] - '0') * shift;
shift *= 10;
}
shift = 10;
k += NUM_DIGIT;
}
if (n = len - n * NUM_DIGIT)
{
a[i] = (value[len - k - 1] - '0');
for (j = 1; j < n; j++)
{
a[i] += (value[len - k - j - 1] - '0') * shift;
shift *= 10;
}
i++;
}
return i;
}
/// <summary>
/// 通過無符號32整型初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]整型值</param>
/// <returns>數(shù)據(jù)長度</returns>
static size_t initByInt32(_NUM_T* a, uint32_t value)
{
size_t i;
for (i = 0; i < 8096; i++)
{
a[i] = value % _hex;
value /= _hex;
if (!value)
{
i++;
break;
}
}
return i;
}
/// <summary>
/// 通過無符號64整型初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]整型值</param>
/// <returns>數(shù)據(jù)長度</returns>
static size_t initByInt64(_NUM_T* a, uint64_t value)
{
size_t i;
for (i = 0; i < 8096; i++)
{
a[i] = value % _hex;
value /= _hex;
if (!value)
{
i++;
break;
}
}
return i;
}
/// <summary>
/// 比較兩個高精度數(shù)的大小
/// </summary>
/// <param name="a">[in]第一個數(shù)</param>
/// <param name="aLen">[in]第一個數(shù)的長度</param>
/// <param name="b">[in]第二個數(shù)</param>
/// <param name="bLen">[in]第二個數(shù)的長度</param>
/// <returns>1是a>b,0是a==b,-1是a<b</returns>
static int compare(const _NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen)
{
if (aLen > bLen)
{
return 1;
}
else if (aLen < bLen)
{
return -1;
}
else {
for (int i = aLen - 1; i > -1; i--)
{
if (a[i] > b[i])
{
return 1;
}
else if (a[i] < b[i])
{
return -1;
}
}
}
return 0;
}
/// <summary>
/// 打印輸出結(jié)果
/// </summary>
static void print(const _NUM_T* a, size_t aLen) {
int i = aLen - 1, j = 0, n = _hex;
char format[32];
sprintf(format, "%%0%dd", NUM_DIGIT);
printf("%d", a[i--]);
for (; i > -1; i--)
printf(format, a[i]);
}三、實現(xiàn)加減乘除
1、加法
由于數(shù)組存儲數(shù)據(jù)的順序是由低位到高位的，所以只需要兩個數(shù)從數(shù)組0位開始相加，結(jié)果除以計算位數(shù)，余數(shù)保存在第一個數(shù)數(shù)組當(dāng)前位，商累加到第一個數(shù)數(shù)組的下一位，然后下標(biāo)加1重復(fù)前面的計算，直到全部元素計算完。
代碼實現(xiàn)如下：
/// <summary>
/// 加法(累加)
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="aLen">[in]被加數(shù)長度</param>
/// <param name="b">[in]加數(shù)</param>
/// <param name="bLen">[in]加數(shù)長度</param>
/// <returns>結(jié)果長度</returns>
static size_t acc(_NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen)
{
size_t i, n = bLen;
const size_t max = _hex - 1;
if (aLen < bLen)
{
memset(a + aLen, 0, (bLen - aLen + 1) * sizeof(_NUM_T));
}
else {
a[aLen] = 0;
}
for (i = 0; i < bLen; i++) {
uint64_t temp = (uint64_t)a[i] + (uint64_t)b[i];
a[i] = temp % _hex;
a[i + 1] += temp / _hex;
}
for (; i < aLen; i++) {
uint64_t temp = a[i];
if (temp <= max)
break;
a[i] = temp % _hex;
a[i + 1] += temp / _hex;
}
n = aLen > bLen ? aLen : bLen;
if (a[n])
return n + 1;
return n;
}2、減法
減法的原理和加法是類似的，兩個數(shù)從數(shù)組0位開始相減，結(jié)果大于等于0直接保存到第一個數(shù)數(shù)組當(dāng)前位，否則結(jié)果小于零結(jié)果+計算進制保存到第一個數(shù)數(shù)組當(dāng)前位，同時下一位減等于1，然后下標(biāo)加1重復(fù)前面的計算，直到全部元素計算完。
代碼實現(xiàn)如下：
/// <summary>
/// 減法(累減)
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被減數(shù)，被減數(shù)必須大于等于減數(shù)</param>
/// <param name="aLen">[in]被減數(shù)長度</param>
/// <param name="b">[in]減數(shù)</param>
/// <param name="bLen">[in]減數(shù)長度</param>
/// <returns>結(jié)果長度</returns>
static size_t subc(_NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen) {
size_t m, n, i;
if (aLen < bLen)
{
m = bLen;
n = aLen;
}
else {
n = bLen;
m = aLen;
}
for (i = 0; i < n; i++)
{
int64_t temp = (int64_t)a[i] - (int64_t)b[i];
a[i] = temp;
if (temp < 0)
{
a[i + 1] -= 1;
a[i] += _hex;
}
}
for (; i < m; i++)
{
_NUM_T temp = a[i];
if (temp < 0)
{
a[i + 1] -= 1;
a[i] += _hex;
}
else
{
break;
}
}
for (size_t i = aLen - 1; i != SIZE_MAX; i--)
if (a[i])
return i + 1;
return 1;
}3、乘法
依然是參考立豎式計算方法，兩層循環(huán)，遍歷一個數(shù)的元素去乘以另一個數(shù)的每個元素，結(jié)果記錄到新的數(shù)組中。
代碼實現(xiàn)如下：
/// <summary>
/// 乘法
/// </summary>
/// <param name="a">[in]被乘數(shù)</param>
/// <param name="aLen">[in]被乘數(shù)長度</param>
/// <param name="b">[in]乘數(shù)</param>
/// <param name="bLen">[in]乘數(shù)長度</param>
/// <param name="c">[out]結(jié)果，數(shù)組長度必須大于等于aLen+bLen+1，且全部元素為0</param>
/// <returns>結(jié)果長度</returns>
static size_t multi(const _NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen, _NUM_T c[]) {
_NUM_T d;
size_t j;
c[aLen + bLen] = 0;
for (size_t i = 0; i < aLen; i++)
{
d = 0;
for (j = 0; j < bLen; j++)
{
uint64_t temp = (uint64_t)a[i] * (uint64_t)b[j] + c[j + i] + d;
d = temp / _hex;
c[j + i] = temp % _hex;
}
if (d)
{
c[j + i] = d;
}
}
for (size_t k = aLen + bLen; k != SIZE_MAX; k--)
if (c[k])
return k + 1;
return 1;
}4、除法
基本的除法直接利用減法就可以實現(xiàn)，本方法使用的是模擬立豎式計算的方式，將移動除數(shù)使其與被除數(shù)高位對其，乘以一定倍數(shù)讓除數(shù)與被除數(shù)值接近再進行減法運算。
代碼實現(xiàn)如下：
/// <summary>
/// 除法
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)。小于商為0、余數(shù)為除數(shù)，等于商為1、余數(shù)為0，不需要在函數(shù)內(nèi)實現(xiàn)，在外部通過compare就可以做到。</param>
/// <param name="aLen">[in]被除數(shù)長度</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="bLen">[in]除數(shù)長度</param>
/// <param name="c">[out]商，數(shù)組長度大于等于aLen，且全部元素為0</param>
/// <param name="mod">[out]余數(shù)，數(shù)組長度大于等于aLen</param>
/// <param name="modLen">[out]余數(shù)長度</param>
/// <param name="temp">[in]臨時緩沖區(qū)，由外部提供以提高性能，數(shù)組長度大于等于aLen+bLen+1</param>
/// <returns>商長度</returns>
static size_t divide(const _NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen, _NUM_T* c, _NUM_T* mod, size_t* modLen, _NUM_T* temp) {
intptr_t n, l;
int equal;
memcpy(mod, a, (aLen) * sizeof(_NUM_T));
n = aLen - bLen;
l = aLen;
while (n > -1)
{
equal = compare(mod + n, l - n, b, bLen);
if (equal == -1)
{
n--;
if (!mod[l - 1])
l--;
continue;
}
if (equal == 0)
{
c[n]++;
n -= bLen;
l -= bLen;
continue;
}
uint64_t x;
if ((l - n) > bLen)
{
x = ((mod[l - 1]) * _hex) / ((uint64_t)b[bLen - 1] + 1);
if (x == 0)
{
x = (mod[l - 2]) / ((uint64_t)b[bLen - 1] + 1);
}
}
else
{
x = (mod[l - 1]) / ((uint64_t)b[bLen - 1] + 1);
}
if (x == 0)
x = 1;
c[n] += x;
if (x == 1)
{
l = n + subc(mod + n, l - n, b, bLen);
}
else
{
_NUM_T num[_MIN_NUM_SIZE];
size_t len = initByInt32(num, x);
memset(temp, 0, (aLen + bLen + 1) * sizeof(_NUM_T));
len = multi(b, bLen, num, len, temp);
l = n + subc(mod + n, l - n, temp, len);
}
}
intptr_t i = l - 1;
for (; i > -1; i--)
if (mod[i])
break;
if (i == -1)
{
mod[0] = 0;
*modLen = 1;
}
else
{
*modLen = i + 1;
}
if (c[aLen - bLen] != 0)
return aLen - bLen + 1;
else
return aLen - bLen;
}四、使用例子
1、加法例子
求 n 累加和(ja)。用高精度方法，求 s=1+2+3+……+n 的精確值(n 以一般整數(shù)輸入)。
int main(){
int64_t n;
size_t len, len2;
_NUM_T num[1024];
_NUM_T num2[1024];
std::cin >> n;
len = initByInt32(num, 0);
for (int64_t i = 1; i <= n; i++)
{
len2 = initByInt64(num2, i);
len = acc(num, len, num2, len2);
}
print(num, len);
return 0;
}
2、減法例子
兩個任意十一位數(shù)的減法；（小于二十位）
int main()
{
_NUM_T a1[8096], a2[8096];
std::string s1, s2;
std::cin >> s1 >> s2;
size_t len1,len2;
len1 =initByStr(a1, s1.c_str(), s1.size());
len2 = initByStr(a2, s2.c_str(), s2.size());
len1 =subc(a1, len1, a2, len2);
print(a1,len1);
return 0;
}
3、乘法例子
求 N！的值(ni)。用高精度方法，求 N！的精確值(N 以一般整數(shù)輸入)。
int main(){
int64_t n;
size_t len, len2;
_NUM_T num[8096];
_NUM_T num2[8096];
_NUM_T num3[8096];
_NUM_T* p1 = num;
_NUM_T* p2 = num3;
std::cin >> n;
len = initByInt32(num,1);
for (int64_t i = 1; i <= n; i++)
{
len2 = initByInt64(num2, i);
memset(p2, 0, 8096* sizeof(_NUM_T));
len = multi(p1, len, num2, len2, p2);
_NUM_T* temp = p1;
p1 = p2;
p2 = temp;
}
print(p1, len);
return 0;
}4、除法例子
給定兩個非負(fù)整數(shù)A，B，請你計算 A / B的商和余數(shù)。
int main()
{
_NUM_T a1[8096], a2[8096],c[8096],mod[8096], temp[8096];
std::string s1, s2;
std::cin >> s1 >> s2;
size_t len1,len2,ml;
len1 =initByStr(a1, s1.c_str(), s1.size());
len2 = initByStr(a2, s2.c_str(), s2.size());
memset(c, 0, 8096 * sizeof(_NUM_T));
len1 =divide(a1, len1, a2, len2,c, mod,&ml, temp);
print(c,len1);
std::cout<< std::endl ;
print(mod, ml);
return 0;
}以上就是C/C++高精度(加減乘除)算法的實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++高精度算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C++特殊成員函數(shù)以及其生成機制的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2022-02-02
C語言中進行函數(shù)指針回調(diào)的實現(xiàn)步驟
在 C 語言中,函數(shù)指針的回調(diào)是一種強大的編程技術(shù),它允許我們在特定的事件發(fā)生或特定的條件滿足時,調(diào)用由用戶定義的函數(shù),這種機制增加了程序的靈活性和可擴展性,使得代碼更具通用性和可重用性,本文給大家介紹了C語言中進行函數(shù)指針回調(diào)的實現(xiàn)步驟,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了C語言判斷回文數(shù)的小例子，有需要的朋友可以參考一下2014-01-01
這篇文章主要介紹了C語言的四大內(nèi)存函數(shù)，講解了mencpy、memmove、memcmp、memset函數(shù)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2022-07-07
C語言結(jié)構(gòu)體成員賦值的深拷貝與淺拷貝詳解
C語言中的淺拷貝是指在拷貝過程中，對于指針型成員變量只拷貝指針本身，而不拷貝指針?biāo)赶虻哪繕?biāo)，它按字節(jié)復(fù)制的。深拷貝除了拷貝其成員本身的值之外，還拷貝成員指向的動態(tài)內(nèi)存區(qū)域內(nèi)容。本文將通過示例和大家詳細(xì)說說C語言的深拷貝與淺拷貝，希望對你有所幫助2022-09-09
C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算
這篇文章主要介紹了C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算,文章中還介紹了矩陣相關(guān)的斯特拉森算法的實現(xiàn),需要的朋友可以參考下2015-12-12
這篇文章主要為大家詳細(xì)介紹了OpenCV3實現(xiàn)車牌識別功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了C++中COM組件初始化方法,涉及C++中COM組件的使用技巧,需要的朋友可以參考下2015-05-05
詳解C++中虛析構(gòu)函數(shù)的作用及其原理分析
這篇文章主要介紹了C++中虛析構(gòu)函數(shù)的作用及其原理分析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)順序表的實現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-09-09