Numeric.QuadraticIrrational

A library for exact computation with quadratic irrationals with support for exact conversion from and to (potentially periodic) simple continued fractions.

A quadratic irrational is a number that can be expressed in the form

(a + b √c) / d

where a, b and d are integers and c is a square-free natural number.

Some examples of such numbers are

• 7/2,
• √2,
• (1 + √5)/2 (the golden ratio),
• solutions to quadratic equations with rational constants – the quadratic formula has a familiar shape.

A simple continued fraction is a number expressed in the form

a + 1/(b + 1/(c + 1/(d + 1/(e + …))))

or alternatively written as

[a; b, c, d, e, …]

where a is an integer and b, c, d, e, … are positive integers.

Every finite SCF represents a rational number and every infinite, periodic SCF represents a quadratic irrational.

3.5      = [3; 2]
(1+√5)/2 = [1; 1, 1, 1, …]
√2       = [1; 2, 2, 2, …]

Constructors and deconstructors

data QI

(a + b √c)

Instances

Eq QI

Defined in Numeric.QuadraticIrrational

Methods

(==) :: QI -> QI -> Bool

(/=) :: QI -> QI -> Bool

Read QI

Defined in Numeric.QuadraticIrrational

Methods

readsPrec :: Int -> ReadS QI

readList :: ReadS [QI]

readPrec :: ReadPrec QI

readListPrec :: ReadPrec [QI]

Show QI

Defined in Numeric.QuadraticIrrational

Methods

showsPrec :: Int -> QI -> ShowS

show :: QI -> String

showList :: [QI] -> ShowS

qi

Arguments

:: Integer

a

-> Integer

b

-> Integer

c

-> Integer

d

-> QI

Given a, b, c and d such that n = (a + b √c)/d, constuct a QI corresponding to n.

>>> qi 3 4 5 6
qi 3 4 5 6

>>> qi 3 0 42 1
qi 3 0 42 1

>>> qi 1 1 (-1) 1
qi 1 1 (-1) 1

The fractions are reduced:

>>> qi 30 40 5 60
qi 3 4 5 6
>>> qi (-30) (-40) (-5) (-60)
qi 3 4 (-5) 6

If c = 0 then b is zeroed and c is put equal to 2:

>>> qi 3 42 0 1
qi 3 0 2 1

The b √c term is simplified:

>>> qi 0 1 (5*5*6) 1
qi 0 5 6 1

If c = 1 (after simplification) then b is moved to a:

>>> qi 1 5 (2*2) 1
qi 11 0 2 1

qi'

Arguments

:: Rational

a

-> Rational

b

-> Integer

c

-> QI

Given a, b and c such that n = a + b √c, constuct a QI corresponding to n.

>>> qi' 0.5 0.7 2
qi 5 7 2 10
>>> qi' 0.3 0.4 (-3)
qi 3 4 (-3) 10

runQI :: QI -> (Integer -> Integer -> Integer -> Integer -> a) -> a

Given n and f such that n = (a + b √c)/d, run f a b c d.

>>> runQI (qi 3 4 5 6) (\a b c d -> (a,b,c,d))
(3,4,5,6)
>>> runQI (qi 1 1 (-1) 1) (\a b c d -> (a,b,c,d))
(1,1,-1,1)

runQI' :: QI -> (Rational -> Rational -> Integer -> a) -> a

Given n and f such that n = a + b √c, run f a b c.

>>> runQI' (qi' 0.5 0.7 2) (\a b c -> (a, b, c))
(1 % 2,7 % 10,2)
>>> runQI' (qi' 0.3 0.4 (-3)) (\a b c -> (a, b, c))
(3 % 10,2 % 5,-3)

unQI :: QI -> (Integer, Integer, Integer, Integer)

Given n such that n = (a + b √c)/d, return (a, b, c, d).

>>> unQI (qi 3 4 5 6)
(3,4,5,6)
>>> unQI (qi 1 1 (-1) 1)
(1,1,-1,1)

unQI' :: QI -> (Rational, Rational, Integer)

Given n such that n = a + b √c, return (a, b, c).

>>> unQI' (qi' 0.5 0.7 2)
(1 % 2,7 % 10,2)
>>> unQI' (qi' 0.3 0.4 (-3))
(3 % 10,2 % 5,-3)

Lenses

_qi :: Lens' QI (Integer, Integer, Integer, Integer)

