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