continued-fractions-0.10.0.1: Continued fractions.

Safe HaskellSafe
LanguageHaskell2010

Math.ContinuedFraction

Synopsis

Documentation

data CF a Source #

A continued fraction. Constructed by cf or gcf.

Instances
Functor CF Source # 
Instance details

Defined in Math.ContinuedFraction

Methods

fmap :: (a -> b) -> CF a -> CF b #

(<$) :: a -> CF b -> CF a #

Show a => Show (CF a) Source # 
Instance details

Defined in Math.ContinuedFraction

Methods

showsPrec :: Int -> CF a -> ShowS #

show :: CF a -> String #

showList :: [CF a] -> ShowS #

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 #

Apply an equivalence transformation that sets the partial numerators of a CF to the specfied values. If the input list is too short, the rest of the CF will be unscaled.

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

Apply an equivalence transformation that sets the partial denominators of a CF to the specfied values. If the input list is too short, the rest of the CF will be unscaled.

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

Computes the even and odd parts, respectively, of a CF. These are new CFs that have the even-indexed and odd-indexed convergents of the original, respectively.

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

Computes the even part of a CF (that is, a new CF whose convergents are the even-indexed convergents of the original).

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

Computes the odd part of a CF (that is, a new CF whose convergents are the odd-indexed convergents of the original).

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.

sumPartialProducts :: Num a => [a] -> CF a Source #

Euler's formula for computing sum (scanl1 (*) xs). Successive convergents of the resulting CF are successive partial sums in the series.