数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

[分享] HugeCalc V8.1 升级计划

[复制链接]
发表于 2013-5-27 16:56:03 | 显示全部楼层
4位十进制的商太少了,我用VB每次还可以得到12位十进制的商。如果除数是长整型时,每次可以得到21位商。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-27 20:29:58 | 显示全部楼层
30#的方法是最容易想到的算法,并且,当被除数位数较少时,这个算法也是最好的算法。但当位数较大时,这个算法的性能就很差了。例如

  被除数有180000位,除数有90000位,若用为1个DWORD表示9位10进制整数,则被除数长度为2n=2万,初数长度为n=1万。
   按30#的做法,其乘法的次数为n*n.
   因为,需要试商1万次,每得到1个部分商,则需要做1万次乘法, 一万次除法(处理本位和进位)和1万次减法。不考虑试商,总共需要1万×1万=1亿次乘法,1亿次除法,一亿次减法。

   按楼主的做法。n位数乘以n位数可以使用分治法,Toom-cook等算法,相对于硬乘法,可大大加快速度,为了便于比较。我们假设,n * n 位的的大数乘法需要 0.1 × n×n次乘法,而除法指令的比重可减少到可忽略的程度。

  当n比较大时,求n位数的除数的的倒数,并精确到n位,其复杂度不超过2个n位数的乘法,故小于0.1 * n *n 次乘法
   求除数的倒数与被除数的乘积。需要 0.1 * n *n (这里被除数仅需考虑前n个单位) 次乘法,故总共不超过0.2*n*n次乘法。而30#的算法需要n*n。 仅仅考虑乘法指令,楼主的算法比30#快5倍,若考虑30#需要大量的除法指令,则楼主的算法比30#快的更多。
  
  n * n 位的的大数乘法需要 K × n×n次乘法,K=0.1只是一个假设,在实际计算中,n越大,k的值就越小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-27 21:10:31 | 显示全部楼层
33# liangbch
以乘作除准备采纳到我的库中。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-9 18:05:37 | 显示全部楼层
30#的方法是最容易想到的算法,并且,当被除数位数较少时,这个算法也是最好的算法。但当位数较大时,这个算法的性能就很差了。例如

  被除数有180000位,除数有90000位,若用为1个DWORD表示9位10进制整数,则被除数长度为2n=2万,初数长度为n=1万。
   按30#的做法,其乘法的次数为n*n.
   因为,需要试商1万次,每得到1个部分商,则需要做1万次乘法, 一万次除法(处理本位和进位)和1万次减法。不考虑试商,总共需要1万×1万=1亿次乘法,1亿次除法,一亿次减法。

   按楼主的做法。n位数乘以n位数可以使用分治法,Toom-cook等算法,相对于硬乘法,可大大加快速度,为了便于比较。我们假设,n * n 位的的大数乘法需要 0.1 × n×n次乘法,而除法指令的比重可减少到可忽略的程度。

  当n比较大时,求n位数的除数的的倒数,并精确到n位,其复杂度不超过2个n位数的乘法,故小于0.1 * n *n 次乘法
   求除数的倒数与被除数的乘积。需要 0.1 * n *n (这里被除数仅需考虑前n个单位) 次乘法,故总共不超过0.2*n*n次乘法。而30#的算法需要n*n。 仅仅考虑乘法指令,楼主的算法比30#快5倍,若考虑30#需要大量的除法指令,则楼主的算法比30#快的更多。
  
  n * n 位的的大数乘法需要 K × n×n次乘法,K=0.1只是一个假设,在实际计算中,n越大,k的值就越小。

我目前正在学牛顿法的除法,一开始结果不对,后来慢慢的有对的了,但在大数和一个很小的数相除时,结果的最后一位不正确。还在摸索中。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-27 11:17 , Processed in 0.063551 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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