请问大家都是怎么实现任意进制转变任意进制算法的

TobyFlenderson

毕设要求做一个高精度科学计算器，高精度的加减乘除模块都做好了，
可是内部进制转十进制模块跑的时间很慢，我现在是用“短除法”来实现改模块的，
可是短除法对于除法的效率要求很高，我的除法模块用的是试除法，时间复杂度应该为 O(n²)
最近在网上又看见一种进制转换方法，为：

对于A进制的大整数a有：
$$
a=\sum_{i=0}^n{\left( a_i\times A^i \right)}=\sum_{i=0}^{\frac{n}{2}-1}{\left( a_i\times A^i \right)}+A^{\frac{n}{2}}\sum_{i=0}^{\frac{n}{2}}{\left( a_{i+\frac{n}{2}}\times A^i \right)}
$$如果采用FNT乘法的话，该算法的时间复杂度为
$$
T\left( n \right) =2\times T\left( \frac{n}{2} \right) +O\left( n\log n \right) =O\left( n\log ^2n \right)
$$
该算法的思想我认为是用多项式乘法的技术再把原数计算一遍，这样就可以避免使用除法了

可是这样的话我就要再实现一个不进位的多项式乘法，请问大家还有没有别的进制转换方式，可以让我学习学习

TobyFlenderson

怎么没人呀

Ickiverar

进制转换应该用分治的除法。对一个比如说10^1000级别的二进制数A，先计算B=10^500，然后计算A/B的余数Z和商Q，那么原问题就转变成了两个500位数Z和Q的进制转换然后字符串拼接的问题。继续这种算法降低位数，直到位数短到能直接输出。
所以，高精度的除法是必须要高效实现的。使用牛顿迭代法可以让除法用时是乘法的一个常数倍，而fft算法可以让乘法的用时降低到 O(nlnn)。对于最简单的可用的高精度计算，这几个算法就够了。

TobyFlenderson

Ickiverar 发表于 2022-1-14 23:12
进制转换应该用分治的除法。对一个比如说10^1000级别的二进制数A，先计算B=10^500，然后计算A/B的余数Z ...

首先感谢指教！！请问牛顿迭代法计算除法是怎样实现的，多项式求逆么，看来高精度方面我还要学的东西有很多啊。。。

TobyFlenderson

Ickiverar 发表于 2022-1-14 23:12
进制转换应该用分治的除法。对一个比如说10^1000级别的二进制数A，先计算B=10^500，然后计算A/B的余数Z ...

还有，我想请问对于FFT在多项式很长的情况下怎样解决精度问题呢，是像karatsuba乘法那样分块处理么

knate

f(x) = a0*x^0 + a1*x^1 + a2*x^2 + a3*x^3 + a4*x^4 + ....

=B0*x^0 + B1*x^1 + B2*x^2 + B3*x^3 + B4*x^4 + …. (1)

= (B0 + B1*x^1)*x^0 + (B2+B3*x)*x^2 + (B4 + B5*x)*x^4 + …..

= C0*x^0 + C2*x^2 + C4*x^4 + ….. (2)

= D0*x^0 + D4*x^4 + …. (3)

.

.

.

= N0*x^0 + N(n/2) * x^(n/2) (t)

= M

nlog^2 n 已经是标准做法了. 不用除法.
知乎上的.

TobyFlenderson

knate 发表于 2022-1-20 15:34
f(x) = a0*x^0 + a1*x^1 + a2*x^2 + a3*x^3 + a4*x^4 + ....

=B0*x^0 + B1*x^1 + B2*x^2 + B3*x^3 + B4* ...

这个好像就是我贴出来的做法

gxqcn

我们知道一个数的大小是确定的，其表达形式若有所不同，只是基于不同的计数法则而已。

假设我们大脑最直观的计算法则是基于十进制(DEC)，

对于 DEC 数 \({123456}_{10}\)，大脑的理解是：\(1*10^5 +2*10^4 +3*10^3 +4*10^2 +5*10^1 + 6\)
对于 HEX 数 \( {123456}_{16}\)，大脑的理解是：\(1*16^5 +2*16^4 +3*16^3 +4*16^2 +5*16^1 + 6\)

上面的结果，前者不用计算，还是 \({123456}_{10}\) 保持不变；
后者需要一些乘加运算，最终得到 \({123456}_{16}={1193046}_{10}\)


现在反过来，用大脑计算：上述两数用十六进制如何表达？
显然，\({123456}_{16} = {123456}_{16}\)，不用再变换；
而 \( {123456}_{10}={1E240}_{16}\)，但过程就麻烦多了，有如下方法：

• 基础法：\({123456}_{10}=7716*16+0=(482*16+4)*16+0=\dots=(((1*16+14)*16+2)*16+4)*16+0={1E240}_{16}\)
• 分治法：\(16^1=16, 16^2=256, 16^4=65536, \cdots, 16^8\gt123456\)
  
  • 先转换成\(16^4\)进制，\({123456}_{10} = 1*(16^4)+57920\)，从低位向高位排列，得到系数：\([57920, 1]\)
  • 将 \(57920\) 和 \(1\)分别转换成 \(16^2\) 进制，得到 \( [[64,226],[1,0]]\)
  • 继续，直到转换成 \(16^1\) 进制，得到 \([[[0,4],[2,14]],[[1,0],[0,0]]]\)
  • 提取系数，并删除高位连续的\(0\)，得到 \({0,4,2,14,1}\)
  • 反序，转换成字符串输出，得到 \({1E240}_{16}\)，此步骤是个数字与字符映射变换的过程
    
  
  

也就是说，进制变换，
1、若目标进制，是我们当前的计数法则进制，可仅通过乘法+加法变换得到目标字串；
2、否则，需以当前的运算法则为平台，并借助除法，得到得到目标字串。

如果要将一个“7进制”的数转换成“12进制”，该怎么做呢？
在电脑中，可：7进制-->二进制-->12进制；
在人脑中，可：7进制-->十进制-->12进制；

所以，楼主所贴，即 6# 的公式，仅完成了前半部分；
后半部分，需要分治法，也即 Ickiverar 在 3# 所述。
当然，前半部分，也可用到分治法思想，只是步骤与后半部分的正好相反。

后半部分的分治法，需要用到除法，而除法可以转换成乘法，但这已是另一个话题了。

TobyFlenderson

gxqcn 发表于 2022-1-21 10:25
我们知道一个数的大小是确定的，其表达形式若有所不同，只是基于不同的计数法则而已。

假设我们大脑最直 ...

感谢郭先生的指教！您的回复我逐字读了，受益匪浅。
我想到郭先生的方法也可以用于进制是非常大的情况，比如7^128（虽然不知道这有什么用
之前以为Ickiverar兄说的和我说的是一种算法，现在看来完全是我会错意了，
现在郭先生一解释，再结合Ickiverar前辈的回复，我有点醍醐灌顶的感觉，
有这个论坛真是太好了！
（最近几天在研究大数除法，用的是牛顿迭代法，还想请教郭先生有哪些高效的除法算法，我直接去学习，可以让我少走些弯路）
下午一直忙于毕设没时间上论坛，所以只在这个时间回复了！

无心人

除法数字小的时候，还一个浮点算法，不过具体的出处我忘记了，你查下math comp