Given a QI corresponding to n = (a + b √c)/d, access (a, b, c, d).

>>> view _qi (qi 3 4 5 6)
(3,4,5,6)
>>> view _qi (qi 1 1 (-1) 1)
(1,1,-1,1)

>>> over _qi (\(a,b,c,d) -> (a+10, b+10, c+10, d+10)) (qi 3 4 5 6)
qi 13 14 15 16
>>> over _qi (\(a,b,c,d) -> (a+10, b+10, c+10, d+10)) (qi 1 1 (-1) 1)
qi 4 0 2 1

_qi' :: Lens' QI (Rational, Rational, Integer)

Given a QI corresponding to n = a + b √c, access (a, b, c).

>>> view _qi' (qi' 0.5 0.7 2)
(1 % 2,7 % 10,2)
>>> view _qi' (qi' 0.3 0.4 (-3))
(3 % 10,2 % 5,-3)

>>> over _qi' (\(a,b,c) -> (a/5, b/6, c*3)) (qi 3 4 5 6)
qi 9 10 15 90
>>> over _qi' (\(a,b,c) -> (a/5, b/6, c*3)) (qi 1 1 (-1) 1)
qi 6 5 (-3) 30

_qiABD :: Lens' QI (Integer, Integer, Integer)

Given a QI corresponding to n = (a + b √c)/d, access (a, b, d). Avoids having to simplify b √c upon reconstruction.

>>> view _qiABD (qi 3 4 5 6)
(3,4,6)
>>> view _qiABD (qi 1 1 (-1) 1)
(1,1,1)

>>> over _qiABD (\(a,b,d) -> (a+10, b+10, d+10)) (qi 3 4 5 6)
qi 13 14 5 16
>>> over _qiABD (\(a,b,d) -> (a+10, b+10, d+10)) (qi 1 1 (-1) 1)
qi 1 1 (-1) 1

_qiA :: Lens' QI Integer

Given a QI corresponding to n = (a + b √c)/d, access a. It is more efficient to use _qi or _qiABD when modifying multiple terms at once.

>>> view _qiA (qi 3 4 5 6)
3
>>> view _qiA (qi 1 1 (-1) 1)
1

>>> over _qiA (+ 10) (qi 3 4 5 6)
qi 13 4 5 6
>>> over _qiA (+ 10) (qi 1 1 (-1) 1)
qi 11 1 (-1) 1

_qiB :: Lens' QI Integer

Given a QI corresponding to n = (a + b √c)/d, access b. It is more efficient to use _qi or _qiABD when modifying multiple terms at once.

>>> view _qiB (qi 3 4 5 6)
4
>>> view _qiB (qi 1 1 (-1) 1)
1

>>> over _qiB (+ 10) (qi 3 4 5 6)
qi 3 14 5 6
>>> over _qiB (+ 10) (qi 1 1 (-1) 1)
qi 1 11 (-1) 1

_qiC :: Lens' QI Integer

Given a QI corresponding to n = (a + b √c)/d, access c. It is more efficient to use _qi or _qiABD when modifying multiple terms at once.

>>> view _qiC (qi 3 4 5 6)
5
>>> view _qiC (qi 1 1 (-1) 1)
-1

>>> over _qiC (+ 10) (qi 3 4 5 6)
qi 3 4 15 6
>>> over _qiC (+ 10) (qi 1 1 (-1) 1)
qi 4 0 2 1

_qiD :: Lens' QI Integer

Given a QI corresponding to n = (a + b √c)/d, access d. It is more efficient to use _qi or _qiABD when modifying multiple terms at once.

>>> view _qiD (qi 3 4 5 6)
6
>>> view _qiD (qi 1 1 (-1) 1)
1

>>> over _qiD (+ 10) (qi 3 4 5 6)
qi 3 4 5 16
>>> over _qiD (+ 10) (qi 1 1 (-1) 1)
qi 1 1 (-1) 11

Numerical operations

qiIsZero :: QI -> Bool

Check if the value is zero.

>>> map qiIsZero [qi 0 0 0 1, qi 1 0 0 1, qiSubR (qi 7 0 0 2) 3.5, qi 0 9 0 1, qi 0 0 (-1) 5]
[True,False,True,True,True]

qiToFloat :: Floating a => QI -> a

Convert a QI number into a Floating one. Returns NaN for imaginary values.

