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