arithmoi- Efficient basic number-theoretic functions.

Copyright(c) 2011 Daniel Fischer
MaintainerDaniel Fischer <>
PortabilityNon-portable (GHC extensions)
Safe HaskellSafe



Efficient calculation of linear recurrent sequences, including Fibonacci and Lucas sequences.



factorial :: (Num a, Enum a) => [a] Source #

Infinite zero-based table of factorials.

> take 5 factorial

The time-and-space behaviour of factorial is similar to described in Math.NumberTheory.Recurrencies.Bilinear.

fibonacci :: Int -> Integer Source #

fibonacci k calculates the k-th Fibonacci number in O(log (abs k)) steps. The index may be negative. This is efficient for calculating single Fibonacci numbers (with large index), but for computing many Fibonacci numbers in close proximity, it is better to use the simple addition formula starting from an appropriate pair of successive Fibonacci numbers.

fibonacciPair :: Int -> (Integer, Integer) Source #

fibonacciPair k returns the pair (F(k), F(k+1)) of the k-th Fibonacci number and its successor, thus it can be used to calculate the Fibonacci numbers from some index on without needing to compute the previous. The pair is efficiently calculated in O(log (abs k)) steps. The index may be negative.

lucas :: Int -> Integer Source #

lucas k computes the k-th Lucas number. Very similar to fibonacci.

lucasPair :: Int -> (Integer, Integer) Source #

lucasPair k computes the pair (L(k), L(k+1)) of the k-th Lucas number and its successor. Very similar to fibonacciPair.

generalLucas :: Integer -> Integer -> Int -> (Integer, Integer, Integer, Integer) Source #

generalLucas p q k calculates the quadruple (U(k), U(k+1), V(k), V(k+1)) where U(i) is the Lucas sequence of the first kind and V(i) the Lucas sequence of the second kind for the parameters p and q, where p^2-4q /= 0. Both sequences satisfy the recurrence relation A(j+2) = p*A(j+1) - q*A(j), the starting values are U(0) = 0, U(1) = 1 and V(0) = 2, V(1) = p. The Fibonacci numbers form the Lucas sequence of the first kind for the parameters p = 1, q = -1 and the Lucas numbers form the Lucas sequence of the second kind for these parameters. Here, the index must be non-negative, since the terms of the sequence for negative indices are in general not integers.