>>> qiToFloat (qi 3 4 5 6) == ((3 + 4 * sqrt 5)/6 :: Double)
True
>>> qiToFloat (qi 2 3 (-5) 7)
NaN

qiAddI :: QI -> Integer -> QI

Add an Integer to a QI.

>>> qi 3 4 5 6 `qiAddI` 1
qi 9 4 5 6
>>> qi 1 1 (-1) 1 `qiAddI` 1
qi 2 1 (-1) 1

qiSubI :: QI -> Integer -> QI

Subtract an Integer from a QI.

>>> qi 3 4 5 6 `qiSubI` 1
qi (-3) 4 5 6
>>> qi 1 1 (-1) 1 `qiSubI` 1
qi 0 1 (-1) 1

qiMulI :: QI -> Integer -> QI

Multiply a QI by an Integer.

>>> qi 3 4 5 6 `qiMulI` 2
qi 3 4 5 3
>>> qi 1 1 (-1) 1 `qiMulI` 2
qi 2 2 (-1) 1

qiDivI :: QI -> Integer -> QI

Divide a QI by an Integer.

>>> qi 3 4 5 6 `qiDivI` 2
qi 3 4 5 12
>>> qi 1 1 (-1) 1 `qiDivI` 2
qi 1 1 (-1) 2

qiAddR :: QI -> Rational -> QI

Add a Rational to a QI.

>>> qi 3 4 5 6 `qiAddR` 1.2
qi 51 20 5 30
>>> qi 1 1 (-1) 1 `qiAddR` 1.2
qi 11 5 (-1) 5

qiSubR :: QI -> Rational -> QI

Subtract a Rational from a QI.

>>> qi 3 4 5 6 `qiSubR` 1.2
qi (-21) 20 5 30
>>> qi 1 1 (-1) 1 `qiSubR` 1.2
qi (-1) 5 (-1) 5

qiMulR :: QI -> Rational -> QI

Multiply a QI by a Rational.

>>> qi 3 4 5 6 `qiMulR` 0.5
qi 3 4 5 12
>>> qi 1 1 (-1) 1 `qiMulR` 0.5
qi 1 1 (-1) 2

qiDivR :: QI -> Rational -> QI

Divide a QI by a Rational.

>>> qi 3 4 5 6 `qiDivR` 0.5
qi 3 4 5 3
>>> qi 1 1 (-1) 1 `qiDivR` 0.5
qi 2 2 (-1) 1

qiNegate :: QI -> QI

Negate a QI.

>>> qiNegate (qi 3 4 5 6)
qi (-3) (-4) 5 6
>>> qiNegate (qi 1 1 (-1) 1)
qi (-1) (-1) (-1) 1

qiRecip :: QI -> Maybe QI

Compute the reciprocal of a QI.

>>> qiRecip (qi 5 0 0 2)
Just (qi 2 0 2 5)

>>> qiRecip (qi 0 1 5 2)
Just (qi 0 2 5 5)

>>> qiRecip (qi 1 1 (-1) 1)
Just (qi 1 (-1) (-1) 2)

>>> qiRecip (qi 0 0 0 1)
Nothing

qiAdd :: QI -> QI -> Maybe QI

Add two QIs if the square root terms are the same or zeros.

>>> qi 3 4 5 6 `qiAdd` qi 1 0 5 1
Just (qi 9 4 5 6)

>>> qi 3 4 5 6 `qiAdd` qi 3 4 5 6
Just (qi 3 4 5 3)

>>> qi 3 4 (-5) 6 `qiAdd` qi 3 4 (-5) 6
Just (qi 3 4 (-5) 3)

>>> qi 0 1 5 1 `qiAdd` qi 0 1 6 1
Nothing

qiSub :: QI -> QI -> Maybe QI

Subtract two QIs if the square root terms are the same or zeros.

>>> qi 3 4 5 6 `qiSub` qi 1 0 5 1
Just (qi (-3) 4 5 6)

>>> qi 3 4 5 6 `qiSub` qi 3 4 5 6
Just (qi 0 0 5 1)

>>> qi 3 4 (-5) 6 `qiSub` qi 3 4 (-5) 6
Just (qi 0 0 (-5) 1)

>>> qi 0 1 5 1 `qiSub` qi 0 1 6 1
Nothing

qiMul :: QI -> QI -> Maybe QI

Multiply two QIs if the square root terms are the same or zeros.

>>> qi 3 4 5 6 `qiMul` qi 0 0 5 1
Just (qi 0 0 5 1)

