Zora-1.2.0: Graphing library wrapper + assorted useful functions

Copyright(c) Brett Wines 2014
LicenseBSD-style
Maintainerbgwines@cs.stanford.edu
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell98

Zora.Math

Contents

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

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.

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.

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]