Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

## Synopsis

- data CF a
- cf :: a -> [a] -> CF a
- gcf :: a -> [(a, a)] -> CF a
- asCF :: Fractional a => CF a -> (a, [a])
- asGCF :: (Num a, Eq a) => CF a -> (a, [(a, a)])
- truncateCF :: Int -> CF a -> CF a
- equiv :: (Num a, Eq a) => [a] -> CF a -> CF a
- setNumerators :: (Fractional a, Eq a) => [a] -> CF a -> CF a
- setDenominators :: (Fractional a, Eq a) => [a] -> CF a -> CF a
- partitionCF :: (Fractional a, Eq a) => CF a -> (CF a, CF a)
- evenCF :: (Fractional a, Eq a) => CF a -> CF a
- oddCF :: (Fractional a, Eq a) => CF a -> CF a
- convergents :: (Fractional a, Eq a) => CF a -> [a]
- steed :: (Fractional a, Eq a) => CF a -> [a]
- lentz :: (Fractional a, Eq a) => CF a -> [a]
- lentzWith :: (Fractional a, Eq a) => (a -> b) -> (b -> b -> b) -> (b -> b) -> CF a -> [b]
- modifiedLentz :: (Fractional a, Eq a) => a -> CF a -> [[a]]
- modifiedLentzWith :: (Fractional a, Eq a) => (a -> b) -> (b -> b -> b) -> (b -> b) -> a -> CF a -> [[b]]
- sumPartialProducts :: Num a => [a] -> CF a

# Documentation

cf :: a -> [a] -> CF a Source #

Construct a continued fraction from its first term and the partial denominators in its canonical form, which is the form where all the partial numerators are 1.

`cf a [b,c,d]`

corresponds to `a + (b / (1 + (c / (1 + d))))`

,
or to `GCF a [(1,b),(1,c),(1,d)]`

.

gcf :: a -> [(a, a)] -> CF a Source #

Construct a continued fraction from its first term, its partial numerators and its partial denominators.

`gcf b0 [(a1,b1), (a2,b2), (a3,b3)]`

corresponds to
`b0 + (a1 / (b1 + (a2 / (b2 + (a3 / b3)))))`

asCF :: Fractional a => CF a -> (a, [a]) Source #

Extract the partial denominators of a `CF`

, normalizing it if necessary so
that all the partial numerators are 1.

asGCF :: (Num a, Eq a) => CF a -> (a, [(a, a)]) Source #

Extract all the partial numerators and partial denominators of a `CF`

.

truncateCF :: Int -> CF a -> CF a Source #

Truncate a `CF`

to the specified number of partial numerators and denominators.

equiv :: (Num a, Eq a) => [a] -> CF a -> CF a Source #

Apply an equivalence transformation, multiplying each partial denominator
with the corresponding element of the supplied list and transforming
subsequent partial numerators and denominators as necessary. If the list
is too short, the rest of the `CF`

will be unscaled.

setNumerators :: (Fractional a, Eq a) => [a] -> CF a -> CF a Source #

setDenominators :: (Fractional a, Eq a) => [a] -> CF a -> CF a Source #

partitionCF :: (Fractional a, Eq a) => CF a -> (CF a, CF a) Source #

convergents :: (Fractional a, Eq a) => CF a -> [a] Source #

Evaluate the convergents of a continued fraction using the fundamental recurrence formula:

A0 = b0, B0 = 1

A1 = b1b0 + a1, B1 = b1

A{n+1} = b{n+1}An + a{n+1}A{n-1}

B{n+1} = b{n+1}Bn + a{n+1}B{n-1}

The convergents are then `Xn = An/Bn`

steed :: (Fractional a, Eq a) => CF a -> [a] Source #

Evaluate the convergents of a continued fraction using Steed's method.
Only valid if the denominator in the following recurrence for D_i never
goes to zero. If this method blows up, try `modifiedLentz`

.

D1 = 1/b1

D{i} = 1 / (b{i} + a{i} * D{i-1})

dx1 = a1 / b1

dx{i} = (b{i} * D{i} - 1) * dx{i-1}

x0 = b0

x{i} = x{i-1} + dx{i}

The convergents are given by `scanl (+) b0 dxs`

lentz :: (Fractional a, Eq a) => CF a -> [a] Source #

Evaluate the convergents of a continued fraction using Lentz's method.
Only valid if the denominators in the following recurrence never go to
zero. If this method blows up, try `modifiedLentz`

.

C1 = b1 + a1 / b0

D1 = 1/b1

C{n} = b{n} + a{n} / C{n-1}

D{n} = 1 / (b{n} + a{n} * D{n-1})

The convergents are given by `scanl (*) b0 (zipWith (*) cs ds)`

lentzWith :: (Fractional a, Eq a) => (a -> b) -> (b -> b -> b) -> (b -> b) -> CF a -> [b] Source #

Evaluate the convergents of a continued fraction using Lentz's method,
mapping the terms in the final product to a new group before performing
the final multiplications. A useful group, for example, would be logarithms
under addition. In `lentzWith f op inv`

, the arguments are:

`f`

, a group homomorphism (eg,`log`

) from {`a`

,(*),`recip`

} to the group in which you want to perform the multiplications.`op`

, the group operation (eg., (+)).`inv`

, the group inverse (eg.,`negate`

).

The `lentz`

function, for example, is given by the identity homomorphism:
`lentz`

= `lentzWith id (*) recip`

.

The original motivation for this function is to allow computation of
the natural log of very large numbers that would overflow with the naive
implementation in `lentz`

. In this case, the arguments would be `log`

, (+),
and `negate`

, respectively.

In cases where terms of the product can be negative (i.e., the sequence of convergents contains negative values), the following definitions could be used instead:

signLog x = (signum x, log (abs x)) addSignLog (xS,xL) (yS,yL) = (xS*yS, xL+yL) negateSignLog (s,l) = (s, negate l)

modifiedLentz :: (Fractional a, Eq a) => a -> CF a -> [[a]] Source #

Evaluate the convergents of a continued fraction using Lentz's method,
(see `lentz`

) with the additional rule that if a denominator ever goes
to zero, it will be replaced by a (very small) number of your choosing,
typically 1e-30 or so (this modification was proposed by Thompson and
Barnett).

Additionally splits the resulting list of convergents into sublists, starting a new list every time the 'modification' is invoked.

modifiedLentzWith :: (Fractional a, Eq a) => (a -> b) -> (b -> b -> b) -> (b -> b) -> a -> CF a -> [[b]] Source #

`modifiedLentz`

with a group homomorphism (see `lentzWith`

, it bears the
same relationship to `lentz`

as this function does to `modifiedLentz`

,
and solves the same problems). Alternatively, `lentzWith`

with the same
modification to the recurrence as `modifiedLentz`

.