Math

Approximate Cumulative Distribution Function

Calculates the cumulative distribution function (CDF) of the normal distribution based on an approximation by George Marsaglia: Marsaglia, George (2004). “Evaluating the Normal Distribution”. Journal of Statistical Software 11 (4).

16 digit precision for 300 iterations when x = 10.

Equation:

f(x) = 1/2 + pdf(x) * (x + (x^3/3) + (x^5/3*5) + (x^7/3*7) + ...)

algorithms.math.approx_cdf.cdf(x, iterations=300)

Calculates the cumulative distribution function of the normal distribution. Uses a taylor exponent to calculate this.

Parameters:

• x – An integer that represents the taylor exponent.
• iterations – An integer representing the number of iterations.

Return type:

The normal distribution

Extended Greatest Common Divisor

Implementation of the extended greatest common divisor algorithm.

Pseudo Code: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

algorithms.math.extended_gcd.extended_gcd(p, q)

Find the greatest common divisor and returns them.

Parameters:

• a – An integer.
• b – An integer.

Return type:

A tuple representing the greatest common divisor.

Lowest Common Multiple

Simple implementation of the Lowest Common Multiple Algorithm.

Pseudo Code: https://en.wikipedia.org/wiki/Least_common_multiple

algorithms.math.lcm.lcm(a, b)

Simple version of lcm, that does not have any dependencies.

Parameters:

• a – Integer
• b – Integer

Return type:

The lowest common multiple of integers a and b

Primality Test

Implementation of a Primality Test that uses a cache to improve performance.

algorithms.math.primality_test.is_prime(number, cache=True)

Takes number and determines if it is prime.

Parameters:

• number – The integer to be tested for primality.
• cache – A boolean to determine if a cache should be used to improve performance.

Return type:

A boolean that signifies if number is prime.

Sieve of Atkin

It is an optimized version of the ancient sieve of Eratosthenes which does some preliminary work and then marks off multiples of the square of each prime, rather than multiples of the prime itself. It was created in 2004 by A. O. L. Atkin and Daniel J. Bernstein.

Time Complexity: O(n/log log n)

Pseudocode: https://en.wikipedia.org/wiki/Sieve_of_Atkin

algorithms.math.sieve_atkin.atkin(limit)

Parameters:limit – The upper limit in which to find all primes less than this value.

Sieve of Eratosthenes

Is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).

Time Complexity: O(n log log n)

Pseudocode: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

algorithms.math.sieve_eratosthenes.eratosthenes(end, start=2, return_boolean=False)

Finds all primes < end.

Parameters:

• end – An integer. The upper limit of the range to look for primes.
• start – An integer. The start of the range to look for primes.
• return_boolean – A boolean. Represents the type of return type.

Return type:

Depending on return_boolean either returns boolean and primes or just the primes.

Standard Normal Probability Density Function

Calculates the normal distribution’s probability density function (PDF). Calculates Standard normal pdf for mean=0, std_dev=1.

Equation: f(x) = 1 / sqrt(2*pi) * e^(-(x-mean)^2/ 2*std_dev^2)

algorithms.math.std_normal_pdf.pdf(x, mean=0, std_dev=1)

Calculates the normal distribution’s probability density function.

Parameters:

• x – An integer.
• mean – An integer.
• std_dev – An integer.

Return type:

The normal distribution