C++高精度算法 | SnowDreamXUE 的 Notion

type

status

date

slug

summary

高精度加法

算法思想：倒置相加再还原。

算法复杂度：o(n)

高精度减法

算法思想：倒置相减再还原。

算法复杂度：o(n)

高精度乘法

1.高精度乘高精度的简单算法

思想：倒置相乘，统一处理进位，还原。

复杂度：o(n^2)

2.高精度乘高精度FFT优化算法

思想：将两个大整数看作多项式的系数，然后利用FFT算法在O(n log n)的时间复杂度内计算出它们的乘积，并最终得到乘积的各位数字。

复杂度：o(nlog(n))

具体步骤：

将输入的两个大整数转换为对应的多项式表示，其中每个数字位作为多项式的系数。

对两个多项式进行补零操作，使其长度变为2的幂，方便进行FFT运算。

利用FFT算法对两个多项式进行快速傅里叶变换，得到它们在频域上的表示。

将两个多项式在频域上进行点乘操作，得到它们的乘积在频域上的表示。

对乘积进行逆FFT操作，得到乘积多项式在时域上的表示。

对乘积多项式进行进位处理，并输出最终的乘积结果。

3.高精度乘单精度

思想：倒置相乘，统一处理进位，再还原。

复杂度：o(n)

高精度除法

1.高精度除于高精度

思想：倒置，试商，高精度减法。

算法复杂度：o(n^2)

2.高精度除与低精度

思想：模拟手工除法

算法复杂度：o(n)

高精度取模

1.高精度对高精度取模

已在高精度除高精度中实现)

2.高精度对单精度取模

思想：利用 (a+b)%c=a%c+b%c。

算法复杂度：o(n)

高精度阶乘

思想：高精度乘单精度的简单运用。

算法复杂度：o(n^2)

高精度幂

传入参数约定：传入第一参数为string类型，第二个为int型，返回值为string型

算法思想：FFT高精乘+二分求幂。

算法复杂度：o(n*log(n)*log(m))

高精度GCD

参数约定：传入参数均为string类型，返回值为string类型

算法思想：高精度加减乘除的运用。

算法复杂度：已无法估计。

高精度进制转换

传入参数约定：传入第一个参数为string类型，第二第三均为int型，返回值为string类型

算法思想：模拟手工进制转换。

算法复杂度：o(n^2)。

高精度求平方根

思路就是二分+高精度加减乘除法

设数的长度为n，则需二分log(2,10^n)次即n*log(2,10)约等于n*3.3，由于数的长度为n，朴素高精度乘法复杂度为o(n^2)。

故朴素算法求解高精度平方根复杂度为O(n^3) 当然，你也可以用FFT优化下高精度乘法。

下面的代码实现了求大整数平方根的整数部分。