quadratic-irrational 0.0.3 → 0.0.4

raw patch · 5 files changed

+55/−27 lines, 5 files

Files

• ChangeLog.md +6/−0
• README.md +9/−8
• quadratic-irrational.cabal +9/−9
• src/Numeric/QuadraticIrrational.hs +26/−10
• tests/QuadraticIrrational.hs +5/−0

@@ -1,3 +1,9 @@+# 0.0.4 (2014-03-27)++* Make the description more precise.+* Add continuedFractionApproximate for rational partial evaluations of+  continued fractions.+ # 0.0.3 (2014-03-26)  * Add a more verbose description of the library.

@@ -2,8 +2,9 @@  [![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].+A library for exact computation with [quadratic irrationals][qi] with support+for exact conversion from and to [(potentially periodic) simple continued+fractions][pcf].  [qi]:  http://en.wikipedia.org/wiki/Quadratic_irrational [pcf]: http://en.wikipedia.org/wiki/Periodic_continued_fraction@@ -24,19 +25,19 @@  * `(1 + √5)/2` ([the golden ratio][gr]), -* solutions to some quadratic equations – the [quadratic formula][qf] has a-  familiar shape.+* solutions to quadratic equations with rational constants – 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 simple continued fraction is a number in the form  ``` a + 1/(b + 1/(c + 1/(d + 1/(e + …)))) ``` -alternatively expressed using the notation+or alternatively written as  ``` [a; b, c, d, e, …]@@ -44,8 +45,8 @@  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.+Every finite SCF represents a rational number and every infinite, periodic SCF+represents a quadratic irrational.  ``` 3.5      = [3; 2]

@@ -1,6 +1,6 @@ name: quadratic-irrational category: Math, Algorithms, Data-version: 0.0.3+version: 0.0.4 license: MIT license-file: LICENSE author: Johan Kiviniemi <devel@johan.kiviniemi.name>@@ -11,10 +11,10 @@ copyright: Copyright © 2014 Johan Kiviniemi synopsis: An implementation of quadratic irrationals description:-  An implementation of+  A library for exact computation with   <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>.+  with support for exact conversion from and to+  <http://en.wikipedia.org/wiki/Periodic_continued_fraction (potentially periodic) simple continued fractions>.   .   A quadratic irrational is a number that can be expressed in the form   .@@ -31,22 +31,22 @@   * @(1 + √5)\/2@     (<http://en.wikipedia.org/wiki/Golden_ratio the golden ratio>),   .-  * solutions to some quadratic equations – the+  * solutions to quadratic equations with rational constants – 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 simple continued fraction is a number expressed in the form   .   > a + 1/(b + 1/(c + 1/(d + 1/(e + …))))   .-  alternatively expressed using the notation+  or alternatively written as   .   > [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.+  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, …]

@@ -9,10 +9,10 @@ -- Stability   : provisional -- Portability : ViewPatterns ----- An implementation of+-- A library for exact computation with -- <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>.+-- with support for exact conversion from and to+-- <http://en.wikipedia.org/wiki/Periodic_continued_fraction (potentially periodic) simple continued fractions>. -- -- A quadratic irrational is a number that can be expressed in the form --@@ -29,22 +29,22 @@ -- * @(1 + √5)\/2@ --   (<http://en.wikipedia.org/wiki/Golden_ratio the golden ratio>), ----- * solutions to some quadratic equations – the+-- * solutions to quadratic equations with rational constants – 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 simple continued fraction is a number expressed in the form -- -- > a + 1/(b + 1/(c + 1/(d + 1/(e + …)))) ----- alternatively expressed using the notation+-- or alternatively written as -- -- > [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.+-- 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, …]@@ -64,11 +64,13 @@   , qiFloor   , -- * Continued fractions     continuedFractionToQI, qiToContinuedFraction+  , continuedFractionApproximate   , module Numeric.QuadraticIrrational.CyclicList   ) where  import Control.Applicative import Control.Monad.State+import qualified Data.Foldable as F import Data.List import Data.Maybe import Data.Ratio@@ -591,7 +593,7 @@      ~(b2cLow, b2cHigh) = iSqrtBounds (b*b * c) --- | Convert a (possibly periodic) continued fraction to a 'QI'.+-- | Convert a (possibly periodic) simple continued fraction to a 'QI'. -- -- @[2; 2] = 2 + 1\/2 = 5\/2@. --@@ -647,7 +649,7 @@      pos = positive "continuedFractionToQI" --- | Convert a 'QI' into a (possibly periodic) continued fraction.+-- | Convert a 'QI' into a (possibly periodic) simple continued fraction. -- -- @5\/2 = 2 + 1\/2 = [2; 2]@. --@@ -694,6 +696,20 @@     go (Just n) = (unQI n, i) : go (qiRecip (qiSubI n i))       where i = qiFloor n     go Nothing  = []++-- | 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]+continuedFractionApproximate :: F.Foldable f+                             => Int -> (Integer, f Integer) -> Rational+continuedFractionApproximate n (i0, F.toList -> is) =+  fromInteger i0 ++    foldr (\(pos -> i) r -> recip (fromInteger i + r)) 0 (take n is)+  where+    pos = positive "continuedFractionApproximate"  iSqrtBounds :: Integer -> (Integer, Integer) iSqrtBounds n = (low, high)

@@ -156,6 +156,11 @@           -- Limit the length of the periodic part for speed.           in (len <= 100) ==>                approxEq' (qiToFloat n) (qiToFloat (continuedFractionToQI cf))++      , testProperty "continuedFractionApproximate" $ \n ->+          let cf = qiToContinuedFraction n+              n' = continuedFractionApproximate 20 cf+          in  approxEq' (qiToFloat n) (fromRational n')       ]     ]