quadratic-irrational 0.0.2 → 0.0.3

raw patch · 6 files changed

+146/−20 lines, 6 filesdep ~numbers

Dependency ranges changed: numbers

Files

• .travis.yml +1/−0
• ChangeLog.md +4/−0
• README.md +47/−0
• quadratic-irrational.cabal +39/−1
• src/Numeric/QuadraticIrrational.hs +55/−16
• src/Numeric/QuadraticIrrational/CyclicList.hs +0/−3

@@ -0,0 +1,1 @@+language: haskell

@@ -1,3 +1,7 @@+# 0.0.3 (2014-03-26)++* Add a more verbose description of the library.+ # 0.0.2 (2014-03-25)  * Add doctests.

@@ -1,7 +1,54 @@ # `quadratic-irrational` +[![Build Status](https://travis-ci.org/ion1/quadratic-irrational.svg)](https://travis-ci.org/ion1/quadratic-irrational)+ An implementation of [quadratic irrationals][qi] with support for conversion from and to [periodic continued fractions][pcf].  [qi]:  http://en.wikipedia.org/wiki/Quadratic_irrational [pcf]: http://en.wikipedia.org/wiki/Periodic_continued_fraction++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][gr]),++* solutions to some quadratic equations – the [quadratic formula][qf] has a+  familiar shape.++[gr]: http://en.wikipedia.org/wiki/Golden_ratio+[qf]: http://en.wikipedia.org/wiki/Quadratic_formula++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, …]+```

@@ -1,6 +1,6 @@ name: quadratic-irrational category: Math, Algorithms, Data-version: 0.0.2+version: 0.0.3 license: MIT license-file: LICENSE author: Johan Kiviniemi <devel@johan.kiviniemi.name>@@ -15,12 +15,49 @@   <http://en.wikipedia.org/wiki/Quadratic_irrational quadratic irrationals>   with support for conversion from and to   <http://en.wikipedia.org/wiki/Periodic_continued_fraction 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@+    (<http://en.wikipedia.org/wiki/Golden_ratio the golden ratio>),+  .+  * solutions to some quadratic equations – the+    <http://en.wikipedia.org/wiki/Quadratic_formula 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, …] tested-with: GHC == 7.6.3  build-type: Simple cabal-version: >= 1.10 extra-source-files:   .gitignore+  .travis.yml   ChangeLog.md   README.md @@ -65,5 +102,6 @@                , doctest >= 0.9                , filepath                , mtl+               , numbers   default-language: Haskell2010   ghc-options: -threaded -Wall

@@ -13,6 +13,42 @@ -- <http://en.wikipedia.org/wiki/Quadratic_irrational quadratic irrationals> -- with support for conversion from and to -- <http://en.wikipedia.org/wiki/Periodic_continued_fraction 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@+--   (<http://en.wikipedia.org/wiki/Golden_ratio the golden ratio>),+--+-- * solutions to some quadratic equations – the+--   <http://en.wikipedia.org/wiki/Quadratic_formula 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, …]  module Numeric.QuadraticIrrational   ( -- * Constructors and deconstructors@@ -44,7 +80,10 @@ import Numeric.QuadraticIrrational.CyclicList import Numeric.QuadraticIrrational.Internal.Lens --- | @(a + b √c) / d@+-- $setup+-- >>> import Data.Number.CReal++-- | @(a + b √c) \/ d@ data QI = QI !Integer              !Integer              !Integer@@ -70,7 +109,7 @@  type QITuple = (Integer, Integer, Integer, Integer) --- | Given @a@, @b@, @c@ and @d@ such that @n = (a + b √c)/d@, constuct a '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@@ -166,7 +205,7 @@     (bN, bD) = (numerator b, denominator b) {-# INLINE qi' #-} --- | Given @n@ and @f@ such that @n = (a + b √c)/d@, run @f a b c d@.+-- | 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)@@ -182,7 +221,7 @@ runQI' (QI a b c d) f = f (a % d) (b % d) c {-# INLINE runQI' #-} --- | Given @n@ such that @n = (a + b √c)/d@, return @(a, b, c, d)@.+-- | Given @n@ such that @n = (a + b √c)\/d@, return @(a, b, c, d)@. -- -- >>> unQI (qi 3 4 5 6) -- (3,4,5,6)@@ -198,7 +237,7 @@ unQI' n = runQI' n (,,) {-# INLINE unQI' #-} --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @(a, b, c, d)@.+-- | 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)@@ -220,7 +259,7 @@ _qi' f n = (\ ~(a',b',c') -> qi' a' b' c') <$> f (unQI' n) {-# INLINE _qi' #-} --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @(a, b, d)@.+-- | 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)@@ -233,7 +272,7 @@   (\ ~(a',b',d') -> qiNoSimpl a' b' c d') <$> f (a,b,d) {-# INLINE _qiABD #-} --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @a@. It is more+-- | 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)@@ -245,7 +284,7 @@ _qiA = _qiABD . go   where go f ~(a,b,d) = (\a' -> (a',b,d)) <$> f a --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @b@. It is more+-- | 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)@@ -257,7 +296,7 @@ _qiB = _qiABD . go   where go f ~(a,b,d) = (\b' -> (a,b',d)) <$> f b --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @c@. It is more+-- | 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)@@ -269,7 +308,7 @@ _qiC = _qi . go   where go f ~(a,b,c,d) = (\c' -> (a,b,c',d)) <$> f c --- | Given a 'QI' corresponding to @n = (a + b √c)/d@, access @d@. It is more+-- | 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)@@ -559,10 +598,10 @@ -- >>> continuedFractionToQI (2,NonCyc [2]) -- qi 5 0 0 2 ----- @[2; 1, 1, 1, 4, 1, 1, 1, 4, …] = √7@.+-- The golden ratio is @[1; 1, 1, …]@. ----- >>> continuedFractionToQI (2,Cyc [] 1 [1,1,4])--- qi 0 1 7 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@@ -615,10 +654,10 @@ -- >>> qiToContinuedFraction (qi 5 0 0 2) -- (2,NonCyc [2]) ----- @√7 = [2; 1, 1, 1, 4, 1, 1, 1, 4, …]@.+-- The golden ratio is @(1 + √5)\/2@. We can compute the corresponding PCF. ----- >>> qiToContinuedFraction (qi 0 1 7 1)--- (2,Cyc [] 1 [1,1,4])+-- >>> 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])

@@ -14,9 +14,6 @@ import Data.Foldable import Data.Monoid --- $setup--- import Data.Foldable (toList)- -- | A container for a possibly cyclic list. -- -- >>> toList (NonCyc "hello")