c*****t
发帖数: 1879 | 1 【 以下文字转载自 Programming 讨论区 】
【 原文由 coconut 所发表 】
my friend is trying to write a giantint type calculator. So,
what's the fastest way of doing multiplications and division?
The algorithm?
thanks.
coco |
c*****t
发帖数: 1879 | 2 偶想到的乘法是:
1110000 (base 2)
x
101
=
1110000 << 2
+
1110000 << 0
这样的话 32 x 32 bit 乘法要 32 步就完成了.
偶想到的除法是
1111 (4 bits)
/
101 (3 bits)
=
101 << 1 // 1 = 4 - 3
+ (101 << 1 + 101 << 0 ) < 1111 ? 101 << 0 : 0
...
也要不少步, 但起码比一个个加减强一点. 觉得应该有更
快的... |
k**y
发帖数: 320 | 3 乘法是对的,除法好象是转化成乘法/加法算的,不过我记不得了
谁有闲心把汇编码看一下就行了
至于快速变换,好象要求是2^n bit的,(a+b)*(c+d)=...
可能80387是根据这个原理做的
coconut是椰子耶,怎么成了可可了?
【在 c*****t 的大作中提到】
: 偶想到的乘法是:
: 1110000 (base 2)
: x
: 101
: =
: 1110000 << 2
: +
: 1110000 << 0
: 这样的话 32 x 32 bit 乘法要 32 步就完成了.
: 偶想到的除法是
|
d*********n
发帖数: 74 | 4 You can refer to books about Divide-and-Conquer Algorithm.
It is the fastest algorithm.
【在 k**y 的大作中提到】
: 乘法是对的,除法好象是转化成乘法/加法算的,不过我记不得了
: 谁有闲心把汇编码看一下就行了
: 至于快速变换,好象要求是2^n bit的,(a+b)*(c+d)=...
: 可能80387是根据这个原理做的
: coconut是椰子耶,怎么成了可可了?
|
e***r
发帖数: 37 | 5 try Goldschmidt's algorithm for the division?
【在 c*****t 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 【 原文由 coconut 所发表 】
: my friend is trying to write a giantint type calculator. So,
: what's the fastest way of doing multiplications and division?
: The algorithm?
: thanks.
: coco
|
e*****e
发帖数: 17 | 6 去www.gnu.org,
有一个软件是做任意位数的integer运算... GPLed
【在 c*****t 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 【 原文由 coconut 所发表 】
: my friend is trying to write a giantint type calculator. So,
: what's the fastest way of doing multiplications and division?
: The algorithm?
: thanks.
: coco
|
