Version 2.0

# Reference of functions and classes

Classes
Global Functions

Overview:

## Classes

Class | Meaning
ContFrac | Continued fractions
Edge | Edges of a Graph
Graph | Graphs
Logic | propositional logic
Matrix | Matrices
Mod | Elements of the residue class rings Z[m]
NumeralSystem | conversions between numeral systems
Perm | Permutations (from dictionary or cycle representation)
Poly | Polynomials over arbitrary rings
Rational | Rational numbers
Rsa | RSA Encryption
Set | Polymorphic sets
Vector | Vectors

## Global Functions

Function | Meaning
allFactors (n) | List of all prime factors of n
binomial (n, k) | Binomial coefficient
ceil (x) | smallest integer n >= x
chinese (mod1, *mod2) | Mod object from mod1, mod2, ... according to the Chinese remainder theorem
copy (x) | independent copy ("clone") of x
divisors (n) | List of all divisors of n
eulerPhi (n) | Euler's totient function
expMod (a, x, m) | Calculates (a**x) % m efficiently.
factor (n) | Prime factorization
factorial (n) | n! = 1*2*3* ... *n (factorial of n)
factors (n) | List of prime factors of n (without multiplicity)
fibonacci (n) | n-th element of the Fibonacci series
fit (data, functions) | Interpolation using the Gaussian method of least squares
floor (x) | highest integer n <= x
fromTo (a, b, step=1) | Iterator over equidistant integers from a to b
gcd (a,b) | greatest common divisor of a and b
gcdExt (a,b) | Extended Euclidean algorithm.
isInteger (n) | returns `True` if and only if n is of type `int`.
isNatural (n) |
isPrime (n,s=20) | Returns bool (is n a prime number?)
join (l, filler="") | Joins the elements of `l` to a string
lcm (a, b) | Least common multiple of a and b
nextPrime (n) | next prime larger than or equal to n
permutations (v, prefix=[]) | List of all permutations of v
permute (v, fn, prefix=[]) | applies procedure `fn` to all permutations of liste v.
prime (n) | n-th prime number
printTable (height, width, cellFunction, **options) | prints a table of height rows and width columns, whose cells are calculated by cellFunction.
printXTable (t, start, nValues, increment, vertical=True) | returns a table with the function defines in t.
product (v) | The product of the elements of list v
rand (n) | Integer random number from the range 0 ... n-1 n must be a natural number (int).
sum (v) | The sum of the elements of list v
toNumber (s) | converts the string s into a rational or floating point number

# Global Functions

## allFactors

Usage: `allFactors(n)`

Description:
List of all prime factors of n
Example: `allFactors(24)` returns `[2, 2, 2, 3]`.
See also `factor`, `factors`.

## binomial

Usage: `binomial(n, k)`

Description:
Binomial coefficient
n must be a nonnegative integer and k in the range 0 .. n.

## ceil

Usage: `ceil(x)`

Description:
smallest integer n >= x

## chinese

Usage: `chinese(mod1, *mod2)`

Description:
Mod object from mod1, mod2, ... according to the Chinese remainder theorem
Requires that mod1, mod2, ... are Mod objects with pairwise coprime moduli.
`chinese(Mod(a1, m1), Mod(a2, m2), ...)`
returns Mod(x, m1*m2*...) with 0 <= `x` < m1*m2*... and
`x % m1 == a1`
`x % m2 == a2`
, ...
Example:

        chinese(Mod(1,5), Mod(2,7))  # -à Mod(16,35)

(16 mod 5 = 1, 16 mod 7 = 2).
See also `Mod`

## copy

Usage: `copy(x)`

Description:
independent copy ("clone") of x

## divisors

Usage: `divisors(n)`

Description:
List of all divisors of n

## eulerPhi

Usage: `eulerPhi(n)`

Description:
Euler's totient function
Number of positive integers less than or equal to n that are coprime to n

## expMod

Usage: `expMod(a, x, m)`

Description:
Calculates (a**x) % m efficiently.
Equivalent to the Python standard function `pow`.

## factor

Usage: `factor(n)`

Description:
Prime factorization
Returns a list of pairs [factor, multiplicity]
Example:
`factor(24)`
returns `[[2,3],[3,1]]`.
See also `factors`, `allFactors`.

## factorial

Usage: `factorial(n)`

Description:
n! = 1*2*3* ... *n (factorial of n)

## factors

Usage: `factors(n)`

Description:
List of prime factors of n (without multiplicity)
Example:
`factors(24)` returns `[2, 3]`.
See also `factor`, `allFactors`.

## fibonacci

Usage: `fibonacci(n)`

Description:
n-th element of the Fibonacci series fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) für n >= 2

## fit

Usage: `fit(data, functions)`

