Zora-1.2.0: Graphing library wrapper + assorted useful functions

Zora.Math

Description

Assorted mathematical functions.

Synopsis

# Prime numbers and division

primes :: [Integer] Source

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

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

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.

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 :: Integral a => a -> a -> Bool Source

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

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

factor :: Integer -> [Integer] Source

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.

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] Source

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.

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.

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.

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

An infinite list of integers with irrational square roots.

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).

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

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

square :: Integral a => a -> Bool Source

Determines whether the given integer is a square number.

# Modular arithmetic

add_mod :: Integral a => a -> a -> a -> a Source

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

`add_mod 5 3 4`
`2`

sub_mod :: Integral a => a -> a -> a -> a Source

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

`sub_mod 5 16 7`
`4`

mul_mod :: Integral a => a -> a -> a -> a Source

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

`mul_mod 5 2 4`
`3`

div_mod :: forall a. Integral a => a -> a -> a -> Maybe a Source

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.

div_mod_prime :: Integral a => a -> a -> a -> a Source

Like `div_mod`, but with the assurance that the modulus is prime (i.e. denominator will have an inverse). Thus, the returnvalue doesn't need to be wrapped in a `Maybe`.

pow_mod :: forall a. Integral a => a -> a -> a -> a Source

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 :: forall a. Integral a => a -> a -> Maybe a Source

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] Source

An infinite list of the Fibonacci numbers.

Takes the square root of a perfect square.

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

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

Converts a `Double` to an `Integer`.

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

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

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

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

Solves a given system of linear equations. Can be subject to rounding errors. 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]`