快捷導航

C/C++高精度算法實現(xiàn)思路與代碼

更新時間：2023年11月28日 15:08:37 作者：仍有未知等待探索

高精度算法就是能處理高精度數(shù)各種運算的算法,但又因其特殊性,故從普通數(shù)的算法中分離,自成一家,下面這篇文章主要給大家介紹了關(guān)于C/C++高精度算法實現(xiàn)思路與代碼的相關(guān)資料,需要的朋友可以參考下

前言

由于c++不能進行位數(shù)過高的數(shù)據(jù)運算，所以要通過模擬數(shù)組來進行運算，首先是加法。通過char或string型數(shù)據(jù)輸入字符來模擬數(shù)字的輸入，數(shù)組下表對應(yīng)的元素應(yīng)當是處于同一位置的數(shù)字，下標相同的兩個元素相加表示的既是結(jié)果。

一、高精度加法

1、思路

其實高精度加法和普通的加法思路沒有什么區(qū)別。就是個位數(shù)先相加，然后判斷進位，在把進位進行相加。最后得到結(jié)果。

從個位開始進行相加，進位操作。（通過數(shù)組進行存儲）

2、代碼

#include<iostream>
#include<string>
using namespace std;

const int N = 510;//數(shù)字最大可以存儲509位的數(shù)字
int a[N];//要相加的數(shù)字
int b[N];//要相加的數(shù)字
int c[N];//得到的結(jié)果
int main()
{
    string str1;//要想加的數(shù)字
    string str2;//要相加的數(shù)字
    cin >> str1;
    cin >> str2;
    //將str1和str2進行逆置存放
    for (int i = 0; i < str1.size(); i++)
        a[str1.size() - 1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i++)
        b[str2.size() - 1 - i] = str2[i] - '0';
    //得到最大的位數(shù)
    int ans = max(str1.size(), str2.size());
    for (int i = 0; i < ans; i++) {
        c[i] += a[i] + b[i];//相加
        c[i + 1] = c[i] / 10;//進位
        c[i] %= 10;//如果1位數(shù)大于10，對其進行取余
    }
    ans += 1;//避免最大位數(shù)相加完之后有進位：比如說500+500，5+5=10，要進位
    //去除前導0
    if (c[ans - 1] == 0 && ans > 1)
        ans -= 1;
    //輸出
    for (int i = 0; i < ans; i++)
        cout << c[ans - 1 - i];
    return 0;
}

二、高精度乘法

1、思路

按照常規(guī)的高精度乘法的思路，分別先用兩個數(shù)組逆序存儲兩數(shù)，方便計算。
結(jié)果的長度必然不會超過兩數(shù)的長度之和。
進行乘法運算時，我們可以先不用考慮進位，按照常規(guī)思路直接算。
計算完成后，處理數(shù)組中結(jié)果大于或等于10的位置，即向前進位。
最后，處理前導零，將結(jié)果逆序輸出。

高精度乘法和豎式運算的乘法思路是一樣的。如圖所示：

根據(jù)上面的規(guī)律可以知道下圖的公式。

2、代碼

#include<iostream>
using namespace std;
const int N = 2000;
int m[N];//要算的數(shù)
int n[N];//要算的數(shù)
int ans[2 * N];//所得的答案
int main() {
	string a, b;//字符串輸入
	cin >> a >> b;
	int la = a.size();//a的字符串長，也就是乘數(shù)的位數(shù)
	int lb = b.size();//b的字符串長，也就是乘數(shù)的位數(shù)
	int i = 0, j = 0;
	//逆序存入數(shù)組中
	for (i = 0; i < la; i++) {
		m[i] = a[la - i - 1] - '0';
	}
	//逆序存入數(shù)組中
	for (j = 0; j < lb; j++) {
		n[j] = b[lb - j - 1] - '0';
	}
	//根據(jù)公式進行計算
	for (i = 0; i < la; i++) {
		for (j = 0; j < lb; j++) {
			ans[i + j] += m[i] * n[j];
		}
	}
	//上述僅進行了計算各個位的數(shù)，沒有考慮進位
	//下面循環(huán)考慮進位
	//ns為答案的位數(shù)，由例子可知，答案的位數(shù)的最小值為la+lb-1
	int ns = la + lb - 1;
	for (i = 0; i < ns; i++) {
		//各位大于9時，才考慮進位的問題
		if (ans[i] > 9) {
			ans[i + 1] += ans[i] / 10;
			ans[i] %= 10;
		}
		//如果i+1進位大于ns，ns要進行更新
		if (i + 1 > ns) {
			ns++;
		}
	}
	//逆序打印
	//考慮先導0的問題
	if (ans[i] == 0 && ns > 1)
		ns--;
	for (i = ns; i >= 0; i--) {
		cout << ans[i];
	}
	return 0;
}

附：c++高精度浮點數(shù)計算

C++自帶的float和double類型精度有限，無法進行高精度計算。如果需要進行高精度浮點數(shù)計算，可以使用第三方庫，如GMP（GNU Multiple Precision Arithmetic Library）和MPFR（Multiple Precision Floating-Point Reliable Library）等。

以下是使用GMP庫進行高精度浮點數(shù)計算的示例代碼：

#include <iostream>
#include <gmpxx.h>

int main()
{
    mpf_set_default_prec(64); // 設(shè)置默認精度為64位
    mpf_class a("123.456"); // 定義高精度浮點數(shù)a
    mpf_class b("789.012"); // 定義高精度浮點數(shù)b
    mpf_class c; // 定義高精度浮點數(shù)c
    c = a + b; // 高精度浮點數(shù)加法
    std::cout << c << std::endl; // 輸出結(jié)果
    return 0;
}

上述代碼中，mpf_class是GMP庫中表示高精度浮點數(shù)的類，mpf_set_default_prec函數(shù)用于設(shè)置默認精度，mpf_class的構(gòu)造函數(shù)可以接受字符串或整數(shù)作為參數(shù)，進行高精度浮點數(shù)的初始化，高精度浮點數(shù)的加法和輸出結(jié)果的方式與普通浮點數(shù)相同。