c_cpp/etc/calc/help/rcin

   1 NAME
   2     rcin - encode for REDC algorithms
   3
   4 SYNOPSIS
   5     rcin(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     rcin(x,m) returns the value of B^N * x % m, where the modulus
  18     operator % here gives the least nonnegative residue.
  19
  20     If y = rcin(x,m), x % m may be evaluated by x % m = rcout(y, m).
  21
  22     The "encoding" method of using rcmul(), rcsq(), and rcpow() for
  23     evaluating products, squares and powers modulo m correspond to the
  24     formulae:
  25
  26             rcin(x * y, m) = rcmul(rcin(x,m), rcin(y,m), m);
  27
  28             rcin(x^2, m) = rcsq(rcin(x,m), m);
  29
  30             rcin(x^k, m) = rcpow(rcin(x,m), k, m).
  31
  32     Here k is any nonnegative integer.  Using these formulae may be
  33     faster than direct evaluation of x * y % m, x^2 % m, x^k % m.
  34     Some encoding and decoding may be bypassed by formulae like:
  35
  36             x * y % m = rcin(rcmul(x, y, m), m).
  37
  38     If m is a divisor of B^N - h for some integer h, rcin(x,m) may be
  39     computed by using rcin(x,m) = h * x % m.  In particular, if
  40     m is a divisor of B^N - 1 and 0 <= x < m, then rcin(x,m) = x.
  41     For example if B = 2^16 or 2^32, this is so for m = (B^N - 1)/d
  42     for the divisors d = 3, 5, 15, 17, ...
  43
  44 RUNTIME
  45     The first time a particular value for m is used in rcin(x, m),
  46     the information required for the REDC algorithms is
  47     calculated and stored for future use in a table covering up to
  48     5 (i.e. MAXREDC) values of m.  The runtime required for this is about
  49     two that required for multiplying two N-word integers.
  50
  51     Two algorithms are available for evaluating rcin(x, m), the one
  52     which is usually faster for small N is used when N <
  53     config("pow2"); the other is usually faster for larger N. If
  54     config("pow2") is set at about 200 and x has both been reduced
  55     modulo m, the runtime required for rcin(x, m) is at most about f
  56     times the runtime required for an N-word by N-word multiplication,
  57     where f increases from about 1.3 for N = 1 to near 2 for N > 200.
  58     More runtime may be required if x has to be reduced modulo m.
  59
  60 EXAMPLE
  61     Using a 64-bit machine with B = 2^32:
  62
  63     ; for (i = 0; i < 9; i++) print rcin(x, 9),:; print;
  64     0 4 8 3 7 2 6 1 5
  65
  66 LIMITS
  67     none
  68
  69 LINK LIBRARY
  70     void zredcencode(REDC *rp, ZVALUE z1, ZVALUE *res)
  71
  72 SEE ALSO
  73    rcout, rcmul, rcsq, rcpow
  74
  75 ## Copyright (C) 1999  Landon Curt Noll
  76 ##
  77 ## Calc is open software; you can redistribute it and/or modify it under
  78 ## the terms of the version 2.1 of the GNU Lesser General Public License
  79 ## as published by the Free Software Foundation.
  80 ##
  81 ## Calc is distributed in the hope that it will be useful, but WITHOUT
  82 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  83 ## or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  84 ## Public License for more details.
  85 ##
  86 ## A copy of version 2.1 of the GNU Lesser General Public License is
  87 ## distributed with calc under the filename COPYING-LGPL.  You should have
  88 ## received a copy with calc; if not, write to Free Software Foundation, Inc.
  89 ## 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  90 ##
  91 ## @(#) $Revision: 30.1 $
  92 ## @(#) $Id: rcin,v 30.1 2007/03/16 11:10:42 chongo Exp $
  93 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rcin,v $
  94 ##
  95 ## Under source code control:   1996/02/25 02:22:21
  96 ## File existed as early as:    1996
  97 ##
  98 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  99 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/