Copyright | © 2014 Johan Kiviniemi |
---|---|
License | MIT |
Maintainer | Johan Kiviniemi <devel@johan.kiviniemi.name> |
Stability | provisional |
Portability | FlexibleContexts, ViewPatterns |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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
- data QI
- qi :: Integer -> Integer -> Integer -> Integer -> QI
- qi' :: Rational -> Rational -> Integer -> QI
- runQI :: QI -> (Integer -> Integer -> Integer -> Integer -> a) -> a
- runQI' :: QI -> (Rational -> Rational -> Integer -> a) -> a
- unQI :: QI -> (Integer, Integer, Integer, Integer)
- unQI' :: QI -> (Rational, Rational, Integer)
- _qi :: Lens' QI (Integer, Integer, Integer, Integer)
- _qi' :: Lens' QI (Rational, Rational, Integer)
- _qiABD :: Lens' QI (Integer, Integer, Integer)
- _qiA :: Lens' QI Integer
- _qiB :: Lens' QI Integer
- _qiC :: Lens' QI Integer
- _qiD :: Lens' QI Integer
- qiIsZero :: QI -> Bool
- qiToFloat :: Floating a => QI -> a
- qiAddI :: QI -> Integer -> QI
- qiSubI :: QI -> Integer -> QI
- qiMulI :: QI -> Integer -> QI
- qiDivI :: QI -> Integer -> QI
- qiAddR :: QI -> Rational -> QI
- qiSubR :: QI -> Rational -> QI
- qiMulR :: QI -> Rational -> QI
- qiDivR :: QI -> Rational -> QI
- qiNegate :: QI -> QI
- qiRecip :: QI -> Maybe QI
- qiAdd :: QI -> QI -> Maybe QI
- qiSub :: QI -> QI -> Maybe QI
- qiMul :: QI -> QI -> Maybe QI
- qiDiv :: QI -> QI -> Maybe QI
- qiPow :: QI -> Integer -> QI
- qiFloor :: QI -> Integer
- continuedFractionToQI :: (Integer, CycList Integer) -> QI
- qiToContinuedFraction :: QI -> (Integer, CycList Integer)
- continuedFractionApproximate :: Foldable f => Int -> (Integer, f Integer) -> Rational
- module Numeric.QuadraticIrrational.CyclicList
Constructors and deconstructors
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
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 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 1 1 (-1) 1) (\a b c d -> (a,b,c,d))
(1,1,-1,1)
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)>>>
runQI' (qi' 0.3 0.4 (-3)) (\a b c -> (a, b, c))
(3 % 10,2 % 5,-3)
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 1 1 (-1) 1)
(1,1,-1,1)
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)>>>
unQI' (qi' 0.3 0.4 (-3))
(3 % 10,2 % 5,-3)
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)>>>
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) 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)>>>
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) 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)>>>
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
Numerical operations
qiIsZero :: QI -> Bool Source #
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]
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 Source #
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 Source #
Add two QI
s 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 Source #
Subtract two QI
s 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 Source #
Multiply two QI
s 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 Source #
Divide two QI
s 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
qiFloor :: QI -> Integer Source #
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 Source #
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) Source #
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 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]