← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/security/nss/lib/freebl/mpi/doc/mul.txt

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/security/nss/lib/freebl/mpi/doc/mul.txt
 
1
Multiplication
 
2
 
 
3
This describes the multiplication algorithm used by the MPI library.
 
4
 
 
5
This is basically a standard "schoolbook" algorithm.  It is slow --
 
6
O(mn) for m = #a, n = #b -- but easy to implement and verify.
 
7
Basically, we run two nested loops, as illustrated here (R is the
 
8
radix):
 
9
 
 
10
k = 0
 
11
for j <- 0 to (#b - 1)
 
12
  for i <- 0 to (#a - 1)
 
13
    w = (a[j] * b[i]) + k + c[i+j]
 
14
    c[i+j] = w mod R
 
15
    k = w div R
 
16
  endfor
 
17
  c[i+j] = k;
 
18
  k = 0;
 
19
endfor
 
20
 
 
21
It is necessary that 'w' have room for at least two radix R digits.
 
22
The product of any two digits in radix R is at most:
 
23
 
 
24
        (R - 1)(R - 1) = R^2 - 2R + 1
 
25
 
 
26
Since a two-digit radix-R number can hold R^2 - 1 distinct values,
 
27
this insures that the product will fit into the two-digit register.
 
28
 
 
29
To insure that two digits is enough for w, we must also show that
 
30
there is room for the carry-in from the previous multiplication, and
 
31
the current value of the product digit that is being recomputed.
 
32
Assuming each of these may be as big as R - 1 (and no larger,
 
33
certainly), two digits will be enough if and only if:
 
34
 
 
35
        (R^2 - 2R + 1) + 2(R - 1) <= R^2 - 1
 
36
 
 
37
Solving this equation shows that, indeed, this is the case:
 
38
 
 
39
        R^2 - 2R + 1 + 2R - 2 <= R^2 - 1
 
40
 
 
41
        R^2 - 1 <= R^2 - 1
 
42
 
 
43
This suggests that a good radix would be one more than the largest
 
44
value that can be held in half a machine word -- so, for example, as
 
45
in this implementation, where we used a radix of 65536 on a machine
 
46
with 4-byte words.  Another advantage of a radix of this sort is that
 
47
binary-level operations are easy on numbers in this representation.
 
48
 
 
49
Here's an example multiplication worked out longhand in radix-10,
 
50
using the above algorithm:
 
51
 
 
52
   a =     999
 
53
   b =   x 999
 
54
  -------------
 
55
   p =   98001
 
56
 
 
57
w = (a[jx] * b[ix]) + kin + c[ix + jx]
 
58
c[ix+jx] = w % RADIX
 
59
k = w / RADIX
 
60
                                                               product
 
61
ix      jx      a[jx]   b[ix]   kin     w       c[i+j]  kout    000000
 
62
0       0       9       9       0       81+0+0  1       8       000001
 
63
0       1       9       9       8       81+8+0  9       8       000091
 
64
0       2       9       9       8       81+8+0  9       8       000991
 
65
                                8                       0       008991
 
66
1       0       9       9       0       81+0+9  0       9       008901
 
67
1       1       9       9       9       81+9+9  9       9       008901
 
68
1       2       9       9       9       81+9+8  8       9       008901
 
69
                                9                       0       098901
 
70
2       0       9       9       0       81+0+9  0       9       098001
 
71
2       1       9       9       9       81+9+8  8       9       098001
 
72
2       2       9       9       9       81+9+9  9       9       098001
 
73
 
 
74
------------------------------------------------------------------
 
75
The contents of this file are subject to the Mozilla Public
 
76
License Version 1.1 (the "License"); you may not use this file
 
77
except in compliance with the License. You may obtain a copy of
 
78
the License at http://www.mozilla.org/MPL/
 
79
 
 
80
Software distributed under the License is distributed on an "AS
 
81
IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
 
82
implied. See the License for the specific language governing
 
83
rights and limitations under the License.
 
84
 
 
85
The Original Code is the MPI Arbitrary Precision Integer Arithmetic
 
86
library.
 
87
 
 
88
The Initial Developer of the Original Code is 
 
89
Michael J. Fromberger <sting@linguist.dartmouth.edu>
 
90
 
 
91
Portions created by Michael J. Fromberger are 
 
92
Copyright (C) 1998, 2000 Michael J. Fromberger. All Rights Reserved.
 
93
 
 
94
Contributor(s):
 
95
 
 
96
Alternatively, the contents of this file may be used under the
 
97
terms of the GNU General Public License Version 2 or later (the
 
98
"GPL"), in which case the provisions of the GPL are applicable
 
99
instead of those above.  If you wish to allow use of your
 
100
version of this file only under the terms of the GPL and not to
 
101
allow others to use your version of this file under the MPL,
 
102
indicate your decision by deleting the provisions above and
 
103
replace them with the notice and other provisions required by
 
104
the GPL.  If you do not delete the provisions above, a recipient
 
105
may use your version of this file under either the MPL or the GPL.
 
106
 
 
107
$Id: mul.txt,v 1.1 2000/07/14 00:44:35 nelsonb%netscape.com Exp $
 
108
 
 
109