云梦 发表于 2013-5-27 16:56:03

4位十进制的商太少了,我用VB每次还可以得到12位十进制的商。如果除数是长整型时,每次可以得到21位商。

liangbch 发表于 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的值就越小。

G-Spider 发表于 2013-5-27 21:10:31

33# liangbch
以乘作除准备采纳到我的库中。:lol

只是呼吸 发表于 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的值就越小。
我目前正在学牛顿法的除法,一开始结果不对,后来慢慢的有对的了,但在大数和一个很小的数相除时,结果的最后一位不正确。还在摸索中。
页: 1 2 3 [4]
查看完整版本: HugeCalc V8.1 升级计划