cl-cf

#+TITLE: cf
#+AUTHOR: Guillaume LE VAILLANT
#+DATE: 2024-06-15
#+EMAIL: glv@posteo.net
#+LANGUAGE: en
#+OPTIONS: num:nil toc:nil html-postamble:nil html-scripts:nil
#+HTML_DOCTYPE: html5

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

* License
*cf* is released under the GPL-3 license. See the [[file:LICENSE][LICENSE]] file for details.

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

#+BEGIN_SRC lisp
  (asdf:load-system "cf")
#+END_SRC

or

#+BEGIN_SRC lisp
  (quicklisp:quickload "cf")
#+END_SRC

The functions will then be available in the ~cf~ package.

** Convert 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.

#+BEGIN_SRC lisp
  (cf x) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-simplify x) => list
#+END_SRC

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.


#+BEGIN_SRC lisp
  (cf-nsimplify x) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-convergent x) => ratio
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-decimal x n) => string
#+END_SRC

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

** Constants
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

** Predicates, equality and inequality functions
#+BEGIN_SRC lisp
  (cf-zerop x) => boolean
#+END_SRC

Return ~t~ if /x/ is zero, and ~nil~ otherwise.


#+BEGIN_SRC lisp
  (cf-minusp x) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-plusp x) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf= x &rest more-fractions) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf/= x &rest more-fractions) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf< x &rest more-fractions) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf<= x &rest more-fractions) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf> x &rest more-fractions) => boolean
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf>= x &rest more-fractions) => boolean
#+END_SRC

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

** Arithmetic functions
#+BEGIN_SRC lisp
  (cf+ &rest fractions) => list
#+END_SRC

Return the continued fraction of the sum of its arguments.


#+BEGIN_SRC lisp
  (cf1+ x) => list
#+END_SRC

Return the continued fraction of /x/ + 1.


#+BEGIN_SRC lisp
  (cf- x &rest more-fractions) => list
#+END_SRC

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/.


#+BEGIN_SRC lisp
  (cf1- x) => list
#+END_SRC

Return the continued fraction of /x/ - 1.


#+BEGIN_SRC lisp
  (cf* &rest fractions) => list
#+END_SRC

Return the continued fraction of the product of its arguments.


#+BEGIN_SRC lisp
  (cf/ x &rest more-fractions) => list
#+END_SRC

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/.


#+BEGIN_SRC lisp
  (cf-min x &rest more-fractions) => list
#+END_SRC

Return the least of its arguments.


#+BEGIN_SRC lisp
  (cf-max x &rest more-fractions) => list
#+END_SRC

Return the greatest of its arguments.


#+BEGIN_SRC lisp
  (cf-abs x) => list
#+END_SRC

Return the continued fraction of the absolute value of /x/.


#+BEGIN_SRC lisp
  (cf-signum x) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-floor x &optional y) => list
#+END_SRC

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.


#+BEGIN_SRC lisp
  (cf-mod x y) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-ceiling x &optional y) => list
#+END_SRC

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.


#+BEGIN_SRC lisp
  (cf-truncate x &optional y) => list
#+END_SRC

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.


#+BEGIN_SRC lisp
  (cf-rem x y) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-round x &optional y) => list
#+END_SRC

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.

** Power, exponential and logarithm functions
#+BEGIN_SRC lisp
  (cf-sqrt x) => list
#+END_SRC

Return the continued fraction of the square root of /x/.


#+BEGIN_SRC lisp
  (cf-exp x) => list
#+END_SRC

Return the continued fraction of the exponential of /x/.


#+BEGIN_SRC lisp
  (cf-log x &optional y) => list
#+END_SRC

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


#+BEGIN_SRC lisp
  (cf-expt x y) => list
#+END_SRC

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

** Circular functions
#+BEGIN_SRC lisp
  (cf-cos x) => list
#+END_SRC

Return the continued fraction of cos(/x/).


#+BEGIN_SRC lisp
  (cf-sin x) => list
#+END_SRC

Return the continued fraction of cos(/x/).


#+BEGIN_SRC lisp
  (cf-tan x) => list
#+END_SRC

Return the continued fraction of tan(/x/).


#+BEGIN_SRC lisp
  (cf-acos x) => list
#+END_SRC

Return the continued fraction of acos(/x/).


#+BEGIN_SRC lisp
  (cf-asin x) => list
#+END_SRC

Return the continued fraction of asin(/x/).


#+BEGIN_SRC lisp
  (cf-atan y &optional x) => list
#+END_SRC

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

** Hyperbolic functions
#+BEGIN_SRC lisp
  (cf-cosh x) => list
#+END_SRC

Return the continued fraction of cosh(/x/).


#+BEGIN_SRC lisp
  (cf-sinh x) => list
#+END_SRC

Return the continued fraction of sinh(/x/).


#+BEGIN_SRC lisp
  (cf-tanh x) => list
#+END_SRC

Return the continued fraction of tanh(/x/).


#+BEGIN_SRC lisp
  (cf-acosh x) => list
#+END_SRC

Return the continued fraction of acosh(/x/).


#+BEGIN_SRC lisp
  (cf-asinh x) => list
#+END_SRC

Return the continued fraction of asinh(/x/).


#+BEGIN_SRC lisp
  (cf-atanh x) => list
#+END_SRC

Return the continued fraction of atanh(/x/).

** Homographic 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 an
expression directly from the coefficients of the continued fractions passed as
arguments.
It means that you don't need to convert the arguments to ratios, compute the
expression, 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.

#+BEGIN_SRC lisp
  (cf-homographic a b c d x) => list
#+END_SRC

Return the continued fraction of
#+BEGIN_SRC
   ax + b
  --------
   cx + d
#+END_SRC
where /a/, /b/, /c/ and /d/ are relative integers,
and /x/ is a continued fraction.


#+BEGIN_SRC lisp
  (cf-bihomographic a b c d e f g h x y) => list
#+END_SRC

Return the continued fraction of
#+BEGIN_SRC
   axy + bx + cy + d
  -------------------
   exy + fx + gy + h
#+END_SRC
where /a/, /b/, /c/, /d/, /e/, /f/, /g/ and /h/ are relative integers,
and /x/ and /y/ are continued fractions.

* Examples
#+BEGIN_SRC lisp
  ;; 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"
#+END_SRC

#+BEGIN_SRC lisp
  ;; 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)
#+END_SRC

#+BEGIN_SRC lisp
  ;; 19 / 17 = 19/17
  (cf/ '(19) '(17))
  => (1 8 2)

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

#+BEGIN_SRC lisp
  (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
#+END_SRC

#+BEGIN_SRC lisp
  (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)
#+END_SRC

#+BEGIN_SRC lisp
  ;; 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)
#+END_SRC

* Tests
The tests require the [[https://common-lisp.net/project/fiveam/][fiveam]] package. They can be run with:

#+BEGIN_SRC lisp
(asdf:test-system "cf")
#+END_SRC


cl-cf

Upstream URL

Author

License

cf

Version:

License:

Authors:

Dependencies:

cf-tests

Version:

License:

Authors:

Dependencies:

Dependencies (1)

Dependents (0)