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

An implementation of quadratic irrationals with support for conversion from and to periodic 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 some quadratic equations – the quadratic formula has a familiar shape.

A continued fraction is a number that can be expressed in the form

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

alternatively expressed using the notation

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

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

Every finite continued fraction represents a rational number and every infinite, periodic continued fraction 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
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) 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) 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])

module Numeric.QuadraticIrrational.CyclicList