数学研发论坛

 找回密码
 欢迎注册
查看: 499|回复: 18

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

[复制链接]
发表于 2022-1-13 09:59:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

对于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)
$$
该算法的思想我认为是用多项式乘法的技术再把原数计算一遍,这样就可以避免使用除法了

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


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-13 13:28:19 | 显示全部楼层
怎么没人呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-1-14 23:12:13 | 显示全部楼层

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-15 08:21:42 | 显示全部楼层
Ickiverar 发表于 2022-1-14 23:12
进制转换应该用分治的除法。对一个比如说10^1000级别的二进制数A,先计算B=10^500,然后计算A/B的余数Z ...

首先感谢指教!!请问牛顿迭代法计算除法是怎样实现的,多项式求逆么,看来高精度方面我还要学的东西有很多啊。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-15 08:25:29 | 显示全部楼层
Ickiverar 发表于 2022-1-14 23:12
进制转换应该用分治的除法。对一个比如说10^1000级别的二进制数A,先计算B=10^500,然后计算A/B的余数Z ...

还有,我想请问对于FFT在多项式很长的情况下怎样解决精度问题呢,是像karatsuba乘法那样分块处理么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-1-20 15:34:41 | 显示全部楼层
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 已经是标准做法了. 不用除法.
知乎上的.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-20 20:20:31 | 显示全部楼层
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* ...

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

点评

本来就是啊  发表于 2022-1-20 23:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-1-21 10:25:15 | 显示全部楼层
我们知道一个数的大小是确定的,其表达形式若有所不同,只是基于不同的计数法则而已。

假设我们大脑最直观的计算法则是基于十进制(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# 所述。
当然,前半部分,也可用到分治法思想,只是步骤与后半部分的正好相反。

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

点评

不知道这个结构体为可修改时, 在SSE 代码影响有多大.SSE代码我不懂不会测试. 一般的测试, 这个结构体是否可变,基本上,对速度没有影响(不是很详细的测试),硬要改固定参数也简单, 只要强制类型变换一下就可以了.  发表于 2022-1-25 11:32
两个是可设置进制的参数(会扩散影响整个类),还有一个是每个对象都带上一个独立的结构体(整个不合适计算, 仅用在特殊情况的临时存放, 计算时效率极低)  发表于 2022-1-25 11:26
区别当然是有的了. 但是不会很大.也不需要重新编译运行.如果所有跟进制相关所需要的参数都丢在一个结构体内, 这个结构体如运行修正就是任意进制, 我的做法是做了5个类,两个固定的常见的二/十进制.  发表于 2022-1-25 11:22
多进制与任意进制,还是有区别的。前者是有限的,比如二/十双进制;后者则是用户任意指定的,除非代码可修订后再编译运行,否则不可避免需要大整数的带余除法运算来实现。  发表于 2022-1-24 11:33
应该还好吧. 只要库支持二/十 双进制, 支持多进制应该是水到渠成的事了. 架构好的话,仅需要把底层优化的汇编改写一下就好了. 工作量不大, 现在C++支持常量表达式了, 这个优化应该算很好改的.  发表于 2022-1-24 11:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-21 20:42:17 | 显示全部楼层
gxqcn 发表于 2022-1-21 10:25
我们知道一个数的大小是确定的,其表达形式若有所不同,只是基于不同的计数法则而已。

假设我们大脑最直 ...


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

点评

感觉你似乎没看明白大神 Ickiverar 所描述的,我就举例说明了下。  发表于 2022-1-21 21:07
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-3-1 11:23:13 | 显示全部楼层
除法数字小的时候,还一个浮点算法,不过具体的出处我忘记了,你查下math comp
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-8-10 04:47 , Processed in 0.118917 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表