Copyright | (c) Brett Wines 2014 |
---|---|

License | BSD-style |

Maintainer | bgwines@cs.stanford.edu |

Stability | experimental |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

Assorted mathematical functions.

- primes :: [Integer]
- composites :: [Integer]
- prime :: Integer -> Bool
- prime_miller_rabin :: Integer -> Bool
- coprime :: Integral a => a -> a -> Bool
- euler_phi :: Integer -> Integer
- factor :: Integer -> [Integer]
- factor_number_is_perfect_square :: Integer -> [Integer]
- divisors :: Integer -> [Integer]
- divisors_number_is_perfect_square :: Integer -> [Integer]
- num_divisors :: Integer -> Integer
- num_divisors_of_n_squared_leq_n :: Integer -> Integer
- irrational_squares :: [Integer]
- sqrt_convergents :: Integer -> [(Integer, Integer)]
- continued_fraction_sqrt :: Integer -> [Integer]
- continued_fraction_sqrt_infinite :: Integer -> [Integer]
- square :: Integral a => a -> Bool
- add_mod :: Integral a => a -> a -> a -> a
- sub_mod :: Integral a => a -> a -> a -> a
- mul_mod :: Integral a => a -> a -> a -> a
- div_mod :: forall a. Integral a => a -> a -> a -> Maybe a
- div_mod_prime :: Integral a => a -> a -> a -> a
- pow_mod :: forall a. Integral a => a -> a -> a -> a
- multiplicative_inverse :: forall a. Integral a => a -> a -> Maybe a
- fibs :: [Integer]
- sqrt_perfect_square :: Integer -> Integer
- is_int :: Double -> Bool
- is_power_of_int :: Integer -> Integer -> Bool
- double_to_int :: Double -> Integer
- num_digits :: Integer -> Integer
- tri_area :: Integer -> Integer -> Integer -> Double
- tri_area_double :: Double -> Double -> Double -> Double
- solve_linear_system :: [[Double]] -> [Double] -> [Double]

# Prime numbers and division

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

composites :: [Integer] Source

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

prime :: Integer -> Bool 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. Returns whether the parameter is a prime number.

prime_miller_rabin :: Integer -> Bool Source

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

euler_phi :: Integer -> Integer Source

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

factor_number_is_perfect_square :: 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.

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.

divisors_number_is_perfect_square :: 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.

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

num_divisors_of_n_squared_leq_n :: 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.

# Square roots

irrational_squares :: [Integer] Source

An infinite list of integers with irrational square roots.

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

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

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

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

# 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

sqrt_perfect_square :: Integer -> Integer Source

Takes the square root of a perfect square.

is_int :: Double -> Bool Source

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 Source

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

Converts a `Double`

to an `Integer`

.

num_digits :: Integer -> Integer Source

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

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

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

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