1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
Multiplication
This describes the multiplication algorithm used by the MPI library.
This is basically a standard "schoolbook" algorithm. It is slow --
O(mn) for m = #a, n = #b -- but easy to implement and verify.
Basically, we run two nested loops, as illustrated here (R is the
radix):
k = 0
for j <- 0 to (#b - 1)
for i <- 0 to (#a - 1)
w = (a[j] * b[i]) + k + c[i+j]
c[i+j] = w mod R
k = w div R
endfor
c[i+j] = k;
k = 0;
endfor
It is necessary that 'w' have room for at least two radix R digits.
The product of any two digits in radix R is at most:
(R - 1)(R - 1) = R^2 - 2R + 1
Since a two-digit radix-R number can hold R^2 - 1 distinct values,
this insures that the product will fit into the two-digit register.
To insure that two digits is enough for w, we must also show that
there is room for the carry-in from the previous multiplication, and
the current value of the product digit that is being recomputed.
Assuming each of these may be as big as R - 1 (and no larger,
certainly), two digits will be enough if and only if:
(R^2 - 2R + 1) + 2(R - 1) <= R^2 - 1
Solving this equation shows that, indeed, this is the case:
R^2 - 2R + 1 + 2R - 2 <= R^2 - 1
R^2 - 1 <= R^2 - 1
This suggests that a good radix would be one more than the largest
value that can be held in half a machine word -- so, for example, as
in this implementation, where we used a radix of 65536 on a machine
with 4-byte words. Another advantage of a radix of this sort is that
binary-level operations are easy on numbers in this representation.
Here's an example multiplication worked out longhand in radix-10,
using the above algorithm:
a = 999
b = x 999
-------------
p = 98001
w = (a[jx] * b[ix]) + kin + c[ix + jx]
c[ix+jx] = w % RADIX
k = w / RADIX
product
ix jx a[jx] b[ix] kin w c[i+j] kout 000000
0 0 9 9 0 81+0+0 1 8 000001
0 1 9 9 8 81+8+0 9 8 000091
0 2 9 9 8 81+8+0 9 8 000991
8 0 008991
1 0 9 9 0 81+0+9 0 9 008901
1 1 9 9 9 81+9+9 9 9 008901
1 2 9 9 9 81+9+8 8 9 008901
9 0 098901
2 0 9 9 0 81+0+9 0 9 098001
2 1 9 9 9 81+9+8 8 9 098001
2 2 9 9 9 81+9+9 9 9 098001
------------------------------------------------------------------
This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
# file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