Description:
Interpolation using the Gaussian method of least squares
`fit(data, functions)` calculates (using the method of least squares) a linear combination of the functions in `functions` with the variable `x`.
(corresponds to the Mathematica function `Fit`).
Example:

     fit([(-1,2), (1,1), (2,1), (3,0), (5,3)],
         ["1", "x", "x**2"])

calculates `[c1, c2, c3]` such that the function
`f(x) = c1*1 + c2*x + c3 * x**2`
approximates the conditions f(-1)=2, f(1)=1, f(2)=1, f(3)=0, f(5)=3 .
Result: "(6/5 * 1) + (-53/70 * x) + (3/14 * x**2)

## floor

Usage: `floor(x)`

Description:
highest integer n <= x

## fromTo

Usage: `fromTo(a, b, step=1)`

Description:
Iterator over equidistant integers from a to b
If no step is given, step is set to 1.
Examples:

        list(fromTo(3, 6))               # -à  [3,4,5,6]
        list(fromTo(3, 6, 2))            # -à  [3,5]
        list(fromTo(6, 3))               # -à  []
        list(fromTo(6, 3, -2))           # -à  [6,4]
        [2*i for i in fromTo(6, 3, -2)]  # -à  [12,8]
        sum(fromTo(1, 10))               # -à  55

## gcd

Usage: `gcd(a,b)`

Description:
greatest common divisor of a and b
Calculated using the Euclidean algorithm
See also `lcm`

## gcdExt

Usage: `gcdExt(a,b)`

Description:
Extended Euclidean algorithm.
Returns (d, x, y) with d == gcd(a,b) and x*a + y*b == d

## isInteger

Usage: `isInteger(n)`

Description:
returns `True` if and only if n is of type `int`.

## isNatural

Usage: `isNatural(n)`

## isPrime

Usage: `isPrime(n,s=20)`

Description:
Returns bool (is n a prime number?)
Implementation using Miller Rabin test
(see. Cormen, Leiserson, Rivest: Algorithms, p. 841)
See also `prime`, `nextPrime`.

## join

Usage: `join(l, filler="")`

Description:
Joins the elements of `l` to a string
Between each two adjacent elements `filler` is inserted.
This is a replacement for the string method `join()`.
In addition to the string method the list elements are converted to strings.
Example:
`join(fromTo(1,5), "-")` returns `"1-2-3-4-5"`.

## lcm

Usage: `lcm(a, b)`

Description:
Least common multiple of a and b
See also `gcd`

## nextPrime

Usage: `nextPrime(n)`

Description:
next prime larger than or equal to n
See also `isPrime`, `prime`.

## permutations

Usage: `permutations(v, prefix=[])`

Description:
List of all permutations of v
If v is sorted, the permutations are also generated in sorted order.

## permute

Usage: `permute(v, fn, prefix=[])`

Description:
applies procedure `fn` to all permutations of liste v.
If v is sorted, the permutations are also generated in sorted order.

## prime

Usage: `prime(n)`

Description:
n-th prime number
See also `isPrime`, `nextPrime`.

## printTable

Usage: `printTable(height, width, cellFunction, **options)`

Description:
prints a table of height rows and width columns, whose cells are calculated by cellFunction.
cellFunction must be a function with two parameters (row, column).
The following optional named parameters are supported:
rowHeadFn: if given, row header cells are added and calculated using this function
colHeadFn: if given, column header cells are added and calculated using this function
headAlign: "left" (default), "right" or "center"
cellAlign: "left", "right" (default) or "center"
title: if given, a title line is added, using this text
corner: if given (and rowHeadFn and colHeadFn are given), this text is displayed in the top left table corner.
Example:

     printTable(7, 7, lambda i,k: i*k % 7,
        rowHeadFn = lambda i: i,
        colHeadFn = lambda k: k,
        title = "Multiplication mod 7",
        corner = "*")

prints a multiplication table modulo 7.

## printXTable

Usage: `printXTable(t, start, nValues, increment, vertical=True)`

Description:
returns a table with the function defines in t.
TODO: explain! Example:

     printXTable([("i", lambda i:i), ("i²", lambda i:i*i)], 1, 10, 1, False)

prints a multiplication table modulo 7.

## product

Usage: `product(v)`

Description:
The product of the elements of list v
The element type must define the operator * (e.g. numbers or strings).

## rand

Usage: `rand(n)`

Description:
Integer random number from the range 0 ... n-1
n must be a natural number (int).

## sum

Usage: `sum(v)`

Description:
The sum of the elements of list v
The element type must define the operator + (e.g. numbers or strings).

## toNumber

Usage: `toNumber(s)`

Description:
converts the string s into a rational or floating point number
Examples:
`toNumber("3.1")`
`toNumber("7/3")`