home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
vol_200
/
247_02
/
manual2.doc
< prev
next >
Wrap
Text File
|
1989-04-19
|
61KB
|
2,641 lines
Appendix III - MIRACL routines
Note: In these routines a big parameter can also be used wherever a
flash is specified, but not visa-versa. Further information may
be gleaned from the (lightly) commented source code.
Function: void absol(x,y) absol
flash x,y;
Module: bncore.c
Description: Gives absolute value of a big or flash number.
Parameters: Two big/flash variables x and y. On exit y=abs(x).
Return value: None
Restrictions: None
See also: negate
Function: void add(x,y,z) add
big x,y,z;
Module: bnarth0.c
Description: Adds two big numbers.
Parameters: Three big numbers x, y and z. On exit z=x+y.
Return value: None
Restrictions: None
See also: subtract, incr, decr.
Example: add(x,x,x);
This doubles the value of x.
Function: void bigdig(x,n,b) bigdig
big x;
int n,b;
Module: bnrand.c
Description: Generates a big random number of given length.
Parameters: A big number x and two integers n and b. On exit x
contains a big random number n digits long to base b.
Return value: None
Restrictions: None
See also: bigrand
Example: bigdig(x,100,10);
This generates a 100 decimal digit random number x
Function: void bigrand(w,x) bigrand
big w,x;
Module: bnrand.c
Description: Generates a big random number.
Parameters: Two big numbers w and x. On exit x is a big random number
in the range 1<x<w.
Return value: None
Restrictions: None
See also: bigdig
Function: int brand() brand
Module: bncore.c
Description: Generates random integer number
Parameters: None
Return Value: A random integer number
Restrictions: First use must be preceded by an initial call to irand.
See also: irand, bigrand, bigdig, frand.
Function: void build(x,gener) build
flash x;
int (*gener)();
Module: bnbuild.c
Description: Uses supplied generator of regular continued fraction
expansion to build up a flash number, rounded if
necessary.
Parameters: The flash number created, and the generator function.
Return value: None
Restrictions: None
See also: round, froot, fexp, ftan
Example: int phi(w,n)
flash w;
int n;
{ /* rcf generator for golden ratio */
return 1;
}
.
.
build(x,phi);
.
This will calculate the golden ratio in x - very quickly!
Function: int cinnum(x,f) cinnum
flash x;
FILE *f;
Module: bnio2.c
Description: Inputs a flash number from the keyboard, a file or a
string, using as number base the current value of the
global variable IOBASE. Flash numbers can be entered
using either a slash '/' to indicate numerator and
denominator, or with a radix point.
Parameters: A big/flash number x and a file descriptor f. For
input from the keyboard specify f as stdin, otherwise
as the descriptor of some other opened file. To input
from a string copy the string to the global character
array IBUFF before calling cinnum. In this case the
file descriptor will be ignored and input taken from
IBUFF instead. To force input of a fixed number of
bytes, set global INPLEN to the required number,
just before calling cinnum.
Return value: The number of input characters.
Restrictions: None
See also: innum, otnum, cotnum
Example: char* chex="AF1298065BFE4C96DB723A";
.
IOBASE=16;
strcpy(IBUFF,chex);
cinnum(x,stdin);
This will input the large hex number chex into the
big variable x.
IOBASE=256;
INPLEN=25;
cinnum(x,fp);
This will input 25 bytes from the file associated with
fp, and convert them into a big positive number x.
Function: int compare(x,y) compare
big x,y;
Module: bncore.c
Description: Compares two big numbers.
Parameters: Two big numbers x and y.
Return value: Returns +1 if x>y, returns 0 if x=y, returns -1 if x<y.
Restrictions: None
See also: fcomp
Function: void convert(n,x) convert
int n;
big x;
Module: bncore.c
Description: Convert an integer number to big number format.
Parameters: An integer n and a big number x.
Return value: None
Restrictions: None
See also: fconv, lconv, dconv
Function: void copy(x,y) copy
flash x,y;
Module: bncore.c
Description: Copies a big or flash number to another.
Parameters: Two big or flash numbers x and y. On exit y=x. Note
that if x and y are the same variable, no operation is
performed.
Return value: None
Restrictions: None
See also: -
Function: int cotnum(x,f) cotnum
flash x;
FILE *f;
Module: bnio2.c
Description: Output a big or flash number to the screen or to a file,
using as number base the value currently assigned to the
global variable IOBASE. A flash number will be converted
to radix-point representation if the global variable
POINT=ON. Otherwise it will be output as a fraction. If
the global variable WRAP=ON, numbers too large to be
represented on one line are 'wrapped around' onto the
next line.
Parameters: A big/flash number x and a file descriptor f. If f is
stdout then output will be to the screen, otherwise to
the file opened with descriptor f.
Return value: Number of output characters.
Restrictions: None
See also: innum, cinnum, otnum.
Example: IOBASE=256
cotnum(x,fp);
This outputs x (in pure binary) as a byte array, to the
file associated with fp.
Function: void dconv(d,x) dconv
double d;
flash x;
Module: bnflash.c
Description: Converts a double to flash format.
Parameters: A double d and a flash variable x. On exit x will
contain the flash equivalent of d.
Return value: None
Restrictions: None
See also: fdsize, lconv, convert,fconv
Function: void decr(x,n,z) decr
big x,z;
int n;
Module: bnarth0.c
Description: Decrement a big number by an integer amount.
Parameters: Big numbers x and z, and integer n. On exit z=x-n.
Return value: None
Restrictions: None
See also: add, subtract, incr.
Example: decr(x,2,x); /* This decrements x by 2. */
Function: void denom(x,y) denom
flash x;
big y;
Module: bncore.c
Description: Extract the denominator of a flash number into a big number
Parameters: A flash number x and a big number y. On exit y will contain
the denominator of x.
Return value: None
Restrictions: None
See also: numer, fpack.
Function: void divide(x,y,z) divide
big x,y,z;
Module: bnarth2.c
Description: Divides one big number by another.
Parameters: Three big numbers x, y and z. On exit z=x/y; x=x mod y.
The quotient only is returned if x and z are the same, the
remainder only if y and z are the same.
Return value: None
Restrictions: Parameters x and y must be different, and y must be
non-zero.
See also: multiply, mad
Example: divide(x,y,y);
This sets x equal to the remainder when x is divided by y.
The quotient is not returned.
Function: void expb2(x,n) expb2
big x;
int n;
Module: bnarth3.c
Description: Calculates 2 to the power of an integer.
Parameters: A big number x and an integer n. On exit x=2^n.
Return value: None
Restrictions: None
See also: logb2
Example: expb2(x,216091);
decr(x,1,x);
cotnum(x,stdout);
This calculates and prints out the largest known prime
number (on a true 32-bit computer).
Function: int exsign(x) exsign
flash x;
Module: bncore.c
Description: Extracts the sign of a big/flash number.
Parameters: A big/flash number x.
Return value: The sign of x, i.e. -1 if x is negative, +1 if x is zero
or positive.
Restrictions: None
See also: insign
Function: void facos(x,y) facos
flash x,y;
Module: bnflsh3.c
Description: Calculates arc-cosine of a flash number, using fasin.
Parameters: Two flash numbers x and y. On exit y=acos(x).
Return value: None
Restrictions: |x| must be less than or equal to 1.
See also: fatan, fasin
Function: void facosh(x,y) facosh
flash x,y;
Module: bnflsh4.c
Description: Calculates hyperbolic arc-cosine of a flash number.
Parameters: Two flash numbers x and y. On exit y=acosh(x).
Return value: None
Restrictions: |x| must be greater than or equal to 1.
See also: fatanh, fasinh
Function: void fadd(x,y,z) fadd
flash x,y,z;
Module: bnflash.c
Description: Add two flash numbers.
Parameters: Three flash numbers x, y and z. On exit z=x+y.
Return value: None
Restrictions: None
See also: fsub, fincr
Function: void fasin(x,y) fasin
flash x,y;
Module: bnflsh3.c
Description: Calculates arc-sin of a flash number, using fatan.
Parameters: Two flash numbers x and y. On exit y=asin(x).
Return value: None
Restrictions: |x| must be less than or equal to 1.
See also: facos, fatan
Function: void fasinh(x,y) fasinh
flash x,y;
Module: bnflsh4.c
Description: Calculates hyperbolic arc-sin of a flash number.
Parameters: Two flash numbers x and y. On exit y=asinh(x).
Return value: None
Restrictions: None
See also: facosh, fatanh
Function: void fatan(x,y) fatan
flash x,y;
Module: bnflsh3.c
Desciption: Calculates the arc-tangent of a flash number, using
O(n^2.5) method based on Newton's iteration.
Parameters: Two flash numbers x and y. On exit y=atan(x).
Return value: None
Restrictions: None
See also: fasin, facos
Function: void fatanh(x,y) fatanh
flash x,y;
Module: bnflsh4.c
Desciption: Calculates the hyperbolic arc-tangent of a flash number.
Parameters: Two flash numbers x and y. On exit y=atanh(x).
Return value: None
Restrictions: x.x must be less than 1
See also: fasinh, facosh
Function: int fcomp(x,y) fcomp
flash x,y;
Module: bnflash.c
Description: Compare two flash numbers.
Parameters: Two flash numbers x and y.
Return value: Returns -1 if y>x, +1 if x>y and 0 if x=y.
Restrictions: None
See also: compare
Function: void fconv(n,d,x) fconv
int n,d;
flash x;
Module: bnflash.c
Description: Convert a simple fraction to flash format.
Parameters: Integers n and d, and a flash number x. On exit x={n/d}
Return value: None
Restrictions: None
See also: convert, lconv, dconv
Function: void fcos(x,y) fcos
flash x,y;
Module: bnflsh3.c
Description: Calculates cosine of a given flash angle, using ftan.
Parameters: Two flash numbers x and y. On exit y=cos(x).
Return value: None
Restrictions: None
See also: fsin, ftan
Function: void fcosh(x,y) fcosh
flash x,y;
Module: bnflsh4.c
Description: Calculates hyperbolic cosine of a given flash angle.
Parameters: Two flash numbers x and y. On exit y=cosh(x).
Return value: None
Restrictions: None
See also: fsinh, ftanh
Function: void fdiv(x,y,z) fdiv
flash x,y,z;
Module: bnflash.c
Description: Divides two flash numbers.
Parameters: Three big numbers x,y and z. on exit z=x/y.
Return value: None
Restrictions: None
See also: fmul, fpmul
Function: double fdsize(x) fdsize
flash x;
Module: bndouble.c
Description: Converts a flash number to double format.
Parameters: A flash number x.
Return value: The value of the parameter x as a double.
Restrictions: The value of x must be less than BIGGEST. See mirdef.h
See also: dconv
Function: void fexp(x,y) fexp
flash x,y;
Module: bnflsh2.c
Description: Calculates the exponential of a flash number using
O(n^2.5) method.
Parameters: Two flash numbers x and y. On exit y=exp(x).
Return value: None
Restrictions: None
See also: flog, fpowf
Function: void fincr(x,n,d,y) fincr
big x,y;
int n,d;
Module: bnflash.c
Description: Add a simple fraction to a flash number.
Parameters: Two flash numbers x and y, and two integers n and d.
On exit y=x+{n/d}.
Return value: None
Restrictions: None
See also: fadd, fsub
Example: fincr(x,-2,3,x);
This subtracts two-thirds from the value of x.
Function: void flog(x,y) flog
flash x,y;
Module: bnflsh2.c
Description: Calculates the natural log of a flash number using
O(n^2.5) method.
Parameters: Two flash numbers x and y. On exit y=log(x).
Return value: None
Restrictions: None
See also: fexp, fpowf
Function: void flop(x,y,op,z) flop
flash x,y,z;
int *op;
Module: bnflash.c
Description: Perform primitive flash operation. Used internally.
Parameters: Three flash numbers x,y and z. On exit z=Fn(x,y),
where the function performed depends on the
parameter op. See source listing comments for more
details.
Restrictions: None
Return value: None
See also: fadd, fsub, fmul, fdiv
Function: void fmul(x,y,z) fmul
flash x,y,z;
Module: bnflash.c
Description: Multiply two flash numbers.
Parameters: Three flash numbers x,y and z. On exit z=x*y.
Return value: None
Restrictions: None
See also: fpmul, fdiv
Function: void fpack(n,d,x) fpack
flash x;
big n,d;
Module: bncore.c
Description: Forms a flash number from big numerator and denominator.
Parameters: A flash number x and two big numbers n and d. On exit
x={n/d}.
Return value: None
Restrictions: The denominator must be non-zero. Flash variable x and big
variable d must be distinct. The resulting flash variable
must not be too big for the representation.
See also: numer, denom.
Function: void fpi(x) fpi
flash x;
Module: bnpi.c
Description: Calculates pi using Guass-Legendre O(n².log(n)) method.
Note that on subsequent calls to this routine, pi is
immediately available, as it is stored internally.
Parameters: A flash number x. On exit x=pi.
Return value: None
Restrictions: None.
See also: fsin, fcos, ftan
Function: void fpower(x,n,y) fpower
flash x,y;
int n;
Module: bnflsh1.c
Description: Raises a flash number to an integer power.
Parameters: Flash variables x and y, and an integer n. On exit
y=x^n.
Return value: None
Restrictions: None
See also: froot
Function: void fpmul(x,n,d,y) fpmul
flash x,y;
int n,d;
Module: bnflash.c
Description: Multiplies a flash number by a simple fraction.
Parameters: Two flash numbers x and y, and two integers n and d.
On exit y=x.{n/d}
Return value: None
Restrictions: None
See also: fmul, fdiv
Function: void fpowf(x,y,z) fpowf
flash x,y,z;
Module: bnflsh2.c
Description: Raises a flash number to a flash power.
Parameters: Three flash numbers x, y and z. On exit z=x^y
Return value: None
Restrictions: None
See also: fexp, flog
Function: void frand(x) frand
flash x;
Module: bnrand.c
Description: Generates a random flash number.
Parameters: A big number x. On exit x contains a flash random number
in the range 0<x<1.
Return value: None
Restrictions: None
See also: bigrand, bigdig
Function: void frecip(x,y) frecip
flash x,y;
Module: bnflash.c
Description: Calculates reciprocal of a flash number.
Parameters: Two flash numbers x and y. On exit y=1/x.
Return value: None
Restrictions: None
See also: fdiv, fmul
Function: bool froot(x,m,y) froot
flash x,y;
int m;
Module: bnflsh1.c
Description: Calculates m-th root of a flash number using Newton's
O(n²) method.
Parameters: Flash numbers x and y, and an integer m. On exit y is
the m-th root of x.
Return value: TRUE for exact root, otherwise FALSE
Restrictions: None
See also: fpower
Function: void fsin(x,y) fsin
flash x,y;
Module: bnflsh3.c
Description: Calculates sine of a given flash angle. Uses ftan.
Parameters: Two flash numbers x and y. On exit y=sin(x).
Return value: None
Restrictions: None
See also: fcos, ftan
Function: void fsinh(x,y) fsinh
flash x,y;
Module: bnflsh4.c
Description: Calculates hyperbolic sine of a given flash angle.
Parameters: Two flash numbers x and y. On exit y=sinh(x).
Return value: None
Restrictions: None
See also: fcosh, ftanh
Function: void fsub(x,y,z) fsub
flash x,y,z;
Module: bnflash.c
Description: Subtract two flash numbers.
Parameters: Three flash numbers x,y and z. On exit z=x-y.
Return value: None
Restrictions: None
See also: fadd, fincr
Function: void ftan(x,y) ftan
flash x,y;
Module: bnflsh3.c
Description: Calculates the tan of a given flash angle, using an
O(n²√n) method.
Parameters: Two flash numbers x and y. On exit y=tan(x).
Return value: None
Restrictions: None
See also: fsin, fcos
Function: void ftanh(x,y) ftanh
flash x,y;
Module: bnflsh4.c
Description: Calculates the hyperbolic tan of a given flash angle.
Parameters: Two flash numbers x and y. On exit y=tanh(x).
Return value: None
Restrictions: None
See also: fsinh, fcosh
Function: void ftrunc(x,y,z) ftrunc
flash x,z;
big y;
Module: bnflash.c
Description: Seperates a flash number to a big number and a flash
remainder.
Parameters: Flash numbers x and z, and a big number y.
On exit y=int(x) and z = x-y (the fractional remainder).
if y is the same as z, only int(x) is returned.
Return value: None
Restrictions: None
Function: int gcd(x,y,z) gcd
big x,y,z;
Module: bngcd.c
Description: Calculates the Greatest Common Divisor of two big numbers.
Parameters: Three big numbers x, y and z. On exit z=gcd(x,y)
Return value: GCD as integer, if possible, otherwise TOOBIG
Restrictions: None
See also: xgcd, round
Function: int getdig(x,i) getdig
big x;
int i;
Module: bncore.c
Description: Extracts a digit from a big number.
Parameters: A big number x, and the required digit i.
Return value: The value of the requested digit.
Restrictions: Returns rubbish if required digit does not exist.
See also: putdig, numdig.
Function: int *gprime(n) *gprime
int n;
Module: bnsmall.c
Description: Generates an array of all prime numbers up to a certain
limit, terminated by zero.
Parameters: A positive integer n indicating the maximum prime
number to be generated, or a negative integer
indicating that (-n) primes are to be generated.
Return value: A pointer to the prime number array.
Restrictions: None
See also: -
Function: int igcd(x,y) igcd
int x,y;
Module: bncore.c
Description: Calculates the Greatest Common Divisor of two integers
using Euclids Method.
Parameters: Two integers x and y
Return value: The GCD of x and y
See also: gcd
Function: void incr(x,n,z) incr
big x,z;
int n;
Module: bnarth0.c
Description: Increment a big variable.
Parameters: Big numbers x and z, and an integer n. On exit z=x+n.
Return value: None
Restrictions: None
See also: add, subtract, decr.
Function: int innum(x,f) innum
flash x;
FILE *f;
Module: bnio1.c
Description: Inputs a big or flash number from a file, the keyboard
or a string. Flash numbers can be entered using either
a slash '/' to indicate numerator and denominator, or
with a radix point.
Parameters: A big/flash number x and a file descriptor f. For input
from the keyboard specify f as stdin, otherwise as the
descriptor of some other opened file. To input from a
string, copy the string to the global character array
IBUFF before calling innum. In this case the file
descriptor will be ignored, and input taken directly from
IBUFF.
Return value: The number of characters input.
Restrictions: The number base specified in mirsys must be less than
or equal to 256. If not use cinnum instead.
See also: otnum, cinnum, cotnum.
Function: void insign(s,x) insign
int s;
flash x;
Module: bncore.c
Description: Forces a big/flash number to a particular sign.
Parameters: A big/flash number x, and the sign s that it is to take.
On exit x=s*abs(x).
Return value: None
Restrictions: None
See also: exsign.
Example: insign(PLUS,x); /* force x to be positive */
Function: int inverse(x,y) inverse
int x,y;
Module: bnsmall.c
Description: Calculates the inverse of an integer modulus a co-
prime integer
Parameters: An integer x and a co-prime integer y
Return value: 1/x mod y
Restrictions: Return value is unpredictable if x and y are not co-
prime
See also: igcd, sqrmp
Function: void irand(seed) irand
long seed;
Module: bncore.c
Description: Initializes random number system. Uses Knuth's subtractive
method. Long integer types are used internally to yield a
generator with maximum period.
Parameters: A long integer seed, which is used to start off the
random number generator.
Return value: None
Restrictions: None
See also: brand, bigrand, bigdig, frand.
Function: void lconv(ln,x) lconv
long n;
big x;
Module: bncore.c
Description: Converts a long integer to big number format
Parameters: A long integer ln and a big number x
Return value: None
Restrictions: None
See also: convert, fconv, dconv
Function: int logb2(x) logb2
big x;
Module: bnarth3.c
Description: Calculates the approximate integer log to the base 2 of
a big number (in fact the number of bits in it.)
Parameters: A big number x.
Return value: Number of bits in x
Restrictions: None
See also: expb2
Function: void mad(x,y,z,w,q,r) mad
big x,y,z,w,q,r;
Module: bnarth2.c
Description: Multiply add and divide big numbers. The initial product
is stored in a double-length internal variable to avoid
the possibility of overflow at this stage.
Parameters: Six big numbers x,y,z,w,q and r. On exit q=(x*y+z)/w and
r contains the remainder. If w and q are not distinct
variables then only the remainder is returned; if q and r
are not distinct then only the quotient is returned. The
addition of z is not done if x and z (or y and z) are the
same.
Return value: None
Restrictions: Parameters w and r must be distinct. The value of w must
not be zero.
See also: multiply, divide.
Example: mad(x,x,x,w,x,x);
This sets x=(x*x)/w. The remainder is not returned.
Function: void mirsys(nd,nb) mirsys
int nd,nb;
Module: bncore.c
Description: Initialize the MIRACL system as described below. Must
be called before attempting to use any other MIRACL
routines.
(1) The error tracing mechanism is initialised.
(2) the number of computer words to use for each
big/flash number is calculated from nd and nb.
(3) Sixteen big work variables (four of them double
length) are initialised.
(4) Certain global variables are given default initial
values.
(5) The random number generator is started by calling
irand(0L).
Parameters: The number of digits nd to use for each big/flash
variable and the number base nb. If nd is negative it
is taken as indicating the size of big/flash numbers
in 8-bit bytes.
Return value: None
Restrictions: The number base nb must be greater than 1 and less
than or equal to MAXBASE. The number of digits nd must
be less than a certain maximum, depending on the value
of BTS. (See mirdef.h).
See also: irand, mirvar.
Example: mirsys(500,10);
This initializes the MIRACL system to use 500 decimal
digits for each big or flash number.
Function: flash mirvar(iv) mirvar
int iv;
Module: bncore.c
Description: Initialises a big/flash variable by reserving a suitable
number of memory locations for it.
Parameters: An integer initial value for the big/flash number.
Return Value: A pointer to the reserved locations.
Restrictions: None
See also: mirsys
Example: flash x;
x=mirvar(1);
Creates a flash variable x=1.
Function: void multiply(x,y,z) multiply
big x,y,z;
Module: bnarth2.c
Description: Multiplies two big numbers
Parameters: Three big numbers x,y and z. On exit z=x.y
Return value: None
Restrictions: None
See also: divide, mad
Function: void negate(x,y) negate
flash x,y;
Module: bncore.c
Description: Negates a big/flash number.
Parameters: Two big/flash numbers x and y. On exit y=-x.
Return value: None
Restrictions: None. Note that negate(x,x) is valid and sets x=-x.
See also: absol.
Function: int numdig(x) numdig
big x;
Module: bncore.c
Description: Calculates the number of digits in a big number.
Parameters: A big number x.
Return value: The number of digits in x.
Restrictions: None
See also: getdig, putdig.
Function: void numer(x,y) numer
flash x;
big y;
Module: bncore.c
Description: Extract the numerator of a flash number.
Parameters: A flash number x and a big number y. On exit y will contain
the numerator of x.
Return value: None
Restrictions: None
See also: denom, fpack.
Function: void nxprime(w,x) nxprime
big w,x;
Module: bnprime.c
Description: Find next prime number.
Parameters: Two big numbers w and x. On exit x contains the next prime
number greater than w.
Return value: None
Restrictions: None
See also: prime
Function: int otnum(x,f) otnum
flash x;
FILE *f;
Module: bnio1.c
Description: Output a big or flash number to the screen or to a file.
If STROUT=TRUE output is redirected to the global string
OBUFF[]. A flash number will be converted to radix-point
representation if the global variable POINT=ON. Otherwise
it will be output as a fraction. If the global variable
WRAP=ON numbers too large to be represented on one line
are 'wrapped around' onto the next line.
Parameters: A big/flash number x and a file descriptor f. If f is
stdout then output will be to the screen, otherwise to
the file opened with descriptor f.
Return value: Number of output characters.
Restrictions: The number base specified in mirsys must be less than or
equal to 256. If not, use cotnum instead.
See also: innum, cinnum, cotnum.
Function: void power(x,n,z,w) power
int n;
big x,z,w;
Module: bnarth3.c
Description: Raise a big number to an integer power.
Parameters: Two big numbers x and z, and an integer n. On exit w=x^n
If w and z are distinct, then w=x^n mod z
Return value: None.
Restrictions: The value of n must be positive
See also: powmod, root
Function: void powmod(x,y,z,w) powmod
big x,y,z,w;
Module: bnarth3.c
Description: Raise a big number to a big power modulus another big
number.
Parameters: Four big numbers x,y,z and w. On exit w=x^y mod z.
Return value: None
Restrictions: The value of y must be positive. The parameters w and z
must be distinct.
See also: power, root
Function: void premult(x,n,z) premult
int n;
big x,z;
Module: bnarth1.c
Description: Multiplies a big number by an integer
Parameters: Two big numbers x and z, and an integer n. On exit z=n.x
Return value: None
Restrictions: None
See also: subdiv
Function: bool prime(x) prime
big x;
Module: bnprime.c
Description: Tests whether or not a big number is prime using a
probabilistic primality test. The number is assumed
to be prime if it passes this test NTRY times, where
NTRY is a global variable with a default initialisation
in routine mirsys.
Parameters: A big number x.
Return value: Returns the boolean value TRUE if x is (almost certainly)
prime, otherwise FALSE.
Restrictions: None
See also: nxprime, strongp
Function: void putdig(n,x,i) putdig
big x;
int i,n;
Module: bncore.c
Description: Set a digit of a big number to a given value
Parameters: A big number x, a digit number i, and its new value n.
Return value: None
Restrictions: The digit indicated must exist.
See also: getdig, numdig.
Function: bool root(x,n,z) root
big x,z;
int n;
Module: bnarth3.c
Description: Extracts lower approximation to a root of a big number.
Parameters: Two big numbers x and z, and an integer n. On exit
z=x^(1/n).
Return value: Returns the boolean value TRUE if the root found is exact,
otherwise returns FALSE.
Restrictions: The value of n must be positive. If x is negative, then n
must be odd.
See also: power, powmod
Function: void round(n,d,x) round
flash x;
big n,d;
Module: bnround.c
Description: Forms a rounded flash number from big numerator and
denominator. If rounding takes place the global variable
EXACT is set to FALSE. EXACT is initialised to TRUE in
routine mirsys. This routine is used internally by most
of the other flash arithmetic routines.
Parameters: A flash number x and two big numbers n and d. On exit
x=R{n/d}, that is the flash number {n/d} rounded if
necessary to fit the representation.
Return value: None
Restrictions: The denominator must be non-zero.
See also: gcd, xgcd, fpack.
Function: int size(x) size
big x;
Module: bncore.c
Description: Tries to convert big number to simple integer format.
Parameters: A big number x.
Return value: The value of x as an integer. If this is not possible
(because x is too big) it returns the value plus or minus
TOOBIG.
Restrictions: None
See also: -
Function: int smul(x,y,z) smul
int x,y,z;
Module: bnsmall.c
Description: Multiplies two integers mod a third
Parameters: Integers x, y and z
Return value: (x.y) mod z
Restrictions: None
See also: spmd
Function: int spmd(x,y,z) spmd
int x,y,z;
Module: bnsmall.c
Description: Raises an integer to an integer power modulus a third
Parameters: Integers x, y, and z
Return value: x^y mod z
Restrictions: None
See also: smul
Function: int sqrmp(x,y) sqrmp
int x,y;
Module: bnsmall.c
Description: Calculates the square root of an integer mod an integer
prime number
Parameters: An integer x and a prime number y
Return value: x^(1/2) mod y, or 0 if root does not exist
Restrictions: Return value unpredictable if y is not prime
See also: inverse
Function: void strongp(p,n) strongp
big p;
int n;
Module: bnprime.c
Description: Generate a 'strong' prime number. Useful for Public Key
Cryptography programs.
Parameters: A big number p and an integer n. On exit p will contain
a 'strong' prime number at least n decimal digits long.
Return value: None
Restrictions: None. The prime p may be rather more than n digits long.
See also: prime, nxprime
Function: int subdiv(x,n,z) subdiv
int n;
big x,z;
Module: bnarth1.c
Description: Divide a big number by an integer.
Parameters: Two big numbers x and z, and an integer n. On exit z=x/n.
Return value: The integer remainder.
Restrictions: The value of n must not be zero.
See also: premult
Function: void subtract(x,y,z) subtract
big x,y,z;
Module: bnarth0.c
Description: Subtracts two big numbers.
Parameters: Three big numbers x, y and z. On exit z=x-y.
Return value: None
Restrictions: None
See Also: add, incr, decr.
Function: int xgcd(x,y,xd,yd,z) xgcd
big x,y,xd,yd,z;
Module: bnxgcd.c
Description: Calculates extended Greatest Common Divisor of two big
numbers. Can also be used to calculate modular inverses.
Note that this routine is about 8 times slower than a
'mad' operation on numbers of similar size.
Parameters: Five big numbers x,y,xd,yd and z.
On exit z=gcd(x,y)=x.xd+y.yd
Return value: GCD as integer, if possible, otherwise TOOBIG
Restrictions: If xd and yd are not distinct, only xd is returned. The
GCD is only returned if z distinct from both xd and yd.
See also: gcd, round
Example: xgcd(x,p,x,x,x); /* x = 1/x mod p (p is prime) */
Function: void zero(x) zero
flash x;
Module: bncore.c
Description: Sets a big or flash number to zero
Parameters: A big or flash number x.
Return value: None
Restrictions: None
See also: -
Appendix IV - Example programs
Note: The programs described here are of an experimental nature, and
in many cases are not completely 'finished off'. For further
information read the comments associated with the appropriate source
file.
Program: hail.c hail.c
This program allows you to investigate so-called hailstone numbers,
as described by Fred Gruenberger in 'Computer Recreations',
Scientific American, April 1984. The procedure is simple. Starting
with any number apply the following rules:
(a) If it is odd, multiply it by 3 and add 1.
(b) If it is even, divide it by 2.
(c) Repeat the process, until the number becomes equal to 1, in which
case stop.
It would appear that for any initial number this process always
eventually terminates, although it has not been proved that this must
happen, or that the process can not get stuck in an infinite loop.
What goes up, it seems, must come down. Try the program for an
initial value of 27. Then try it using much bigger numbers.
Program: palin.c palin.c
This programs allows you to investigate palindromic reversals. See
'Computer Recreations' by Fred Gruenberger, Scientific American,
April 1984. A palindromic number is one which reads the same in both
directions. Start with any number and apply the following rules.
(a) Add the number to the number obtained by reversing the order of
the digits. Make this the new number.
(b) Stop the process when the new number is palindromic.
It appears that for most initial numbers this process quickly
terminates. Try it for 89. Then try it for 196.
Program: brute.c brute.c
This program attempts to factorise a number by brute force division,
using a table of small prime numbers. When attempting a difficult
factorisation it makes sense to try this approach first.
Use this program to factorise 12345678901234567890. Then try it on
bigger random numbers.
Program: brent.c brent.c
This program attempts to factorise a number using the Brent-Pollard
method. This method is faster at finding larger factors than the
simple-minded brute force approach. However it will not always
succeed, even for very simple factorisations. Use it to factorise
R17, that is 11111111111111111 (seventeen ones). Then try it on larger
numbers that would not yield to the brute force approach.
Program: pollard.c pollard.c
Another factoring program, which implements Pollard's (p-1) method,
specialises in quickly finding a factor p of a number N for which
(p-1) has itself only small factors. Phase 1 of this method will work
if all these small factors are less than LIMIT1. If Phase 1 fails
then Phase 2 searches for just one final larger factor less than
LIMIT2. The constants LIMIT1 and LIMIT2 are set inside the program.
Program: williams.c williams.c
This program is similar to Pollards method, but can find a factor p
of N for which (p+1) has only small factors. Again two phases are
used. In fact this method is sometimes a (p+1) method, and sometimes
a (p-1) method, so several attempts are made to find the (p+1)
condition. The algorithm is rather more complex than that used in
Pollards method, and is somewhat slower.
Program: lenstra.c lenstra.c
Recently Lenstra has discovered a new method of factorisation,
generically similar to the Pollard and Williams methods, but
potentially much more powerful. It works by randomly generating an
Elliptic Curve, which can then be used to find a factor p of N, for
which p+1-d has only small factors, where d depends on the particular
curve chosen. If one curve fails then another can be tried, an option
not possible with the Pollard/Williams methods. Again this is a two
phase method, and although it has very good asymptotic behaviour, it
is much slower than the pollard/williams for each iteration.
Program: qsieve.c qsieve.c
This is a very sophisticated Pomerance-Silverman-Montgomery
factoring program. Its speciality is factoring all numbers (up to
about sixty digits long), irrespective of the size of the factors. If
the number to be factored is N, then the program actually works with
a number k.N, where k is a small Knuth-Schroepel multiplier. The
program itself works out the best value of k to use. Internally, the
program uses a 'factor base' of small primes. The larger the number,
the bigger will be this factor base. The program works by
accumulating information from a number of simpler factorisations. As
it progresses with these it prints out 'working...n'. When it thinks
it has enough information it prints out 'trying', but these tries
may be premature and may not succeed. The program will always
terminate before the number n in 'working...n' reaches the size of
the factor base.
This program uses much more memory than any of the other example
programs, particularly when factoring bigger numbers. The amount of
memory that the program can take is limited by the values defined for
MEM and MLF at the beginning of the program. These should be
increased if possible, or reduced if your computer has insufficient
memory.
Use qsieve to factor 10000000000000000000000000000000009 (thirty-
five digits).
Program: mersenne.c mersenne.c
This program generates all prime numbers of the form 2^n-1. The
largest known primes have always been of this form because of the
efficiency of this Lucas-Lehmer test.
Program: rsakey.c rsakey.c
Public Key Cryptography is a two key encipherment system with the
very desirable feature that the encoding key can be made publicly
available, without weakening the strength of the cipher. This program
generates the 'public' encoding key and 'private' decoding key for
the original Rivest-Shamir-Adleman PKS system. These keys can take a
long time to generate, as they are formed from very large prime
numbers, which must be generated carefully for maximum security.
The program prompts for 'Minimum size of keys in decimal digits'. The
security of the system depends on the difficulty of factoring the
encoding 'public' key, which is formed from two large primes. The
largest numbers which can be routinely factored using the most
powerful computers are 100 digits long (1988). So a minimum size of
120 gives adequate security (for now!)
After this program has run, the two keys are created in files
PUBLIC.KEY and PRIVATE.KEY.
Program: encode.c encode.c
Messages or files may be encoded with this program, which uses the
'public' encoding key from the file PUBLIC.KEY, generated by the
program 'rsakey', which must have been run prior to using this
program. When run the user is prompted for a file to encipher.
Either give the name of a text file, or press return to enter a
message directly from the keyboard. In the former case the encoded
output is sent to a file with the same name, but with the extension
.RSA. In the latter case you are prompted for an output filename,
which must be given. Text entered from the keyboard must be
terminated by a CONTROL Z (end-of-file). Type out the encoded file
and be impressed by how indecipherable it looks
Program: decode.c decode.c
Messages or files encoded using the RSA system may be decoded using
this program, which uses the 'private' decoding key from the file
PRIVATE.KEY generated by the program 'rsakey' which must have been
run at some stage prior to using this program.
When run, the user is prompted for the name of the file to be
decoded. Type in the filename (without an extension - the program
will assume the extension .RSA) and press return. Then the user is
asked for an output filename. Either supply a filename or press
return, in which case the decoded output will be sent straight to the
screen. A problem with the RSA system becomes immediately apparent -
decoding takes a very long time! This is particularly true for larger
key sizes and long messages.
Program: okakey.c okakey.c
This program generates 'public' and 'private' keys for use with the
Okamoto PKS system. As with the RSA system the keys are generated
from large prime numbers carefully selected for certain properties,
so this program takes a long time to run. A key length of 150 is
adequate. The two keys are generated into files PUBLIC.KEY and
PRIVATE.KEY.
Program: enciph.c enciph.c
This program works in an identical fashion to the program 'encode',
although in this case the encoded file produced will be 1.35 times
bigger than the original.
Program: deciph.c deciph.c
This program works in an identical fashion to the program 'decode'.
However it has the advantage that it runs much more quickly.
Note : The original version of this program was 'cracked' by the
redoubtable Shamir. Okamoto (Electronics letters 30th July 1987, Vol.
23 No. 16 pp814-815) responded with a modified algorithm which
appears to be resistant to Shamirs method of attack. This improved
version has now been implemented. Over to you Shamir...
Program: pi.c pi.c
This program calculates pi using a Guass-Legendre O(n².log(n))
method. (Is there a more efficient way to calculate pi for moderate
n?) The greater the precision specified in the call to routine
'mirsys', the more decimal place there will be in the answer (and the
longer it will take).
Program: roots.c roots.c
This program calculates the n-th root of an input number, using
Newtons method. Try it to calculate the square root of two. Again the
accuracy obtained depends on the size of the flash variables,
specified in routine 'mirsys'. The tendency of flash arithmetic to
prefer simple numbers can be illustrated by requesting, say, the
square root of 7. The program calculates this value and then squares
it, to give 7 again exactly. On your pocket calculator the same
result will only be obtained if clever use is made of extra (hidden)
guard digits.
Program: hilbert.c hilbert.c
Traditionally the inversion of 'Hilbert' matrices is regarded as a
tough test for any system of arithmetic. This programs solves the set
of linear equations H.x = b, where H is a Hilbert matrix and b is the
vector [1,1,1,1,....1], using the classical Guassian Elimination
method.
Program: sample.c sample.c
This program is the same as that used by Brent (1978) to demonstrate
some of the capabilities of his Fortran Multiprecision arithmetic
package. It calculates pi, exp(pi*sqrt(163/9)) and exp(pi*sqrt(163)).
Program: ratcalc.c ratcalc.c
As a comprehensive and useful demonstration of flash arithmetic this
program simulates a standard full-function scientific calculator. Its
unique feature (besides its 36-digit accuracy) is its ability to work
directly with fractions, and to handle mixed calculations involving
both fractions and decimals. By using this program the user will
quickly get a feel for flash arithmetic and its capabilities. Note
that this program contains some non-portable code (screen handling
routines) that must be tailored to each individual computer/terminal
combination.