c_cpp/etc/calc/help/rcout

   1 NAME
   2     rcout - decode for REDC algorithms
   3
   4 SYNOPSIS
   5     rcout(x, m)
   6
   7 TYPES
   8     x           integer
   9     m           odd positive integer
  10
  11     return      integer v, 0 <= v < m.
  12
  13 DESCRIPTION
  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
  33 RUNTIME
  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
  51 EXAMPLE
  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
  57 LIMITS
  58     none
  59
  60 LINK LIBRARY
  61     void zredcdecode(REDC *rp, ZVALUE z1, ZVALUE *res)
  62
  63 SEE 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 ## @(#) $Revision: 30.1 $
  83 ## @(#) $Id: rcout,v 30.1 2007/03/16 11:10:42 chongo Exp $
  84 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rcout,v $
  85 ##
  86 ## Under source code control:   1996/02/25 02:22:21
  87 ## File existed as early as:    1996
  88 ##
  89 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  90 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/