云梦
发表于 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的值就越小。
我目前正在学牛顿法的除法,一开始结果不对,后来慢慢的有对的了,但在大数和一个很小的数相除时,结果的最后一位不正确。还在摸索中。