Zora.Math

Assorted mathematical functions.

Prime numbers and division

primes :: [Integer]

A complete, monotonically increasing, infinite list of primes. Implementation from http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell).

composites :: [Integer]

A complete, monotonically increasing, infinite list of composite numbers.

prime :: Integer -> Bool

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number. Returns whether the parameter is a prime number.

prime_miller_rabin :: Integer -> Bool

O(log^3 n) Uses the Miller-Rabin primality test to determine primality. Always correctly identifies primes, but may misidentify some composites as primes (for most practical input values, this will not happen (~3 below 10^9? 0 below 10^7.).).

coprime :: Integer -> Integer -> Bool

O(min(n, m)) Returns whether the the two parameters are coprime, that is, whether they share any divisors.

euler_phi :: Integer -> Integer

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers).

factor :: Integer -> [Integer]

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number.

factor_number_is_perfect_square :: Integer -> [Integer]

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number.

divisors :: Integer -> [Integer]

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number. Essentially, linear in the time it takes to factor the number.

divisors_number_is_perfect_square :: Integer -> [Integer]

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number. Essentially, linear in the time it takes to factor the number.

num_divisors :: Integer -> Integer

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number. Essentially, linear in the time it takes to factor the number.

num_divisors_of_n_squared_leq_n :: Integer -> Integer

O(k n log(n)^-1), where k is the number of primes dividing n (double-counting for powers). n log(n)^-1 is an approximation for the number of primes below a number. Essentially, linear in the time it takes to factor the number.

Square roots

irrational_squares :: [Integer]

An infinite list of integers with irrational square roots.

sqrt_convergents :: Integer -> [(Integer, Integer)]

A list of fractions monotonically increasingly accurately approximating the square root of the parameter, where each fraction is represented as a pair of (numerator, denominator) See http://en.wikipedia.org/wiki/Convergent_(continued_fraction).

continued_fraction_sqrt :: Integer -> [Integer]

O(k) The continued fraction representation of the square root of the parameter. k is the length of the continued fraction.

continued_fraction_sqrt_infinite :: Integer -> [Integer]

An infinite list of the terms of the continued fraction representation of the square root of the given parameter.

square :: Integer -> Bool

Determines whether the given integer is a square number.

Modular arithmetic

add_mod :: Integer -> Integer -> Integer -> Integer

Adds the second parameter by the third, mod the first. E.g.:

add_mod 5 3 4

2

sub_mod :: Integer -> Integer -> Integer -> Integer

Subtracts the third parameter from the second, mod the first. E.g.:

sub_mod 5 16 7

4

mul_mod :: Integer -> Integer -> Integer -> Integer

Multiplies the second parameter by the third, mod the first. E.g.:

mul_mod 5 2 4

3

div_mod :: Integer -> Integer -> Integer -> Maybe Integer

Divides the second parameter by the third, mod the first. More explicitly, it multiplies the second by the multiplicative inverse of the third, mod the first. E.g.:

div_mod 5 16 7

Just 3

Note that only elements coprime to the modulus will have inverses; in cases that do not match this criterion, we return Nothing.

pow_mod :: Integer -> Integer -> Integer -> Integer

O(log_2 e) Raises base b (2nd param) to exponent e (3rd param) mod m (1st param). E.g.:

pow_mod 13 2 4

3

multiplicative_inverse :: Integer -> Integer -> Maybe Integer

O(log m) Computes the multiplicative inverse of the second parameter, in the group Z_m, where m/ is the first parameter. E.g.:

multiplicative_inverse 13 6

Just 11

That is, 6 * 11 = 66, and 66 mod 13 == 1 . Note that only elements coprime to the modulus will have inverses; in cases that do not match this criterion, we return Nothing.

Assorted functions

fibs :: [Integer]

An infinite list of the Fibonacci numbers.

sqrt_perfect_square :: Integer -> Integer

Takes the square root of a perfect square.

is_int :: Double -> Bool

Returns whether a Double value is an integer. For example, 16.0 :: Double is an integer, but not 16.1.

is_power_of_int :: Integer -> Integer -> Bool

O(1) Calculates whether n is the e^th power of any integer, where n is the first parameter and e is the second.

double_to_int :: Double -> Integer

Converts a Double to an Integer.

num_digits :: Integer -> Integer

O(log_10(n)) Calculates the number of digits in an integer. Relies on logBase, so gives wrong answer for very large n.

tri_area :: Integer -> Integer -> Integer -> Double

O(1) Area of a triangle, where the parameters are the edge lengths (Heron's formula).

tri_area_double :: Double -> Double -> Double -> Double

O(1) Area of a triangle, where the parameters are the edge lengths (Heron's formula).

solve_linear_system :: [[Double]] -> [Double] -> [Double]

Solves a given system of linear equations. Can be subject to rounding errors for large numbers in the input. Here's an example:

solve_linear_system [[2, 3, 4],[6, -3, 9],[2, 0, 1]] [20, -6, 8]

4.999999999999999,6.0,-2.0