Sequence of primorial primes: Difference between revisions
m
→The plan
m (→The plan) |
m (→The plan) |
||
Line 1,480:
Already, the formula translation of ''A<sup>B</sup> mod N'' into <code>MOD(A**B,N)</code> has first been abandoned for "bignumber" arithmetic to encompass numbers far beyond ordinary integer arithmetic, and secondly, the ''mod'' operation has been pushed into the evaluation of ''A<sup>B</sup>'' because otherwise the value would increase to a size beyond any possible storage capacity since the variables might be hundred-digit numbers and more. A third push is possible: into the evaluation of multiply itself.
Suppose for specificity, all three numbers are four digits long and A*B is to be calculated. The scheme followed is to produce the product via BIGMULT, then reduce it via BIGMOD. Thus an eight-digit number is produced by the multiply and after the ''mod'' it is reduced to a four-digit number. In positional notation the product is X<sub>8</sub>X<sub>7</sub>X<sub>6</sub>X<sub>5</sub>X<sub>4</sub>X<sub>3</sub>X<sub>2</sub>X<sub>1</sub>, which is of course for base b a summation of X<sub>8</sub>b<sup>7</sup> + X<sub>7</sub>b<sup>6</sup> + ''etc''. and it would be possible to apply the ''mod'' to high-order digits separately. Imagine a table of the values ''of b<sup>i</sup> mod N'' for the digits above four. This table need have only the same four digits as N, and, given that A and B are already reduced modulo N, it need only extend as far as to handle an eight-digit number. There need be no entries for numbers up to four digits. Once prepared, it can be used for all multiplications involving modulo N.
Referring to the template multiply presented in BIGMULT, once a column sum S is prepared, it will be placed in the result if it is for the first four digits, and for higher digits, the result will be augmented by <code>MOD(S,BIGNUM)*REM(L)</code> via subroutine BADDREM where <code>REM(L)</code> would be the four-digit remainder corresponding to digit L (<code>MOD(BIGBASE**(L - 1),N)</code>, remembering that digit one is the units digits with power zero) and <code>MOD(S,BIGNUM)</code> would normally be the value for <code>DIGIT(L)</code> and <code>S/BIGBASE</code> would be its carry to the next digit up. All this is more convenient to arrange working from the low-order up (as in primary-school multiplication) rather than the high-order end down used by BIGMULT that allows the result to be constructed in-place on top of variable A. In short, a temporary variable is used, which means additional effort in copying the result to replace the value in A. But this temporary variable will not grow much longer than the length of N, a digit or two depending on how many additions are made, but definitely not as far as twice as many digits. There will be no production of an eight-digit number, laboriously reduced by BIGMOD to four digits. There will still be a BIGMOD at the end, but of a much smaller number. This also means that numbers approaching BIGLIMIT in size can still be multiplied by BMODMULT because unlike with BIGMULT there will be no double-size result that would otherwise limit the size of numbers to BIGLIMIT/2, remembering that variable-sized numbers incur a performance penalty.
| |||