|Portability||Non-portable (GHC extensions)|
|Maintainer||Daniel Fischer <email@example.com>|
Generalised Moebius inversion for
Int valued functions.
generalInversion g n evaluates the generalised Moebius inversion of
at the argument
The generalised Moebius inversion implemented here allows an efficient
calculation of isolated values of the function
f : N -> Z if the function
g defined by
g n = sum [f (n `quot` k) | k <- [1 .. n]]
can be cheaply computed. By the generalised Moebius inversion formula, then
f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]
which allows the computation in O(n) steps, if the values of the Moebius function are known. A slightly different formula, used here, does not need the values of the Moebius function and allows the computation in O(n^0.75) steps, using O(n^0.5) memory.
An example of a pair of such functions where the inversion allows a more efficient computation than the direct approach is
f n = number of reduced proper fractions with denominator <= n g n = number of proper fractions with denominator <= n
(a proper fraction is a fraction
0 < n/d < 1). Then
f n is the
cardinality of the Farey sequence of order
n (minus 1 or 2 if 0 and/or
1 are included in the Farey sequence), or the sum of the totients of
2 <= k <= n.
f n is not easily directly computable,
g n = n*(n-1)/2 is very easy to compute, and hence the inversion
gives an efficient method of computing
Int valued functions, unboxed arrays can be used for greater efficiency.
That bears the risk of overflow, however, so be sure to use it only when it's
f n is then computed by
generalInversion g n). Note that when
many values of
f are needed, there are far more efficient methods, this
method is only appropriate to compute isolated values of