c_cpp/etc/calc/help/rcmul

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