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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
Squaring Algorithm
When you are squaring a value, you can take advantage of the fact that
half the multiplications performed by the more general multiplication
algorithm (see 'mul.txt' for a description) are redundant when the
multiplicand equals the multiplier.
In particular, the modified algorithm is:
k = 0
for j <- 0 to (#a - 1)
w = c[2*j] + (a[j] ^ 2);
k = w div R
for i <- j+1 to (#a - 1)
w = (2 * a[j] * a[i]) + k + c[i+j]
c[i+j] = w mod R
k = w div R
endfor
c[i+j] = k;
k = 0;
endfor
On the surface, this looks identical to the multiplication algorithm;
however, note the following differences:
- precomputation of the leading term in the outer loop
- i runs from j+1 instead of from zero
- doubling of a[i] * a[j] in the inner product
Unfortunately, the construction of the inner product is such that we
need more than two digits to represent the inner product, in some
cases. In a C implementation, this means that some gymnastics must be
performed in order to handle overflow, for which C has no direct
abstraction. We do this by observing the following:
If we have multiplied a[i] and a[j], and the product is more than half
the maximum value expressible in two digits, then doubling this result
will overflow into a third digit. If this occurs, we take note of the
overflow, and double it anyway -- C integer arithmetic ignores
overflow, so the two digits we get back should still be valid, modulo
the overflow.
Having doubled this value, we now have to add in the remainders and
the digits already computed by earlier steps. If we did not overflow
in the previous step, we might still cause an overflow here. That
will happen whenever the maximum value expressible in two digits, less
the amount we have to add, is greater than the result of the previous
step. Thus, the overflow computation is:
u = 0
w = a[i] * a[j]
if(w > (R - 1)/ 2)
u = 1;
w = w * 2
v = c[i + j] + k
if(u == 0 && (R - 1 - v) < w)
u = 1
If there is an overflow, u will be 1, otherwise u will be 0. The rest
of the parameters are the same as they are in the above description.
------------------------------------------------------------------
***** BEGIN LICENSE BLOCK *****
Version: MPL 1.1/GPL 2.0/LGPL 2.1
The contents of this file are subject to the Mozilla Public License Version
1.1 (the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.mozilla.org/MPL/
Software distributed under the License is distributed on an "AS IS" basis,
WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
for the specific language governing rights and limitations under the
License.
The Original Code is the MPI Arbitrary Precision Integer Arithmetic
library.
The Initial Developer of the Original Code is
Michael J. Fromberger <sting@linguist.dartmouth.edu>
Portions created by the Initial Developer are Copyright (C) 1998, 2000
the Initial Developer. All Rights Reserved.
Contributor(s):
Alternatively, the contents of this file may be used under the terms of
either the GNU General Public License Version 2 or later (the "GPL"), or
the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
in which case the provisions of the GPL or the LGPL are applicable instead
of those above. If you wish to allow use of your version of this file only
under the terms of either the GPL or the LGPL, and not to allow others to
use your version of this file under the terms of the MPL, indicate your
decision by deleting the provisions above and replace them with the notice
and other provisions required by the GPL or the LGPL. If you do not delete
the provisions above, a recipient may use your version of this file under
the terms of any one of the MPL, the GPL or the LGPL.
***** END LICENSE BLOCK *****
$Id$
|
