1NAME 2 rcout - decode for REDC algorithms 3 4SYNOPSIS 5 rcout(x, m) 6 7TYPES 8 x integer 9 m odd positive integer 10 11 return integer v, 0 <= v < m. 12 13DESCRIPTION 14 Let B be the base calc uses for representing integers internally 15 (B = 2^16 for 32-bit machines, 2^32 for 64-bit machines) and N the 16 number of words (base-B digits) in the representation of m. Then 17 rcout(x,m) returns the value of B^-N * x % m, where the inverse 18 implicit in B^-N is modulo m and the modulus operator % gives the 19 least non-negative residue. The functions rcin() and rcout() are 20 inverses of each other for all x: 21 22 rcout(rcin(x,m), m) = rcin(rcout(x,m),m) = x % m. 23 24 The normal use of rcout() may be said to be that of decoding 25 values encoded by rcin() and REDC functions, as in: 26 27 x * y % m = rcout(rcmul(rcin(x,m),rcin(y,m),m),m), 28 29 x^2 % m = rcout(rcsq(rcin(x,m),m),m), 30 31 x ^ k % m = rcout(rcpow(rcin(x,m),k,m),m). 32 33RUNTIME 34 If the value of m in rcout(x,m) is being used for the first time in 35 a REDC function, the information required for the REDC algorithms 36 is calculated and stored for future use, possibly replacing an 37 already stored valued, in a table covering up to 5 (i.e. MAXREDC) 38 values of m. The runtime required for this is about two times that 39 required for multiplying two N-word integers. 40 41 Two algorithms are available for evaluating rcout(x, m), the one 42 which is usually faster for small N is used when N < 43 config("pow2"); the other is usually faster for larger N. If 44 config("pow2") is set at about 200, and x has been reduced modulo 45 m, the runtime required for rcout(x, m) is at most about f times 46 the runtime required for an N-word by N-word multiplication, where 47 f increases from about 1 for N = 1 to near 2 for N > 48 config("pow2"). More runtime may be required if x has to be 49 reduced modulo m. 50 51EXAMPLE 52 Using a 64-bit machine with B = 2^32: 53 54 ; for (i = 0; i < 9; i++) print rcout(i,9),:; print; 55 0 7 5 3 1 8 6 4 2 56 57LIMITS 58 none 59 60LINK LIBRARY 61 void zredcdecode(REDC *rp, ZVALUE z1, ZVALUE *res) 62 63SEE ALSO 64 rcout, rcmul, rcsq, rcpow 65 66## Copyright (C) 1999 Landon Curt Noll 67## 68## Calc is open software; you can redistribute it and/or modify it under 69## the terms of the version 2.1 of the GNU Lesser General Public License 70## as published by the Free Software Foundation. 71## 72## Calc is distributed in the hope that it will be useful, but WITHOUT 73## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 74## or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 75## Public License for more details. 76## 77## A copy of version 2.1 of the GNU Lesser General Public License is 78## distributed with calc under the filename COPYING-LGPL. You should have 79## received a copy with calc; if not, write to Free Software Foundation, Inc. 80## 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 81## 82## Under source code control: 1996/02/25 02:22:21 83## File existed as early as: 1996 84## 85## chongo <was here> /\oo/\ http://www.isthe.com/chongo/ 86## Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/ 87