cf

1Description

cf is a Common Lisp library for doing computations using continued fractions.

2License

cf is released under the GPL-3 license. See the LICENSE file for details.

3API

After puting the library in a place where your Common Lisp system can see it,it can be loaded with the usual:

  (asdf:load-system "cf")

or

  (quicklisp:quickload "cf")

The functions will then be available in the cf package.

3.1Convert to/from continued fractions

A continued fraction is represented by a list of coefficients.

The *cf-length* parameter indicates the maximum number of coefficients that will be used when making a continued fraction (20 by default).

The *cf-max-number-in-fractional-part* parameter indicates the maximum integer that can appear in the fractional part of a continued fraction (most-positive-fixnum by default). The cf-simplify function will truncate the continued fraction if it encounters a number bigger than this maximum, in order to make the computations faster by reducing the amount of arithmetic operations on bignums.

  (cf x) => list

Return the continued fraction for the number x (with at most *cf-length* coefficients).

  (cf-simplify x) => list

Keep at most *cf-length* coefficients of the continued fraction x and remove huge numbers (greater than *cf-max-number-in-fractional-part*) from the fractional part. You should rarely need to call this function as it is used automatically by most functions in the library.

  (cf-nsimplify x) => list

Like cf-simplify , but modifying x instead of creating a new continued fraction.

  (cf-convergent x) => ratio

Return the convergent of the continued fraction x (i.e. convert the continued fraction to a ratio).

  (cf-decimal x n) => string

Return a string representing the decimal expansion of the continued fraction x, with at most n digits in the fractional part.

3.2Constants

The continued fractions for some constants are included in the library:

• +cf-pi+ : π, ratio of a circle's circumference to its diameter
• +cf-pi/2+ : π/2
• +cf-tau+ : τ = 2π
• +cf-e+ : Euler's number
• +cf-gamma+ : γ, the Euler-Mascheroni constant
• +cf-ln-2+ : natural logarithm of 2
• +cf-atan-1/2+ : arctangent of 1/2

3.3Predicates, equality and inequality functions

  (cf-zerop x) => boolean

Return t if x is zero, and nil otherwise.

  (cf-minusp x) => boolean

Return t if x is strictly negative, and nil otherwise.

  (cf-plusp x) => boolean

Return t if x is strictly positive, and nil otherwise.

  (cf= x &rest more-fractions) => boolean

Return t if all its arguments are equal, and nil otherwise.

  (cf/= x &rest more-fractions) => boolean

Return nil if at least two of its arguments are equal, and t otherwise.

  (cf< x &rest more-fractions) => boolean

Return if t its arguments are in strictly increasing order, and nil otherwise.

  (cf<= x &rest more-fractions) => boolean

Return t if its arguments are in increasing order, and nil otherwise.

  (cf> x &rest more-fractions) => boolean

Return t if its arguments are in strictly decreasing order, and nil otherwise.

  (cf>= x &rest more-fractions) => boolean

Return t if its arguments are in decreasing order, and nil otherwise.

3.4Arithmetic functions

  (cf+ &rest fractions) => list

Return the continued fraction of the sum of its arguments.

  (cf1+ x) => list

Return the continued fraction of x + 1.

  (cf- x &rest more-fractions) => list

Return the continued fraction of the subtraction of the second and subsequent arguments from x. If more-fractions are not specified, return the continued fraction of -/x/.

  (cf1- x) => list

Return the continued fraction of x - 1.

  (cf* &rest fractions) => list

Return the continued fraction of the product of its arguments.

  (cf/ x &rest more-fractions) => list

Return the continued fraction of the division of x by the second and subsequent arguments. If more-fractions are not specified, return the continued fraction of 1 / x.

  (cf-min x &rest more-fractions) => list

Return the least of its arguments.

  (cf-max x &rest more-fractions) => list

Return the greatest of its arguments.

  (cf-abs x) => list

Return the continued fraction of the absolute value of x.

  (cf-signum x) => list

Return the continued fraction of -1, 0 or 1 if x is respectively negative, zero or positive.

  (cf-floor x &optional y) => list

Return the continued fraction of the greatest integer smaller than or equal to x / y, and the continued fraction of x modulo y. The default value for y is 1.

  (cf-mod x y) => list

Return the continued fraction of x modulo y (the second value of cf-floor).

  (cf-ceiling x &optional y) => list

Return the continued fraction of the smallest integer greater than or equal to x / y, and the continued fraction of the remainder. The default value for y is 1.

  (cf-truncate x &optional y) => list

Return the continued fraction of the integer part of x / y rounded toward 0, and the continued fraction of the remainder. The default value for y is 1.

  (cf-rem x y) => list

