NumTheory

© 2009,2012-2013 John Abbott
GNU Free Documentation License, Version 1.2

CoCoALib Documentation Index

User documentation

Generalities

The functions in the NumTheory file are predominantly basic operations from number theory. Most of the functions may be applied to machine integers or big integers (i.e. values of type BigInt). Please recall that computational number theory is not the primary remit of CoCoALib, so do not expect to find a complete collection of operations here -- you would do better to look at Victor Shoup's NTL (Number Theory Library), or PARI/GP, or some other specialized library/system.

See also IntOperations for very basic arithmetic operations on integers, and BigRat for very basic arithmetic operations on rational numbers.

Examples

The Functions Available For Use

Several of these functions give errors if they are handed unsuitable values: unless otherwise indicated below the error is of type ERR::BadArg. All functions expecting a modulus will throw an error if the modulus is less than 2 (or an unsigned long value too large to fit into a long).

The main functions available are:

Continued Fractions

Several of these functions give errors if they are handed unsuitable values: unless otherwise indicated below the error is of type ERR::BadArg.

Recall that any real number has an expansion as a continued fraction (e.g. see Hardy & Wright for definition and many properties). This expansion is finite for any rational number. We adopt the following conventions which guarantee that the expansion is unique:

For example, with these conventions the expansion of -7/3 is (-3, 1, 2).

The main functions available are:

Chinese Remaindering -- Integer Reconstruction

CoCoALib offers the class CRTMill for reconstructing an integer from several residue-modulus pairs via Chinese Remaindering. At the moment the moduli from distinct pairs must be coprime.

The operations available are:

Rational Reconstruction

CoCoALib offers two heuristic methods for reconstructing rationals from residue-modulus pairs; they have the same user interface but internally one algorithm is based on continued fractions while the other uses lattice reduction. The methods are heuristic, so may (rarely) produce an incorrect result.

NOTE the heuristic requires the (combined) modulus to be a certain amount larger than strictly necessary to reconstruct the correct answer (assuming perfect bounds are known). In practice, this means that the methods always fail if the combined modulus is too small.

The constructors available are:

The operations available are:

There is also a function for deterministic rational reconstruction which requires certain bounds to be given in input. It uses the continued fraction method.

Maintainer Documentation

Correctness of ExtendedEuclideanAlg is not immediately clear, because the cofactor variables could conceivably overflow -- in fact this cannot happen (at least on a binary computer): for a proof see Shoup's book A Computational Introduction to Number Theory and Algebra, in particular Theorem 4.3 and the comment immediately following it. There is just one line where a harmless "overflow" could occur -- it is commented in the code.

I have decided to make ExtGcd give an error if the inputs are both zero because this is an exceptional case, and so should be handled specially. I note that mpz_exgcd accepts this case, and returns two zero cofactors; so if we decide to accept this case, we should do the same -- this all fits in well with the (reasonable/good) principle that "zero inputs have zero cofactors".

Several functions are more complicated than you might expect because I wanted them to be correct for all possible machine integer inputs (e.g. including the most negative long value).

In some cases the function which does all the work is implemented as a file local function operating on unsigned long values: the function should normally be used only via the "dispatch" functions whose args are of type MachineInt or BigInt.

The impl of eratosthenes is fairly straightforward given that I chose to represent only odd numbers in the table: the k-th entry corresponds to the integer 2*k+1. Overflow cannot occur: recall that the table size is at most half the biggest long. I'm hoping that C++11 will avoid the cost of copying the result upon returning. Anyway, I think the code is a decent compromise between readability, speed and space efficiency.

The continued fraction functions are all pretty simple. The only tricky part is that the "end" of the ContFracIter is represented by both myFrac and myQuot being zero. This means that a newly created iterator for zero is already ended.

CFApproximantsIter delegates most of the work to ContFracIter.

Bugs, Shortcomings, etc.

Several functions return long values when perhaps unsigned long would possibly be better choice (since it offers a greater range, and in the case of gcd it would permit the fn to return a result always, rather than report "overflow"). The choice of return type was dictated by the coding conventions, which were in turn dictated by the risks of nasty surprises to unwary users unfamiliar with the foibles of unsigned values in C++.

Should there also be procedural forms of functions which return BigInt values? (e.g. gcd, lcm, InvMod, PowerMod, and so on).

Certain implementations of PowerMod should be improved (e.g. to use PowerModSmallModulus whenever possible). Is behaviour for 0^0 correct?

LucasTest should produce a certificate, and be made publicly accessible.

How should the cont frac iterators be printed out???

ContFracIter could be rather more efficient for rationals having very large numerator and denominator. One way would be to compute with num and den divided by the same large factor (probably a power of 2), and taking care to monitor how accurate these "scaled" num and den are. I'll wait until there is a real need before implementing (as I expect it will turn out a bit messy).

CFApproximantsIter::operator++() should be made more efficient.