Calculator

Description

This module contains some commonly needed functions that makes a Haskell interpreter an ideal CS calculator.

Synopsis

• hex :: (Integral n, Show n) => n -> String
• oct :: (Integral n, Show n) => n -> String
• bin :: (Integral n, Show n) => n -> String
• powmod :: (Integral n, Integral e) => n -> n -> e -> n
• fiblist :: [Integer]
• fib :: (Integral b, Num a) => b -> a
• primelist :: [Integer]
• isprime :: Integer -> Bool
• euclid :: Integral a => a -> a -> (a, a, a)
• binomial :: (Integral b, Num a) => b -> [a]
• choose :: Num a => Int -> Int -> a
• ack :: (Num a, Eq a) => a -> a -> a
• cfsqrt :: Integral a => a -> [a]

# Display non-negative integer in bases

hex :: (Integral n, Show n) => n -> String

oct :: (Integral n, Show n) => n -> String

non-negative integer to octal string

bin :: (Integral n, Show n) => n -> String

non-negative integer to binary string

# Exponentiation with mod

powmod :: (Integral n, Integral e) => n -> n -> e -> n

`powmod m b e` = b^e modulo m

# Fibonacci numbers

The fibonacci numbers. f0 = 0, f1 = 1, f(n+2) = f(n+1) + f(n). We seem to use 0 as the starting index, but notice it is compatible with the usual 1-based definition, since f2=1.

fiblist :: [Integer]

The infinite list of fibonacci numbers.

fib :: (Integral b, Num a) => b -> a

An efficient recursive algorithm for computing one fibonacci number.

• f (2k+1) = (f k)^2 + (f (k+1))^2
• f (2k) = 2 * f k * f (k+1) - (f k)^2

# Primes

primelist :: [Integer]

The infinite list of prime numbers from 2 in increasing order.

isprime :: Integer -> Bool

Whether a number is prime. This looks for the number in the prime list.

# Extended Euclidean algorithm

euclid :: Integral a => a -> a -> (a, a, a)

`euclid a b` performs the extended euclidean algorithm to find (d,m,n) such that a*m+b*n = d = gcd(a,b).

# Binomial coefficients, combination (nCr)

binomial :: (Integral b, Num a) => b -> [a]

Binomial coefficients of (x+1)^n.

choose :: Num a => Int -> Int -> a

nCr.

# Ackermann

The horror!

ack :: (Num a, Eq a) => a -> a -> a

Please don't use the Ackermann function!

# Continued fractions of square roots

cfsqrt :: Integral a => a -> [a]

Continued fraction of square root of n.