[[toc:]]
== math
=== Introduction
math is a chicken port of racket's math library.
The following documentation is largely taken directly from the racket
documentation, but tweaked for the CHICKEN implementation.
=== Modules
==== (math base)
Constants and elementary functions
===== Constants
phi.0
An approximation of φ, the [[https://en.wikipedia.org/wiki/Golden_ratio|golden ratio]].
> phi.0
1.618033988749895
euler.0
An approximation of ''e'', or [[https://en.wikipedia.org/wiki/E_(mathematical_constant)|Euler's number]].
> euler.0
2.718281828459045
> (exp 1)
2.718281828459045
catalan.0
An approximation of ''G'', or [[|Catalan's constant]].
> catalan.0
0.915965594177219
===== Functions
(float-complex? v) -> boolean
; v : any
Returns {{#t}} when {{v}} is an inexact complex number. Analogous to
[[https://wiki.call-cc.org/man/5/Module%20(chicken%20base)#flonum|flonum?]]
(number->float-complex x) -> cplxnum
; x : number
Returns a new complex number with a flonum real part and a flonum imaginary
part. Analogous to {{exact->inexact}}.
(power-of-two? x) -> boolean
; x : number
Returns {{#t}} when {{x}} is an integer power of 2.
Examples:
> (power-of-two? 1.0)
#t
> (power-of-two? 1/2)
#t
> (power-of-two? (flnext 2.0))
#f
(asinh z) -> number
(acosh z) -> number
(atanh z) -> number
; z : number
The inverses of {{sinh}}, {{cosh}}, and {{tanh}}.
(sum xs) -> number
; xs : (list-of number)
Like {{(apply + xs)}}, but incurs rounding error only once when adding inexact
numbers. (In fact, the inexact numbers in {{xs}} are summed separately using
{{fpsum}}).
===== Random Number Generation
(random-natural k) -> integer
; k : integer
Returns a random natural number less than {{k}}, which must be positive.
(random-integer a b) -> integer
; a : integer
; b : integer
Returns a random integer n such that {{(<= a n)}} and {{(< n b)}}.
(random-bits num)
; num : integer
Returns a random natural smaller than {{(expt 2 num)}}; {{num}} must be
positive. For powers of two, this is faster than using {{random-natural}},
which is implemented in terms of {{random-bits}}, using biased rejection
sampling.
===== Measuring error
(absolute-error x r) -> number
; x : number
; r : number
Usually computes {{(abs (- x r))}} using exact rationals, but handles
non-rational reals such as {{+inf.0}} specially.
Examples:
> (absolute-error 1/2 1/2)
0
> (absolute-error 0.14285714285714285 1/7)
7.93016446160826e-18
> (absolute-error +inf.0 +inf.0)
0.0
> (absolute-error +inf.0 +nan.0)
+inf.0
> (absolute-error 1e-20 0.0)
1e-20
> (absolute-error (- 1.0 (fl 4999999/5000000)) 1/5000000)
5.751132903242251e-18
(relative-error x r) -> number
; x : number
; r : number
Measures how close an approximation {{x}} is to the correct value {{r}},
relative to the magnitude of {{r}}.
This function usually computes {{(abs (/ (- x r) r))}} using exact rationals, but
handles non-rational reals such as {{+inf.0}} specially, as well as {{r = 0}}.
> (relative-error 1/2 1/2)
0
> (relative-error 0.14285714285714285 1/7)
5.551115123125783e-17
> (relative-error +inf.0 +inf.0)
0.0
> (relative-error +inf.0 +nan.0)
+inf.0
> (relative-error 1e-20 0.0)
+inf.0
> (relative-error (- 1.0 (fl 4999999/5000000)) 1/5000000)
2.8755664516211255e-11
In the last two examples, relative error is high because the result is near
zero. (Compare the same examples with {{absolute-error}}.) Because flonums are
particularly dense near zero, this makes relative error better than absolute
error for measuring the error in a flonum approximation. An even better one is
error in ulps; see {{fpulp}} and {{fpulp-error}}.
==== (math number-theory)
Number-theoretic functions
===== Congruences and modular arithmetic
(divides? m n) -> boolean
; m : integer
; n : integer
Returns {{#t}} if {{m}} divides {{n}}, {{#f}} otherwise.
Examples:
> (divides? 2 9)
#f
> (divides? 2 8)
#t
Note that 0 cannot divide anything:
> (divides? 0 5)
#f
> (divides? 0 0)
#f
Practically, if {{(divides? m n)}} is {{#t}}, then {{(/ n m)}} will return an integer.
Wikipedia: [[https://en.wikipedia.org/wiki/Divisor|Divisor]]
(bezout a b c ...) -> (list-of integer)
; a : integer
; b : integer
; c : integer
Given integers {{a b c ...}} returns a list of integers {{(list u v w ...)}}
such that {{(gcd a b c ...)}} = {{(+ (* a u) (* b v) (* c w) ...)}}.
Examples:
> (bezout 6 15)
(-2 1)
> (+ (* -2 6) (* 1 15))
3
> (gcd 6 15)
3
Wikipedia: [[https://en.wikipedia.org/wiki/B%C3%A9zout's_identity|Bézout's Identity]]
(coprime? a b ...) -> boolean
; a : integer
; b : integer
Returns {{#t}} if the integers {{a b ...}} are coprime. Formally, a set of
integers is considered coprime (also called relatively prime) if their greatest
common divisor is 1.
Example:
> (coprime? 2 6 15)
#t
Wikipedia: [[https://en.wikipedia.org/wiki/Coprime|Coprime]]
(pairwise-coprime? a b ...) -> boolean
; a : integer
; b : integer
Returns {{#t}} if the integers {{a b ...}} are ''pairwise'' coprime, meaning that each
pair of integers is coprime.
The numbers 2, 6 and 15 are coprime, but not ''pairwise'' coprime, because 6 and 15
share the factor 3:
> (pairwise-coprime? 2 6 15)
#f
Wikipedia:[[https://en.wikipedia.org/wiki/Pairwise_coprime|Pairwise Coprime]]
(solve-chinese as ns) -> integer
; as : (list-of integer)
; ns : (list-of integer)
Given a length-k list of integers as and a length-k list of coprime moduli ns,
(solve-chinese as ns) returns the least natural number x that is a solution to
the equations
x = a₁ (mod n₁)
...
x = aₖ (mod nₖ)
The solution {{x}} is less than {{(* n1 ... nk)}}.
The moduli {{ns}} must all be positive.
What is the least number {{x}} that when divided by 3 leaves a remainder of 2, when
divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder
of 2?
> (solve-chinese '(2 3 2) '(3 5 7))
23
Wikipedia: [[https://en.wikipedia.org/wiki/Chinese_remainder_theorem|Chinese Remainder Theorem]]
(quadratic-residue? a n) -> boolean
; a : integer
; n : integer
Returns {{#t}} if {{a}} is a quadratic residue modulo {{n}}, otherwise {{#f}}. The modulus
{{n}} must be positive, and a must be nonnegative.
Formally, {{a}} is a quadratic residue modulo {{n}} if there exists a number
{{x}} such that {{(* x x)}} = {{a}} (mod {{n}}). In other words,
{{(quadratic-residue? a n)}} is {{#t}} when {{a}} is a perfect square modulo
{{n}}.
Examples:
> (quadratic-residue? 0 4)
#f
> (quadratic-residue? 1 4)
#t
> (quadratic-residue? 2 4)
#f
> (quadratic-residue? 3 4)
#f
Wikipedia: [[https://en.wikipedia.org/wiki/Quadratic_residue|Quadratic Residue]]
(quadratic-character a p) -> integer
; a : integer
; b : integer
Returns the value of the quadratic character modulo the prime {{p}}. That is,
for a non-zero {{a}} the number 1 is returned when {{a}} is a quadratic
residue, and -1 is returned when {{a}} is a non-residue. If {{a}} is zero, then
0 is returned.
If {{a}} is negative or {{p}} is not positive, quadratic-character raises an
error. If {{p}} is not prime, (quadratic-character a p) is indeterminate.
This function is also known as the ''Legendre symbol''.
> (quadratic-character 0 5)
0
> (quadratic-character 1 5)
1
> (quadratic-character 2 5)
-1
> (quadratic-character 3 5)
-1
Wikipedia: [[https://en.wikipedia.org/wiki/Legendre_symbol|Legendre Symbol]]
(jacobi-symbol a n) -> integer
; a : integer
; n : integer
Computes the Jacobi symbol for any nonnegative integer {{a}} and any positive
odd integer {{n}}.
If {{n}} is not an odd positive integer, {{(jacobi-symbol a n)}} throws an exception.
> (jacobi-symbol 1 1)
1
> (jacobi-symbol 8 11)
-1
> (jacobi-symbol 39 27)
0
> (jacobi-symbol 22 59)
1
> (jacobi-symbol 32 8)
Error: (jacobi-symbol) bad argument type - not an odd integer: 8
Wikipedia: [[https://en.wikipedia.org/wiki/Jacobi_symbol|Jacobi Symbol]]
(modular-inverse a n) -> integer
; a : integer
; b : integer
Returns the inverse of a modulo {{n}} if {{a}} and {{n}} are coprime, otherwise raises an
error. The modulus {{n}} must be positive, and {{a}} must be nonzero.
Formally, if {{a}} and {{n}} are coprime, {{b}} = {{(modular-inverse a n)}} is the unique
natural number less than {{n}} such that {{(* a b)}} = {{1}} (mod {{n}}).
> (modular-inverse 2 5)
3
> (modulo (* 2 3) 5)
1
Wikipedia: [[https://en.wikipedia.org/wiki/Modular_multiplicative_inverse|Multiplicative Inverse]]
(modular-expt a b n) -> integer
; a : integer
; b : integer
; n : integer
Computes {{(modulo (expt a b) n)}}, but much more efficiently. The modulus {{n}} must
be positive, and the exponent {{b}} must be nonnegative.
> (modulo (expt -6 523) 19)
13
> (modular-expt -6 523 19)
13
> (modular-expt 9 158235208 19)
4
> ; don't try this at home!
(modulo (expt 9 158235208) 19)
4
===== Parameterized Modular Arithmetic
The {{math.number-theory}} library supports modular arithmetic parameterized on
a current modulus. For example, the code
(with-modulus n
(mod= (modexpt a b) c))
corresponds with the mathematical statement ''a^b'' = ''c'' (mod ''n'').
The current modulus is stored in a parameter that, for performance reasons, can
only be set using with-modulus. (The basic modular operators cache parameter
reads, and this restriction guarantees that the cached values are current.
'''NOTE:''' I'm not entirely sure this is true for the chicken port, as a
slightly more complicated racket syntax-case has been turned into a simple
syntax-rule for {{(parameterize ...)}})
Wikipedia: [[https://en.wikipedia.org/wiki/Modular_arithmetic|Modular Arithmetic]]
(with-modulus n body ...)
; n : integer
Alters the current modulus within the dynamic extent of {{body}}. The
expression {{n}} must evaluate to a positive integer.
By default, the current modulus is 1, meaning that every modular arithmetic
expression that does not raise an error returns 0.
(current-modulus) -> integer
Returns the current modulus.
Examples:
> (current-modulus)
1
> (with-modulus 5 (current-modulus))
5
(mod x) -> integer
; x : exact rational
Converts a rational number {{x}} to a natural number less than the current
modulus.
If {{x}} is an integer, this is equivalent to {{(modulo x n)}}. If {{x}} is a
fraction, an integer input is generated by multiplying its numerator by its
denominator’s modular inverse.
Examples:
> (with-modulus 7 (mod (* 218 7)))
0
> (with-modulus 7 (mod 3/2))
5
> (with-modulus 7 (mod/ 3 2))
5
> (with-modulus 7 (mod 3/7))
Error: (modular-inverse) bad argument type - not coprime to modulus 7: 7
(mod+ a ...) -> integer
(mod* a ...) -> integer
; a : integer
Equivalent to {{(modulo (+ a ...) (current-modulus))}} and {{(modulo (* a ...) (current-modulus))}},
respectively, but generate smaller intermediate values.
(modsqr a) -> integer
(modexpt a b) -> integer
; a : integer
; b : integer
Equivalent to {{(mod* a a)}} and {{(modular-expt a b (current-modulus))}}, respectively.
(mod- a b ...) -> integer
; a : integer
; b : integer
Equivalent to {{(modulo (- a b ...) (current-modulus))}}, but generates smaller
intermediate values. Note that {{(mod- a)}} = {{(mod (- a))}}.
(mod/ a b ...) -> integer
; a : integer
; b : integer
Divides a by {{(* b ...)}}, by multiplying {{a}} by the multiplicative inverse of
{{(* b ...)}}. The one-argument variant returns the modular inverse of {{a}}.
Note that {{(mod/ a b ...)}} is '''not''' equivalent to
{{(modulo (/ a b ...) (current-modulus))}}; see {{mod=}} for a demonstration.
(mod= a b ...) -> boolean
(mod< a b ...) -> boolean
(mod<= a b ...) -> boolean
(mod> a b ...) -> boolean
(mod>= a b ...) -> boolean
; a : integer
; b : integer
Each of these is equivalent to {{(op (mod a) (mod b) ...)}}, where op is the
corresponding numeric comparison function. Additionally, when given one
argument, the inequality tests always return {{#t}}.
Suppose we wanted to know why 17/4 = 8 (mod 15), but 51/12 (mod 15) is
undefined, even though normally 51/12 = 17/4. In code,
> (with-modulus 15 (mod/ 17 4))
8
> (/ 51 12)
17/4
> (with-modulus 15 (mod/ 51 12))
Error: (modular-inverse) bad argument type - not coprime to modulus 15: 12
We could try to divide by brute force: find, modulo 15, all the numbers {{a}} for
which {{(mod* a 4)}} is 17, then find all the numbers {{b}} for which {{(mod* a 12)}} is
51.
(import srfi-42)
> (with-modulus 15
(list-ec (:range a 15)
(if (mod= (mod* a 4) 17))
a))
(8)
> (with-modulus 15
(list-ec (:range a 15)
(if (mod= (mod* a 12) 51))
a))
(3 8 13)
So the problem isn't that {{b}} doesn't exist, it's that {{b}} isn't
''unique''.
===== Primes
(prime? z) -> boolean
; z : integer
Returns {{#t}} if {{z}} is a prime, {{#f}} otherwise.
Formally, an integer {{z}} is prime when the only positive divisors of {{z}}
are 1 and {{(abs z)}}.
The positive primes below 20 are:
> (filter prime? (iota 20 1))
(2 3 5 7 11 13 17 19)
The corresponding negative primes are:
> (filter prime? (iota 20 0 -1))
(-2 -3 -5 -7 -11 -13 -17 -19)
Wikipedia: [[https://en.wikipedia.org/wiki/Prime_number|Prime Number]]
(odd-prime? z) -> boolean
; z : integer
Returns {{#t}} if {{z}} is a odd prime, {{#f}} otherwise.
> (odd-prime? 2)
#f
> (odd-prime? 3)
#t
(nth-prime n) -> integer
; n : integer
Returns the {{n}}th positive prime; {{n}} must be nonnegative.
> (nth-prime 0)
2
> (nth-prime 1)
3
> (nth-prime 2)
5
(random-prime n) -> integer
; n : integer
Returns a random prime smaller than {{n}}, which must be greater than 2.
The function {{random-prime}} picks random numbers below {{n}} until a prime is
found.
> (random-prime 10)
3
> (random-prime 10)
2
> (random-prime 10)
5
(next-prime z) -> integer
; z : integer
Returns the first prime larger than {{z}}.
> (next-prime 4)
5
> (next-prime 5)
7
(prev-prime z) -> integer
Returns the first prime smaller than {{z}}.
> (prev-prime 4)
3
> (prev-prime 5)
3
(next-primes z n) -> (list-of integer)
; z : integer
; n : integer
Returns list of the next {{n}} primes larger than {{z}}; {{n}} must be
nonnegative.
> (next-primes 2 4)
(3 5 7 11)
(prev-primes z n) -> (list-of integer)
; z : integer
; n : integer
Returns list of the next {{n}} primes smaller than {{z}}; {{n}} must be
nonnegative.
> (prev-primes 13 4)
(11 7 5 3)
(factorize n) -> (list-of (list integer integer))
; n : integer
Returns the factorization of a natural number {{n}}. The factorization consists of
a list of corresponding primes and exponents. The primes will be in ascending
order.
The prime factorization of 600 = 2^3 * 3^1 * 5^2:
> (factorize 600)
((2 3) (3 1) (5 2))
(defactorize f) -> integer
; f : (list-of (list integer integer))
Returns the natural number, whose factorization is given by {{f}}. The
factorization {{f}} is represented as described in {{factorize}}.
> (defactorize '((2 3) (3 1) (5 2)))
600
Wikipedia: [[https://en.wikipedia.org/wiki/Integer_factorization|Integer Factorization]]
(divisors z) -> (list-of integer)
; z : integer
Returns a list of all positive divisors of the integer {{z}}. The divisors appear
in ascending order.
> (divisors 120)
(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
> (divisors -120)
(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
(prime-divisors z) -> (list-of integer)
; z : integer
Returns a list of all positive prime divisors of the integer {{z}}. The divisors
appear in ascending order.
> (prime-divisors 120)
'(2 3 5)
(prime-exponents z) -> (list-of integer)
; z : integer
Returns a list of the exponents of in a factorization of the integer {{z}}.
> (define z (* 2 2 2 3 5 5))
> (prime-divisors z)
(2 3 5)
> (prime-exponents z)
(3 1 2)
===== Roots
(integer-root n m) -> integer
; n : integer
; m : integer
Returns the mth integer root of {{n}}. This is the largest integer {{r}} such that
{{(expt r m)}} <= {{n}}.
> (integer-root (expt 3 4) 4)
3
> (integer-root (+ (expt 3 4) 1) 4)
3
(integer-root/remainder n m) -> integer integer
; n : integer
; m : integer
Returns two values. The first, {{r}}, is the {{m}}th integer root of {{n}}. The
second is {{n}}-{{r}}^{{m}}.
> (integer-root/remainder (expt 3 4) 4)
3
0
> (integer-root/remainder (+ (expt 3 4) 1) 4)
3
1
===== Powers
(max-dividing-power a b) -> integer
; a : integer
; b : integre
Returns the largest exponent, {{n}}, of a power with base {{a}} that divides
{{b}}.
That is, {{(expt a n)}} divides {{b}} but {{(expt a (+ n 1))}} does not divide {{b}}.
> (max-dividing-power 3 (expt 3 4))
4
> (max-dividing-power 3 5)
0
(perfect-power m) -> (or (list integer integer) #f)
; m : integer
If {{m}} is a perfect power, a list with two elements {{b}} and {{n}} such that
{{(expt b n)}} = {{m}} is returned, otherwise {{#f}} is returned.
> (perfect-power (expt 3 4))
(3 4)
> (perfect-power (+ (expt 3 4) 1))
#f
(perfect-power? m) -> boolean
; m : integer
Returns {{#t}} if {{m}} is a perfect power, otherwise {{#f}}.
> (perfect-power? (expt 3 4))
#t
> (perfect-power? (+ (expt 3 4) 1))
#f
Wikipedia: [[https://en.wikipedia.org/wiki/Perfect_power|Perfect Power]]
(prime-power m) -> (or (list integer integer) #f)
; m : integer
If {{M}} is a power of the form {{(expt p n)}} where p is prime, then a list with the
prime and the exponent is returned, otherwise {{#f}} is returned.
> (prime-power (expt 3 4))
(3 4)
> (prime-power (expt 6 4))
#f
(prime-power? m) -> boolean
; m : integer
Returns {{#t}} if {{m}} is a prime power, otherwise {{#f}}.
> (prime-power? (expt 3 4))
#t
> (prime-power? (expt 6 4))
#f
> (prime-power? 1)
#f
> (prime-power? 0)
#f
(odd-prime-power? m) -> boolean
; m : integer
Returns {{#t}} if {{m}} is a power of an odd prime, otherwise {{#f}}.
> (odd-prime-power? (expt 2 4))
#f
> (odd-prime-power? (expt 3 4))
#t
> (odd-prime-power? (expt 15 4))
#f
(as-power m) -> integer integer
; m : integer
Returns two values {{b}} and {{n}} such that {{m}} = {{(expt b n)}} and {{n}}
is maximal.
> (as-power (* (expt 2 4) (expt 3 4)))
6
4
> (expt 6 4)
1296
> (* (expt 2 4) (expt 3 4))
1296
> (as-power (* (expt 2 4) (expt 3 5)))
3888
1
(prefect-square m) -> (or integer #f)
Returns {{(sqrt m)}} if {{m}} is perfect square, otherwise {{#f}}.
> (perfect-square 9)
3
> (perfect-square 10)
#f
===== Multiplicative and Arithmetic Functions
The functions in this section are ''multiplicative'' (with exception of the Von
Mangoldt function). In number theory, a multiplicative function is a function
{{f}} such that {{(f (* a b))}} = {{(* (f a) (f b))}} for all coprime natural
numbers {{a}} and {{b}}.
(totient n) -> integer
; n : integer
Returns the number of integers from 1 to {{n}} that are coprime with {{n}}.
This function is known as Euler's totient or phi function.
> (totient 9)
6
> (length (filter (curry coprime? 9) (range 10)))
6
Wikipedia: [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|Euler's Totient]]
(moebius-mu n) -> integer
; n : integer
Returns:
* 1 if {{n}} is a square-free product of an even number of primes
* -1 if {{n}} is a square-free product of an odd number of primes
* 0 if {{n}} has a multiple prime factor
> (moebius-mu (* 2 3 5))
-1
> (moebius-mu (* 2 3 5 7))
1
> (moebius-mu (* 2 2 3 5 7))
0
Wikipedia: [[https://en.wikipedia.org/wiki/M%C3%B6bius_function|Moebius Function]]
(divisor-sum n k) -> integer
; n : integer
; k : integer
Returns sum of the {{k}}th powers of all divisors of {{n}}.
> (divisor-sum 12 2)
210
> (apply + (map sqr (divisors 12)))
210
Wikipedia: [[https://en.wikipedia.org/wiki/Divisor_function|Divisor Function]]
(prime-omega n) -> integer
; n : integer
Counting multiplicities the number of prime factors of {{n}} is returned.
> (prime-omega (* 2 2 2 3 3 5))
6
OEIS: [[https://oeis.org/A001222|Big Omega]], [[https://oeis.org/wiki/Omega(n),_number_of_prime_factors_of_n_(with_multiplicity)|Big Omega]]
(mangoldt-lambda n) -> number
; n : integer
The von Mangoldt function. If n=p^k for a prime {{p}} and an integer {{k>=1}}
then {{(log n)}} is returned. Otherwise {{0}} is returned.
Note: The Von Mangoldt function is not multiplicative.
> (mangoldt-lambda (* 3 3))
1.0986122886681098
> (log 3)
1.0986122886681098
Wikipedia: [[https://en.wikipedia.org/wiki/Von_Mangoldt_function|Von Mangoldt Function]]
===== Number Sequences
(bernoulli-number n) -> ratnum
; n : integer
Returns the {{n}}th Bernoulli number; {{n}} must be nonnegative.
> (map bernoulli-number (iota 9))
(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30)
Note that these are the ''first'' Bernoulli numbers, since
{{(bernoulli-number 1)}} = {{-1/2}}.
Wikipedia: [[https://en.wikipedia.org/wiki/Bernoulli_number|Bernoulli Number]]
(eulerian-number n k) -> integer
; n : integer
; k : integer
Returns the Eulerian number {{}}; both arguments must be nonnegative.
> (eulerian-number 5 2)
66
Wikipedia: [[http://mathworld.wolfram.com/EulerianNumber.html|Eulerian Number]]
(fibonacci n) -> integer
; n : integer
Returns the {{n}}th Fibonacci number; {{n}} must be nonnegative.
The ten first Fibonacci numbers:
> (map fibonacci (iota 10))
'(0 1 1 2 3 5 8 13 21 34)
Wikipedia: [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacci Number]]
(make-fibonaci a b) -> (integer -> integer)
; a : integer
; b : integer
Returns a function representing a Fibonacci sequence with the first two numbers
{{a}} and {{b}}. The {{fibonacci}} function is defined as {{(make-fibonacci 0 1)}}.
The Lucas numbers are defined as a Fibonacci sequence starting with 2 and 1:
> (map (make-fibonacci 2 1) (iota 10))
(2 1 3 4 7 11 18 29 47 76)
Wikipedia: [[https://wikipedia.org/wiki/Lucas_number|Lucas Number]]
(modular-fibonacci n m) -> integer
; n : integer
; m : integer
Returns the {{n}}th Fibonacci number modulo {{m}}; {{n}} must be nonnegative
and {{m}} must be positive.
The ten first Fibonacci numbers modulo 5:
> (map (lambda (n) (modular-fibonacci n 5)) (range 10))
(0 1 1 2 3 0 3 3 1 4)
(make-modular-fibonacci a b) -> (integer integer -> integer)
; a : integer
; b : integer
Like {{make-fibonacci}}, but makes a modular fibonacci sequence.
(farey-sequence n) -> (list-of ratnum)
; n : integer
Returns a list of the numbers in the {{n}}th Farey sequence; {{n}} must be positive.
The {{n}}th Farey sequence is the sequence of all completely reduced rational
numbers from 0 to 1 which denominators are less than or equal to {{n}}.
> (farey-sequence 1)
(0 1)
> (farey-sequence 2)
(0 1/2 1)
> (farey-sequence 3)
(0 1/3 1/2 2/3 1)
Wikipedia: [[https://en.wikipedia.org/wiki/Farey_sequence|Farey Sequence]]
(tangent-number n) -> integer
; n : integer
Returns the {{n}}th tangent number; {{n}} must be nonnegative.
> (tangent-number 1)
1
> (tangent-number 2)
0
> (tangent-number 3)
2
MathWorld: [[http://mathworld.wolfram.com/TangentNumber.html|Tangent Number]]
===== Combinatorics
(factorial n) -> integer
; n : integer
Returns the factorial of {{n}}, which must be nonnegative. The factorial of
{{n}} is the number {{(* n (- n 1) (- n 2) ... 1)}}.
> (factorial 3)
6
> (factorial 0)
1
Wikipedia: [[https://en.wikipedia.org/wiki/Factorial|Factorial]]
(binomial n k) -> integer
; n : integer
; k : integer
Returns the number of ways to choose a set of k items from a set of n items;
i.e. the order of the k items is not significant. Both arguments must be
nonnegative.
When {{k > n}}, {{(binomial n k) = 0}}. Otherwise, {{(binomial n k)}} is
equivalent to {{(/ (factorial n) (factorial k) (factorial (- n k)))}},
but computed more quickly.
> (binomial 5 3)
10
Wikipedia: [[https://en.wikipedia.org/wiki/Binomial_coefficient|Binomial Coefficient]]
(permutations n k) -> integer
; n : integer
; k : integer
Returns the number of ways to choose a sequence of {{k}} items from a set of n
items; i.e. the order of the {{k}} items is significant. Both arguments must be
nonnegative.
When {{k > n}}, {{(permutations n k) = 0}}. Otherwise, {{(permutations n k)}}
is equivalent to {{(/ (factorial n) (factorial (- n k)))}}.
> (permutations 5 3)
60
Wikipedia: [[https://en.wikipedia.org/wiki/Permutation#Permutations_in_combinatorics|Permutations]]
(multinomial n ks) -> integer
; n : integer
; ks : (list-of integer)
A generalization of binomial to multiple sets of choices; e.g.
{{(multinomial n (list k0 k1 k2))}} is the number of ways to choose a set of
{{k0}} items, a set of {{k1}} items, and a set of {{k2}} items from a set of {{n}}
items. All arguments must be nonnegative.
When {{(apply + ks) = n}}, this is equivalent to
{{(apply / (factorial n) (map factorial ks))}}. Otherwise, multinomial returns 0.
> (multinomial 5 '(3 2))
10
> (= (multinomial 8 '(5 3))
(binomial 8 5)
(binomial 8 3))
#t
> (multinomial 10 '(5 3 2))
2520
> (multinomial 0 '())
1
> (multinomial 4 '(1 1))
0
Wikipedia: [[https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients|Multinomial Coefficient]]
(partitions n) -> integer
; n : integer
Returns the number of partitions of {{n}}, which must be nonnegative. A partition
of a positive integer {{n}} is a way of writing {{n}} as a sum of positive integers.
The number 3 has the partitions {{(+ 1 1 1)}}, {{(+ 1 2)}} and {{(+ 3)}}.
> (partitions 3)
3
> (partitions 4)
5
Wikipedia: [[https://en.wikipedia.org/wiki/Partition_(number_theory)|Partition]]
===== Polygonal numbers
(triangle-number? n) -> boolean
(square-number? n) -> boolean
(pentagonal-number? n) -> boolean
(hexagonal-number? n) -> boolean
(heptagonal-number? n) -> boolean
(octagonal-number? n) -> boolean
; n : integer
These functions check whether the input is a polygonal number of the types
triangle, square, pentagonal, hexagonal, heptagonal and octogonal respectively.
Wikipedia: [[https://en.wikipedia.org/wiki/Polygonal_number|Polygonal Number]]
(triangle-number n) -> boolean
(sqr n) -> boolean
(pentagonal-number n) -> boolean
(hexagonal-number n) -> boolean
(heptagonal-number n) -> boolean
(octagonal-number n) -> boolean
; n : integer
These functions return the {{n}}th polygonal number of the corresponding type
of polygonal number.
===== Fractions
(mediant x y) -> ratnum
; x : ratnum
; y : ratnum
Computes the mediant of the numbers {{x}} and {{y}}. The mediant of two
fractions {{p/q}} and {{r/s}} in their lowest term is the number
{{(p+r)/(q+s)}}.
> (mediant 1/2 5/6)
3/4
Wikipedia: [[https://en.wikipedia.org/wiki/Mediant_(mathematics)|Mediant]]
===== The Quadratic Equation
(quadratic-solutions a b c) -> (list-of number)
a : number
b : number
c : number
Returns a list of all real solutions to the equation a {{x^2 + bx + c = 0}}
with real coefficients.
> (quadratic-solutions 1 0 -1)
'(-1 1)
> (quadratic-solutions 1 2 1)
'(-1)
> (quadratic-solutions 1 0 1)
'()
(quadratic-integer-solutions a b c) -> (list-of integer)
; a : number
; b : number
; c : number
Returns a list of all integer solutions to the equation a {{x^2 + bx + c = 0}}
with real coefficients.
> (quadratic-integer-solutions 1 0 -1)
'(-1 1)
> (quadratic-integer-solutions 1 0 -2)
'()
(quadratic-natural-solutions a b c) -> (list-of integer)
; a : number
; b : number
; c : number
Returns a list of all natural solutions to the equation a {{x^2 + bx + c = 0}}
with real coefficients.
> (quadratic-natural-solutions 1 0 -1)
'(1)
> (quadratic-natural-solutions 1 0 -2)
'()
(complex-quadratic-solutions a b c) -> (list-of number)
; a : number
; b : number
; c : number
Returns a list of all complex solutions to the equation a {{x^2 + bx + c = 0}}.
This function allows complex coeffecients.
> (complex-quadratic-solutions 1 0 1)
(0-1i 0+1i)
> (complex-quadratic-solutions 1 0 (sqrt -1))
(-0.7071067811865476+0.7071067811865475i 0.7071067811865476-0.7071067811865475i)
> (complex-quadratic-solutions 1 0 1)
(0-1i 0+1i)
===== The group Zn and Primitive Roots
The numbers 0, 1, ..., n-1 with addition and multiplication modulo {{n}} is a ring
called {{Zn}}.
The group of units in {{Zn}} with respect to multiplication modulo {{n}} is
called {{Un}}.
The order of an element {{x}} in {{Un}} is the least {{k>0}} such that {{x^k=1 mod n}}.
A generator the group {{Un}} is called a primitive root modulo {{n}}. Note that {{g}} is a
primitive root if and only if {{order(g)=totient(n)}}. A group with a generator is
called cyclic.
Wikipedia: [[https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n|The Group Zn]]
(unit-group n) -> (list-of integer)
; n : integer
Returns a list of all elements of {{Un}}, the unit group modulo {{n}}. The
modulus {{n}} must be positive.
> (unit-group 5)
(1 2 3 4)
> (unit-group 6)
(1 5)
(unit-group-order x n) -> integer
; x : integer
; n : integer
Returns the order of {{x}} in the group {{Un}}; both arguments must be
positive. If {{x}} and n are not coprime, {{(unit-group-order x n)}} raises an
error.
> (unit-group-order 2 5)
4
> (unit-group-order 2 6)
Error: (unit-group-order) expected coprime arguments; given 2 and 6
(unit-group-orders n) -> (list-of positive-integer)
; n : integer
Returns a list {{(list (unit-group-order x0 n) (unit-group-order x1 n) ...)}}
where {{x0}}, {{x1}}, {{...}} are the elements of {{Un}}. The modulus {{n}}
must be positive.
> (unit-group-orders 5)
(1 4 4 2)
> (map (cut unit-group-order <> 5) (unit-group 5))
(1 4 4 2)
(primitive-root? x n) -> boolean
; x : integer
; n : integer
Returns {{#t}} if the element {{x}} in {{Un}} is a primitive root modulo {{n}},
otherwise {{#f}} is returned. An error is signaled if {{x}} is not a member of
{{Un}}. Both arguments must be positive.
> (primitive-root? 1 5)
#f
> (primitive-root? 2 5)
#t
> (primitive-root? 5 5)
Error: (primitive-root?) expected coprime arguments; given 5 and 5
(exists-primitive-root? n) -> boolean
; n : integer
Returns {{#t}} if the group {{Un}} has a primitive root (i.e. it is cyclic),
otherwise {{#f}} is returned. In other words, {{#t}} is returned if {{n}} is
one of {{1}}, {{2}}, {{4}}, {{p^e}}, {{2*p^e}} where {{p}} is an odd prime, and
{{#f}} otherwise. The modulus {{n}} must be positive.
> (exists-primitive-root? 5)
#t
> (exists-primitive-root? 6)
#t
> (exists-primitive-root? 12)
#f
(primitive-root n) -> (or integer false)
Returns a primitive root of {{Un}} if one exists, otherwise {{#f}} is returned.
The modulus {{n}} must be positive.
> (primitive-root 5)
2
> (primitive-root 6)
5
(primitive-roots n) -> (list-of integer)
; n : integer
Returns a list of all primitive roots of {Un}. The modulus {{n}} must be positive.
> (primitive-roots 3)
(2)
> (primitive-roots 5)
(2 3)
> (primitive-roots 6)
(5)
=== Original documentation
[[https://docs.racket-lang.org/math/]]
=== Development status
This egg is still largely under active development, with the exception of the
{{math.number-theory}} module, which is finished and ready for use.
=== Implementation caveats
* It's possible some undefined behavior may occur with arguments of the wrong
type, since a good amount of the original functions were originally defined
in typed racket, which AFAIK would catch those and throw an exception.
* In some places the original implementation references {{unsafe-}} {{fx}} and
{{fl}} operators, but these are actually just aliased to safe operators. This
implementation just uses chicken's {{chicken.fixnum}} module, which is
unsafe. This may also lead to undefined behavior in some cases.
=== Author
Neil Toronto and Jens Axel Søgaard for Racket
=== Maintainer
[[/users/diego-mundo|Diego A. Mundo]]
=== Repository
[[https://github.com/dieggsy/chicken-math]]
=== License
GPL-3.0
=== Version History
; 0.3.0 : Finish (math base) and (math flonum), bug and typo fixes, credit original authors
; 0.2.3 : Fix broken .egg file
; 0.2.2 : Re-organize internals, add (math base constants)
; 0.2.1 : Minor bug fixes
; 0.2.0 : Update (math number-theory quadratic) to reflect upstream
; 0.1.0 : Initial release