diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/doc/mul.txt')
| -rw-r--r-- | security/nss/lib/freebl/mpi/doc/mul.txt | 114 |
1 files changed, 0 insertions, 114 deletions
diff --git a/security/nss/lib/freebl/mpi/doc/mul.txt b/security/nss/lib/freebl/mpi/doc/mul.txt deleted file mode 100644 index 01464f251..000000000 --- a/security/nss/lib/freebl/mpi/doc/mul.txt +++ /dev/null @@ -1,114 +0,0 @@ -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 - ------------------------------------------------------------------- -***** 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$ - - |