FORM 4.3
|
Go to the source code of this file.
Macros | |
#define | GCDMAX 3 |
#define | NEWTRICK 1 |
#define | COPYLONG(x1, nx1, x2, nx2) { int i; for(i=0;i<ABS(nx2);i++)x1[i]=x2[i];nx1=nx2; } |
#define | WARMUP 6 |
Functions | |
VOID | Pack (UWORD *a, WORD *na, UWORD *b, WORD nb) |
VOID | UnPack (UWORD *a, WORD na, WORD *denom, WORD *numer) |
WORD | Mully (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb) |
WORD | Divvy (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb) |
WORD | AddRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | MulRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | DivRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | Simplify (PHEAD UWORD *a, WORD *na, UWORD *b, WORD *nb) |
WORD | AccumGCD (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb) |
int | TakeRatRoot (UWORD *a, WORD *n, WORD power) |
WORD | AddLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | AddPLon (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
VOID | SubPLon (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | MulLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | BigLong (UWORD *a, WORD na, UWORD *b, WORD nb) |
WORD | DivLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc, UWORD *d, WORD *nd) |
WORD | RaisPow (PHEAD UWORD *a, WORD *na, UWORD b) |
VOID | RaisPowCached (PHEAD WORD x, WORD n, UWORD **c, WORD *nc) |
WORD | RaisPowMod (WORD x, WORD n, WORD m) |
int | NormalModulus (UWORD *a, WORD *na) |
int | MakeInverses () |
int | GetModInverses (WORD m1, WORD m2, WORD *im1, WORD *im2) |
int | GetLongModInverses (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *ia, WORD *nia, UWORD *ib, WORD *nib) |
WORD | Product (UWORD *a, WORD *na, WORD b) |
UWORD | Quotient (UWORD *a, WORD *na, WORD b) |
WORD | Remain10 (UWORD *a, WORD *na) |
WORD | Remain4 (UWORD *a, WORD *na) |
VOID | PrtLong (UWORD *a, WORD na, UBYTE *s) |
WORD | GetLong (UBYTE *s, UWORD *a, WORD *na) |
WORD | GcdLong (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
WORD | GetBinom (UWORD *a, WORD *na, WORD i1, WORD i2) |
WORD | LcmLong (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc) |
int | TakeLongRoot (UWORD *a, WORD *n, WORD power) |
int | MakeRational (WORD a, WORD m, WORD *b, WORD *c) |
int | MakeLongRational (PHEAD UWORD *a, WORD na, UWORD *m, WORD nm, UWORD *b, WORD *nb) |
WORD | CompCoef (WORD *term1, WORD *term2) |
WORD | Modulus (WORD *term) |
WORD | TakeModulus (UWORD *a, WORD *na, UWORD *cmodvec, WORD ncmod, WORD par) |
WORD | TakeNormalModulus (UWORD *a, WORD *na, UWORD *c, WORD nc, WORD par) |
WORD | MakeModTable () |
int | Factorial (PHEAD WORD n, UWORD *a, WORD *na) |
int | Bernoulli (WORD n, UWORD *a, WORD *na) |
WORD | NextPrime (PHEAD WORD num) |
WORD | Moebius (PHEAD WORD nn) |
void | iniwranf (PHEAD0) |
UWORD | wranf (PHEAD0) |
UWORD | iranf (PHEAD UWORD imax) |
UBYTE * | PreRandom (UBYTE *s) |
This file contains the numerical routines. The arithmetic in FORM is normally over the rational numbers. Hence there are routines for dealing with integers and with rational of 'arbitrary precision' (within limits) There are also routines for that calculus modulus an integer. In addition there are the routines for factorials and bernoulli numbers. The random number function is currently only for internal purposes.
Definition in file reken.c.
#define COPYLONG | ( | x1, | |
nx1, | |||
x2, | |||
nx2 | |||
) | { int i; for(i=0;i<ABS(nx2);i++)x1[i]=x2[i];nx1=nx2; } |
VOID UnPack | ( | UWORD * | a, |
WORD | na, | ||
WORD * | denom, | ||
WORD * | numer | ||
) |
WORD Mully | ( | PHEAD UWORD * | a, |
WORD * | na, | ||
UWORD * | b, | ||
WORD | nb | ||
) |
WORD Divvy | ( | PHEAD UWORD * | a, |
WORD * | na, | ||
UWORD * | b, | ||
WORD | nb | ||
) |
WORD AddRat | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD MulRat | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD DivRat | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD Simplify | ( | PHEAD UWORD * | a, |
WORD * | na, | ||
UWORD * | b, | ||
WORD * | nb | ||
) |
WORD AccumGCD | ( | PHEAD UWORD * | a, |
WORD * | na, | ||
UWORD * | b, | ||
WORD | nb | ||
) |
WORD AddLong | ( | UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD AddPLon | ( | UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
VOID SubPLon | ( | UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD MulLong | ( | UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD DivLong | ( | UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc, | ||
UWORD * | d, | ||
WORD * | nd | ||
) |
VOID RaisPowCached | ( | PHEAD WORD | x, |
WORD | n, | ||
UWORD ** | c, | ||
WORD * | nc | ||
) |
Computes power x^n and caches the value
Calculates the power x^n and stores the results for caching purposes. The pointer c (i.e., the pointer, and not what it points to) is overwritten. What it points to should not be overwritten in the calling function.
Definition at line 1286 of file reken.c.
Referenced by poly::divmod_heap(), poly::divmod_univar(), and poly::mul_heap().
int NormalModulus | ( | UWORD * | a, |
WORD * | na | ||
) |
Brings a modular representation in the range -p/2 to +p/2 The return value tells whether anything was done. Routine made in the general modulus revamp of July 2008 (JV).
Definition at line 1393 of file reken.c.
Referenced by AddCoef(), and MergePatches().
int MakeInverses | ( | ) |
Makes a table of inverses in modular calculus The modulus is in AC.cmod and AC.ncmod One should notice that the table of inverses can only be made if the modulus fits inside a single FORM word. Otherwise the table lookup becomes too difficult and the table too long.
Definition at line 1430 of file reken.c.
References GetModInverses().
int GetModInverses | ( | WORD | m1, |
WORD | m2, | ||
WORD * | im1, | ||
WORD * | im2 | ||
) |
Input m1 and m2, which are relative prime. determines a*m1+b*m2 = 1 (and 1 is the gcd of m1 and m2) then a*m1 = 1 mod m2 and hence im1 = a. and b*m2 = 1 mod m1 and hence im2 = b. Set m1 = 0*m1+1*m2 = a1*m1+b1*m2 m2 = 1*m1+0*m2 = a2*m1+b2*m2 If everything is OK, the return value is zero
Definition at line 1466 of file reken.c.
Referenced by poly::divmod_heap(), poly::divmod_univar(), MakeDollarMod(), MakeInverses(), MakeMod(), TakeContent(), and TakeSymbolContent().
int GetLongModInverses | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | ia, | ||
WORD * | nia, | ||
UWORD * | ib, | ||
WORD * | nib | ||
) |
WORD GcdLong | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
WORD LcmLong | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | b, | ||
WORD | nb, | ||
UWORD * | c, | ||
WORD * | nc | ||
) |
int MakeLongRational | ( | PHEAD UWORD * | a, |
WORD | na, | ||
UWORD * | m, | ||
WORD | nm, | ||
UWORD * | b, | ||
WORD * | nb | ||
) |
WORD CompCoef | ( | WORD * | term1, |
WORD * | term2 | ||
) |
Routine takes a1 mod m1 and a2 mod m2 and returns a mod m1*m2 with a mod m1 = a1 and a mod m2 = a2
Chinese remainder: a%(m1*m2) = q1*m1+a1 a%(m1*m2) = q2*m2+a2 Compute n1 such that (n1*m1)m2 is one Compute n2 such that (n2*m2)m1 is one Then (a1*n2*m2+a2*n1*m1)%(m1*m2) is a%(m1*m2)
Definition at line 3037 of file reken.c.
Referenced by Compare1().
WORD TakeModulus | ( | UWORD * | a, |
WORD * | na, | ||
UWORD * | cmodvec, | ||
WORD | ncmod, | ||
WORD | par | ||
) |
WORD TakeNormalModulus | ( | UWORD * | a, |
WORD * | na, | ||
UWORD * | c, | ||
WORD | nc, | ||
WORD | par | ||
) |
WORD NextPrime | ( | PHEAD WORD | num | ) |
Gives the next prime number in the list of prime numbers.
If the list isn't long enough we expand it. For ease in ParForm and because these lists shouldn't be very big we let each worker keep its own list.
The list is cut off at MAXPOWER, because we don't want to get into trouble that the power of a variable gets larger than the prime number.