reken.c File Reference

#include "form3.h"
#include <math.h>

Include dependency graph for reken.c:

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)
int	Mully (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb)
int	Divvy (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb)
int	AddRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	MulRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	DivRat (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	Simplify (PHEAD UWORD *a, WORD *na, UWORD *b, WORD *nb)
int	AccumGCD (PHEAD UWORD *a, WORD *na, UWORD *b, WORD nb)
int	TakeRatRoot (UWORD *a, WORD *n, WORD power)
int	AddLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	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)
int	MulLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	BigLong (UWORD *a, WORD na, UWORD *b, WORD nb)
int	DivLong (UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc, UWORD *d, WORD *nd)
int	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 (void)
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)
int	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)
int	GetLong (UBYTE *s, UWORD *a, WORD *na)
int	GcdLong (PHEAD UWORD *a, WORD na, UWORD *b, WORD nb, UWORD *c, WORD *nc)
int	GetBinom (UWORD *a, WORD *na, WORD i1, WORD i2)
int	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)
int	Modulus (WORD *term)
int	TakeModulus (UWORD *a, WORD *na, UWORD *cmodvec, WORD ncmod, WORD par)
int	TakeNormalModulus (UWORD *a, WORD *na, UWORD *c, WORD nc, WORD par)
int	MakeModTable (void)
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
	)		{ int i; for(i=0;i<ABS(nx2);i++)x1[i]=x2[i];nx1=nx2; }

Definition at line 2902 of file reken.c.

WARMUP

#define WARMUP   6

Definition at line 3802 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()

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

Definition at line 126 of file reken.c.

Divvy()

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

Definition at line 172 of file reken.c.

AddRat()

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

Definition at line 210 of file reken.c.

MulRat()

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

Definition at line 378 of file reken.c.

DivRat()

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

Definition at line 500 of file reken.c.

Simplify()

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

Definition at line 531 of file reken.c.

AccumGCD()

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

Definition at line 648 of file reken.c.

TakeRatRoot()

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

Definition at line 681 of file reken.c.

AddLong()

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

Definition at line 706 of file reken.c.

AddPLon()

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

Definition at line 751 of file reken.c.

SubPLon()

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

Definition at line 804 of file reken.c.

MulLong()

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

Definition at line 842 of file reken.c.

BigLong()

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

Definition at line 945 of file reken.c.

DivLong()

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

Definition at line 973 of file reken.c.

RaisPow()

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

Definition at line 1229 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 1297 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 1384 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 1404 of file reken.c.

Referenced by AddCoef(), and MergePatches().

MakeInverses()

int MakeInverses

(

void

)

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 1441 of file reken.c.

References GetModInverses().

Here is the call graph for this function:

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 1477 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 1509 of file reken.c.

Product()

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

Definition at line 1586 of file reken.c.

Quotient()

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

Definition at line 1621 of file reken.c.

Remain10()

WORD Remain10	(	UWORD *	a,
		WORD *	na
	)

Definition at line 1660 of file reken.c.

Remain4()

WORD Remain4	(	UWORD *	a,
		WORD *	na
	)

Definition at line 1687 of file reken.c.

PrtLong()

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

Definition at line 1713 of file reken.c.

GetLong()

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

Definition at line 1775 of file reken.c.

GcdLong()

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

Definition at line 2277 of file reken.c.

GetBinom()

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

Definition at line 2668 of file reken.c.

LcmLong()

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

Definition at line 2702 of file reken.c.

TakeLongRoot()

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

Definition at line 2736 of file reken.c.

MakeRational()

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

Definition at line 2856 of file reken.c.

MakeLongRational()

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

Definition at line 2904 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 3048 of file reken.c.

Referenced by Compare1().

Modulus()

int Modulus

(

WORD *

term

)

Definition at line 3103 of file reken.c.

TakeModulus()

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

Definition at line 3150 of file reken.c.

TakeNormalModulus()

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

Definition at line 3322 of file reken.c.

MakeModTable()

int MakeModTable

(

void

)

Definition at line 3364 of file reken.c.

Factorial()

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

Definition at line 3450 of file reken.c.

Bernoulli()

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

Definition at line 3530 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 3665 of file reken.c.

Moebius()

WORD Moebius

(

PHEAD WORD

nn

)

Definition at line 3729 of file reken.c.

iniwranf()

void iniwranf

(

PHEAD0

)

Definition at line 3820 of file reken.c.

wranf()

UWORD wranf

(

PHEAD0

)

Definition at line 3869 of file reken.c.

iranf()

UWORD iranf

(

PHEAD UWORD

imax

)

Definition at line 3888 of file reken.c.

PreRandom()

UBYTE * PreRandom

(

UBYTE *

s

)

Definition at line 3913 of file reken.c.