FORM 4.3
reken.c File Reference
#include "form3.h"
#include <math.h>

Go to the source code of this file.

Macros

#define GCDMAX   3
 
#define NEWTRICK   1
 
#define COPYLONG(x1, nx1, x2, 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)
 

Detailed Description

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.

Macro Definition Documentation

◆ GCDMAX

#define GCDMAX   3

Definition at line 49 of file reken.c.

◆ NEWTRICK

#define NEWTRICK   1

Definition at line 51 of file reken.c.

◆ COPYLONG

#define COPYLONG ( x1,
nx1,
x2,
nx2 )
Value:
{ int i; for(i=0;i<ABS(nx2);i++)x1[i]=x2[i];nx1=nx2; }

Definition at line 2891 of file reken.c.

◆ WARMUP

#define WARMUP   6

Definition at line 3786 of file reken.c.

Function Documentation

◆ Pack()

VOID Pack ( UWORD * a,
WORD * na,
UWORD * b,
WORD nb )

Definition at line 62 of file reken.c.

◆ UnPack()

VOID UnPack ( UWORD * a,
WORD na,
WORD * denom,
WORD * numer )

Definition at line 100 of file reken.c.

◆ Mully()

WORD Mully ( PHEAD UWORD * a,
WORD * na,
UWORD * b,
WORD nb )

Definition at line 126 of file reken.c.

◆ Divvy()

WORD Divvy ( PHEAD UWORD * a,
WORD * na,
UWORD * b,
WORD nb )

Definition at line 172 of file reken.c.

◆ AddRat()

WORD AddRat ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 210 of file reken.c.

◆ MulRat()

WORD MulRat ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 378 of file reken.c.

◆ DivRat()

WORD DivRat ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 500 of file reken.c.

◆ Simplify()

WORD Simplify ( PHEAD UWORD * a,
WORD * na,
UWORD * b,
WORD * nb )

Definition at line 530 of file reken.c.

◆ AccumGCD()

WORD AccumGCD ( PHEAD UWORD * a,
WORD * na,
UWORD * b,
WORD nb )

Definition at line 647 of file reken.c.

◆ TakeRatRoot()

int TakeRatRoot ( UWORD * a,
WORD * n,
WORD power )

Definition at line 680 of file reken.c.

◆ AddLong()

WORD AddLong ( UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 705 of file reken.c.

◆ AddPLon()

WORD AddPLon ( UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 750 of file reken.c.

◆ SubPLon()

VOID SubPLon ( UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 803 of file reken.c.

◆ MulLong()

WORD MulLong ( UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 841 of file reken.c.

◆ BigLong()

WORD BigLong ( UWORD * a,
WORD na,
UWORD * b,
WORD nb )

Definition at line 944 of file reken.c.

◆ DivLong()

WORD DivLong ( UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc,
UWORD * d,
WORD * nd )

Definition at line 972 of file reken.c.

◆ RaisPow()

WORD RaisPow ( PHEAD UWORD * a,
WORD * na,
UWORD b )

Definition at line 1218 of file reken.c.

◆ RaisPowCached()

VOID RaisPowCached ( PHEAD WORD x,
WORD n,
UWORD ** c,
WORD * nc )

Computes power x^n and caches the value

Description

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.

Notes

  • Caching is done in AT.small_power[]. This array is extended if necessary.

Definition at line 1286 of file reken.c.

Referenced by poly::divmod_heap(), poly::divmod_univar(), and poly::mul_heap().

◆ RaisPowMod()

WORD RaisPowMod ( WORD x,
WORD n,
WORD m )

Definition at line 1373 of file reken.c.

◆ NormalModulus()

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().

◆ MakeInverses()

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().

◆ 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().

◆ GetLongModInverses()

int GetLongModInverses ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * ia,
WORD * nia,
UWORD * ib,
WORD * nib )

Definition at line 1498 of file reken.c.

◆ Product()

WORD Product ( UWORD * a,
WORD * na,
WORD b )

Definition at line 1575 of file reken.c.

◆ Quotient()

UWORD Quotient ( UWORD * a,
WORD * na,
WORD b )

Definition at line 1610 of file reken.c.

◆ Remain10()

WORD Remain10 ( UWORD * a,
WORD * na )

Definition at line 1649 of file reken.c.

◆ Remain4()

WORD Remain4 ( UWORD * a,
WORD * na )

Definition at line 1676 of file reken.c.

◆ PrtLong()

VOID PrtLong ( UWORD * a,
WORD na,
UBYTE * s )

Definition at line 1702 of file reken.c.

◆ GetLong()

WORD GetLong ( UBYTE * s,
UWORD * a,
WORD * na )

Definition at line 1764 of file reken.c.

◆ GcdLong()

WORD GcdLong ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 2266 of file reken.c.

◆ GetBinom()

WORD GetBinom ( UWORD * a,
WORD * na,
WORD i1,
WORD i2 )

Definition at line 2657 of file reken.c.

◆ LcmLong()

WORD LcmLong ( PHEAD UWORD * a,
WORD na,
UWORD * b,
WORD nb,
UWORD * c,
WORD * nc )

Definition at line 2691 of file reken.c.

◆ TakeLongRoot()

int TakeLongRoot ( UWORD * a,
WORD * n,
WORD power )

Definition at line 2725 of file reken.c.

◆ MakeRational()

int MakeRational ( WORD a,
WORD m,
WORD * b,
WORD * c )

Definition at line 2845 of file reken.c.

◆ MakeLongRational()

int MakeLongRational ( PHEAD UWORD * a,
WORD na,
UWORD * m,
WORD nm,
UWORD * b,
WORD * nb )

Definition at line 2893 of file reken.c.

◆ CompCoef()

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().

◆ Modulus()

WORD Modulus ( WORD * term)

Definition at line 3092 of file reken.c.

◆ TakeModulus()

WORD TakeModulus ( UWORD * a,
WORD * na,
UWORD * cmodvec,
WORD ncmod,
WORD par )

Definition at line 3139 of file reken.c.

◆ TakeNormalModulus()

WORD TakeNormalModulus ( UWORD * a,
WORD * na,
UWORD * c,
WORD nc,
WORD par )

Definition at line 3311 of file reken.c.

◆ MakeModTable()

WORD MakeModTable ( )

Definition at line 3353 of file reken.c.

◆ Factorial()

int Factorial ( PHEAD WORD n,
UWORD * a,
WORD * na )

Definition at line 3439 of file reken.c.

◆ Bernoulli()

int Bernoulli ( WORD n,
UWORD * a,
WORD * na )

Definition at line 3519 of file reken.c.

◆ NextPrime()

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.

Definition at line 3654 of file reken.c.

◆ Moebius()

WORD Moebius ( PHEAD WORD nn)

Definition at line 3718 of file reken.c.

◆ iniwranf()

void iniwranf ( PHEAD0 )

Definition at line 3804 of file reken.c.

◆ wranf()

UWORD wranf ( PHEAD0 )

Definition at line 3853 of file reken.c.

◆ iranf()

UWORD iranf ( PHEAD UWORD imax)

Definition at line 3872 of file reken.c.

◆ PreRandom()

UBYTE * PreRandom ( UBYTE * s)

Definition at line 3897 of file reken.c.