Copyright	© 2014 Johan Kiviniemi
License	MIT
Maintainer	Johan Kiviniemi <devel@johan.kiviniemi.name>
Stability	provisional
Portability	ViewPatterns
Safe Haskell	None
Language	Haskell2010

Numeric.QuadraticIrrational

Contents

Constructors and deconstructors
Lenses
Numerical operations
Continued fractions

Description

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, …]

Synopsis

Constructors and deconstructors

data QI Source

(a + b √c) / d

Instances

Eq QI
Ord QI
Read QI
Show QI

qi Source

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

The fractions are reduced:

>>> qi 30 40 5 60
qi 3 4 5 6

If b = 0 then c is zeroed and vice versa:

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

>>> qi 3 42 0 1
qi 3 0 0 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 0 1

qi' Source

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

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

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 -> (Rational -> Rational -> Integer -> a) -> a Source

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)

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

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 -> (Rational, Rational, Integer) Source

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

>>> unQI' (qi' 0.5 0.7 2)
(1 % 2,7 % 10,2)

Lenses

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

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)

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

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

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)

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

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

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)

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

_qiA :: Lens' QI Integer Source

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

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

_qiB :: Lens' QI Integer Source

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

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

_qiC :: Lens' QI Integer Source

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

>>> over _qiC (+ 10) (qi 3 4 5 6)
qi 3 4 15 6

_qiD :: Lens' QI Integer Source

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

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

Numerical operations

qiZero :: QI Source

The constant zero.

>>> qiZero
qi 0 0 0 1

qiOne :: QI Source

The constant one.

>>> qiOne
qi 1 0 0 1

qiIsZero :: QI -> Bool Source

Check if the value is zero.

>>> map qiIsZero [qiZero, qiOne, qiSubR (qi 7 0 0 2) 3.5]
[True,False,True]

qiToFloat :: Floating a => QI -> a Source

Convert a QI number into a Floating one.

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

qiAddI :: QI -> Integer -> QI Source

Add an Integer to a QI.

>>> qi 3 4 5 6 `qiAddI` 1
qi 9 4 5 6

qiSubI :: QI -> Integer -> QI Source

Subtract an Integer from a QI.

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

qiMulI :: QI -> Integer -> QI Source

Multiply a QI by an Integer.

>>> qi 3 4 5 6 `qiMulI` 2
qi 3 4 5 3

qiDivI :: QI -> Integer -> QI Source

Divice a QI by an Integer.

>>> qi 3 4 5 6 `qiDivI` 2
qi 3 4 5 12

qiAddR :: QI -> Rational -> QI Source

Add a Rational to a QI.

>>> qi 3 4 5 6 `qiAddR` 1.2
qi 51 20 5 30

qiSubR :: QI -> Rational -> QI Source

Subtract a Rational from a QI.

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

qiMulR :: QI -> Rational -> QI Source

Multiply a QI by a Rational.

>>> qi 3 4 5 6 `qiMulR` 0.5
qi 3 4 5 12

qiDivR :: QI -> Rational -> QI Source

Divice a QI by a Rational.

>>> qi 3 4 5 6 `qiDivR` 0.5
qi 3 4 5 3

qiNegate :: QI -> QI Source

Negate a QI.

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

qiRecip :: QI -> Maybe QI Source

Compute the reciprocal of a QI.

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

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

>>> qiRecip qiZero
Nothing

qiAdd :: QI -> QI -> Maybe QI Source

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

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

>>> 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 Source

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

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

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

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

qiMul :: QI -> QI -> Maybe QI Source

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

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

>>> qi 3 4 5 6 `qiMul` qiOne
Just (qi 3 4 5 6)

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

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

qiDiv :: QI -> QI -> Maybe QI Source

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

>>> qi 3 4 5 6 `qiDiv` qiZero
Nothing

>>> qi 3 4 5 6 `qiDiv` qiOne
Just (qi 3 4 5 6)

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

>>> 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 Source

Exponentiate a QI to an Integer power.

>>> qi 3 4 5 6 `qiPow` 0
qi 1 0 0 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

qiFloor :: QI -> Integer Source

Compute the floor of a QI.

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

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

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

Continued fractions

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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