Return the continued fraction of the remainder of x / y (the second value of cf-truncate).

  (cf-round x &optional y) => list

Return the continued fraction of x / y rounded to the nearest integer, and the continued fraction of the remainder. The default value for y is 1.

3.5Power, exponential and logarithm functions

  (cf-sqrt x) => list

Return the continued fraction of the square root of x.

  (cf-exp x) => list

Return the continued fraction of the exponential of x.

  (cf-log x &optional y) => list

If y is specified, return the continued fraction of the base y logarithm of x, and ln(x) otherwise.

  (cf-expt x y) => list

Return the continued fraction of x raised to the power of y.

3.6Circular functions

  (cf-cos x) => list

Return the continued fraction of cos(x).

  (cf-sin x) => list

Return the continued fraction of cos(x).

  (cf-tan x) => list

Return the continued fraction of tan(x).

  (cf-acos x) => list

Return the continued fraction of acos(x).

  (cf-asin x) => list

Return the continued fraction of asin(x).

  (cf-atan y &optional x) => list

If x is specified, return the continued fraction of atan(y / x), and atan(y) otherwise.

3.7Hyperbolic functions

  (cf-cosh x) => list

Return the continued fraction of cosh(x).

  (cf-sinh x) => list

Return the continued fraction of sinh(x).

  (cf-tanh x) => list

Return the continued fraction of tanh(x).

  (cf-acosh x) => list

Return the continued fraction of acosh(x).

  (cf-asinh x) => list

Return the continued fraction of asinh(x).

  (cf-atanh x) => list

Return the continued fraction of atanh(x).

3.8Homographic functions

Most of the functions in the library are based on the two following functions.They can be used to compute the coefficients of the continued fraction of anexpression directly from the coefficients of the continued fractions passed asarguments.It means that you don't need to convert the arguments to ratios, compute theexpression, and convert back to a continued fraction.

These functions don't call cf-simplify on their result automatically, so you might have to do it if necessary.

  (cf-homographic a b c d x) => list

Return the continued fraction of

   ax + b
  --------
   cx + d

where a, b, c and d are relative integers,and x is a continued fraction.

  (cf-bihomographic a b c d e f g h x y) => list

Return the continued fraction of

   axy + bx + cy + d
  -------------------
   exy + fx + gy + h

where a, b, c, d, e, f, g and h are relative integers,and x and y are continued fractions.

4Examples

  ;; Get the continued fraction for the number 17/19
  (cf 17/19)
  => (0 1 8 2)

  ;; Get the simple ratio from the continued fraction
  (cf-convergent '(0 1 8 2))
  => 17/19

  ;; Get the decimal representation from the continued fraction
  (cf-decimal '(0 1 8 2) 30)
  => "0.894736842105263157894736842105"

  ;; 26/5 + 10/7 = 232/35
  (cf+ '(5 5) '(1 2 3))
  => (6 1 1 1 2 4)

  ;; 232/35 - 10/7 = 26/5
  (cf- '(6 1 1 1 2 4) '(1 2 3))
  => (5 5)

  ;; 19 / 17 = 19/17
  (cf/ '(19) '(17))
  => (1 8 2)

  ;; 19/17 * 17 = 19
  (cf* '(1 8 2) '(17))
  => (19)

  (cf-sqrt '(7))
  => (2 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1)

  ;; √7 * √7 = 7
  (let ((a (cf-sqrt '(7))))
    (float (cf-convergent (cf* a a))))
  => 7.0

  (cf-simplify +cf-pi+)
  => (3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2)

  ;; Computing atan(1) + atan(2) + atan(3) with continued fractions of 20
  ;; coefficients doesn't return the fully correct continued fraction for π.
  ;; The last coefficients are different.
  (let ((a (cf-atan '(1)))
        (b (cf-atan '(2)))
        (c (cf-atan '(3))))
    (cf+ a b c))
  => (3 7 15 1 292 1 1 1 2 1 3 1 4 4 3 2 1 1 5 1)

  ;; By using continued fractions of 30 coefficients in the computation,
  ;; the precision of the result increases and we can get the correct first 20
  ;; coefficients for π.
  (let* ((*cf-length* 30)
         (a (cf-atan '(1)))
         (b (cf-atan '(2)))
         (c (cf-atan '(3)))
         (d (cf+ a b c)))
    (let ((*cf-length* 20))
      (cf-simplify d)))
  => (3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2)

  ;; Compute the continued fraction for the golden ratio (1 + √5) / 2
  (cf-simplify (cf-homographic 1 1 0 2 (cf-sqrt '(5))))
  => (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

5Tests

The tests require the fiveam package. They can be run with:

(asdf:test-system "cf")