>>> qi 3 4 5 6 `qiMul` qi 1 0 5 1
Just (qi 3 4 5 6)

>>> qi 3 4 5 6 `qiMul` qi 3 4 5 6
Just (qi 89 24 5 36)

>>> qi 3 4 (-5) 6 `qiMul` qi 3 4 (-5) 6
Just (qi (-71) 24 (-5) 36)

>>> qi 0 1 5 1 `qiMul` qi 0 1 6 1
Nothing

qiDiv :: QI -> QI -> Maybe QI

Divide two QIs if the square root terms are the same or zeros.

>>> qi 3 4 5 6 `qiDiv` qi 0 0 5 1
Nothing

>>> qi 3 4 5 6 `qiDiv` qi 1 0 5 1
Just (qi 3 4 5 6)

>>> qi 3 4 5 6 `qiDiv` qi 3 4 5 6
Just (qi 1 0 5 1)

>>> qi 3 4 5 6 `qiDiv` qi 0 1 5 1
Just (qi 20 3 5 30)

>>> qi 3 4 (-5) 6 `qiDiv` qi 0 1 (-5) 1
Just (qi 20 (-3) (-5) 30)

>>> qi 0 1 5 1 `qiDiv` qi 0 1 6 1
Nothing

qiPow :: QI -> Integer -> QI

Exponentiate a QI to an Integer power.

>>> qi 3 4 5 6 `qiPow` 0
qi 1 0 5 1

>>> qi 3 4 5 6 `qiPow` 1
qi 3 4 5 6

>>> qi 3 4 5 6 `qiPow` 2
qi 89 24 5 36

>>> qi 1 1 (-1) 1 `qiPow` 4
qi (-4) 0 (-1) 1

qiFloor :: QI -> Integer

Compute the floor of a QI. Throws an error for imaginary values.

>>> qiFloor (qi 10 0 0 2)
5

>>> qiFloor (qi 10 2 2 2)
6

>>> qiFloor (qi 10 2 5 2)
7

>>> qiFloor (qi 1 1 (-1) 1)
*** Exception: ...
...

Continued fractions

continuedFractionToQI :: (Integer, CycList Integer) -> QI

Convert a (possibly periodic) simple continued fraction to a QI.

[2; 2] = 2 + 1/2 = 5/2.

>>> continuedFractionToQI (2,CycList [2] [])
qi 5 0 2 2

The golden ratio is [1; 1, 1, …].

>>> showCReal 1000 (qiToFloat (continuedFractionToQI (1,CycList [] [1])))
"1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678806752087668925017116962070322210432162695486262963136144381497587012203408058879544547492461856953648644492410443207713449470495658467885098743394422125448770664780915884607499887124007652170575179788341662562494075890697040002812104276217711177780531531714101170466659914669798731761356006708748071013179523689427521948435305678300228785699782977834784587822891109762500302696156170025046433824377648610283831268330372429267526311653392473167111211588186385133162038400522216579128667529465490681131715993432359734949850904094762132229810172610705961164562990981629055520852479035240602017279974717534277759277862561943208275051312181562855122248093947123414517022373580577278616008688382952304592647878017889921990270776903895321968198615143780314997411069260886742962267575605231727775203536139362"

>>> continuedFractionToQI (0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82])
qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886

qiToContinuedFraction :: QI -> (Integer, CycList Integer)

Convert a QI into a (possibly periodic) simple continued fraction. Throws an error for imaginary values.

5/2 = 2 + 1/2 = [2; 2].

>>> qiToContinuedFraction (qi 5 0 0 2)
(2,CycList [2] [])

The golden ratio is (1 + √5)/2. We can compute the corresponding PCF.

>>> qiToContinuedFraction (qi 1 1 5 2)
(1,CycList [] [1])

>>> qiToContinuedFraction (qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886)
(0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82])

>>> qiToContinuedFraction (qi 1 1 (-1) 1)
*** Exception: ...
...

continuedFractionApproximate :: Foldable f => Int -> (Integer, f Integer) -> Rational

Compute a rational partial evaluation of a simple continued fraction.

Rational approximations that converge toward φ:

>>> [ continuedFractionApproximate n (1, repeat 1) | n <- [0,3..18] ]
[1 % 1,5 % 3,21 % 13,89 % 55,377 % 233,1597 % 987,6765 % 4181]

module Numeric.QuadraticIrrational.CyclicList