CFrac — Convert from/to continued fractions (Emacs package)

[1 2 3 4]               ; continued fraction
'(43 . 30)              ; fraction
1.43333333333333333333  ; float

(use-package cfrac :demand t)

(require 'cfrac)

(cfrac-flo->cfr float-e 21)
=> [2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 11]
;;     Fails on the 21st position: should be ^14

;;; cfrac.el --- Convert from/to continued fractions  -*- lexical-binding: t -*-
;;; Commentary:
;;;; For all the details, please do see the README
;;; Code:
;;;; Libraries
;;;; Package metadata
;;;; Customizable variables
;;;; Other variables
;;;; Functions
;;;;; In one direction
;;;;; In the opposite direction
;;;;; Utilities
;;;;; Misc
;;;;; See README
;;;; Wrapping up
;;; cfrac.el ends here

;;; cfrac.el --- Convert from/to continued fractions  -*- lexical-binding: t -*-

;; SPDX-FileCopyrightText: © flandrew <https://flandrew.srht.site/listful>

;;---------------------------------------------------------------------------
;; Author:    flandrew
;; Created:   2021-05-01
;; Updated:   2025-07-29
;; Keywords:  extensions
;; Homepage:  <https://flandrew.srht.site/listful/software.html>
;;---------------------------------------------------------------------------
;; Package-Version:  0.2.0
;; Package-Requires: ((emacs "25.1"))
;;---------------------------------------------------------------------------

;; SPDX-License-Identifier: GPL-3.0-or-later

;; This file is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published
;; by the Free Software Foundation, either version 3 of the License,
;; or (at your option) any later version.
;;
;; This file is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this file. If not, see <https://www.gnu.org/licenses/>.

;;; Commentary:
;;
;; CFrac is a simple continued fractions library.
;;
;;;; For all the details, please do see the README
;;
;; Open it easily with:
;;   (find-file-read-only "README.org")   <--- C-x C-e here¹
;;
;; or from any buffer:
;;   M-x cfrac-see-readme
;;
;; or read it online:
;;   <https://flandrew.srht.site/listful/sw-emacs-cfrac.html>
;;
;; ¹ or the key that ‘eval-last-sexp’ is bound to, if not C-x C-e.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



;;; Code:
;;;; Libraries

(require 'lisp-mnt)  ; ‘lm-summary’, ‘lm-homepage’, ‘lm-version’, ‘lm-header’


;;;; Package metadata

(defvar cfrac--name "CFrac")

(defvar cfrac--dot-el
  (format "%s.el" (file-name-sans-extension (eval-and-compile
                                              (or load-file-name
                                                  buffer-file-name)))))
(defvar cfrac--readme-org
  (expand-file-name "README.org" (file-name-directory cfrac--dot-el)))

(defvar cfrac--summary  (lm-summary   cfrac--dot-el))
(defvar cfrac--homepage (lm-homepage  cfrac--dot-el))
(defvar cfrac--version  (lm-with-file cfrac--dot-el
                          (or (lm-header "package-version")
                              (lm-version))))


;;;; Customizable variables

(defgroup cfrac nil
  (format "%s." cfrac--summary)
  :group 'extensions
  :link  '(emacs-library-link :tag "Lisp file" "cfrac.el")
  :link  `(file-link :tag "README.org" ,cfrac--readme-org)
  :link  `(url-link  :tag "Homepage"   ,cfrac--homepage))


;;;; Other variables

(defvar cfrac-maxstep-default 100)

(defvar cfrac-maxelem-default 1000000)


;;;; Functions
;;;;; In one direction

(defun cfrac-flo->cfr (flo &optional maxstep maxelem)
  "Convert float FLO into continued fraction, represented as a vector.
MAXSTEP is the maximum number of steps. If nil, default to
`cfrac-maxstep-default'.

MAXELEM is the maximum element. If nil, default to
`cfrac-maxelem-default'.

Example: 3.875 => [3 1 7]"
  (unless maxstep (setq maxstep cfrac-maxstep-default))
  (unless maxelem (setq maxelem cfrac-maxelem-default))
  (let ((res nil)
        (cur flo)
        (stp maxstep))
    (while (and (> stp 0)
                (< cur maxelem))
      (setq res (cons (floor cur) res)
            cur (/ 1.0 (- cur (floor cur)))
            stp (1- stp)))
    ;; If we stopped before number of steps, we converged.
    ;; If last one is 1, canonicalize it.
    (and (< (length res) stp)
         (= (car res) 1)
         (setq res (cons (1+ (cadr res))
                         (cddr res))))
    (vconcat (nreverse res))))

(defun cfrac-cfr->fra (cfr)
  "Convert continued fraction CFR into a proper fraction.
The fraction is represented as a cons cell: (num . den).
Example: [3 1 7]  =>  (31 . 8)"
  (if (= 1 (length cfr))
      (cons (aref cfr 0) 1)
    (let* ((onum 1)
           (num  1)
           (cur  (string-to-list (reverse cfr)))
           (oden (car cur))
           (den  (cadr cur)))
      (while (> (length cur) 2)
        (setq num  oden
              oden (+ (* oden den) onum)
              onum num
              num  1
              den  (caddr cur)
              cur  (cons oden (cddr cur))))
      (cons (+ (* oden den) onum) oden))))

(defun cfrac-fra->flo (fra)
  "Convert fraction FRA expressed as cons cell into a float.
Example: (31 . 8)  =>  3.875"
  (/ (car fra) (cdr fra) 1.0))


;;;;; In the opposite direction

(defun cfrac-flo->fra (flo &optional maxstep maxelem)
  "Convert float FLO into a fraction, expressed as cons cell.
MAXSTEP is the maximum number of steps. If nil, default to
`cfrac-maxstep-default'.

MAXELEM is the maximum element. If nil, default to
`cfrac-maxelem-default'.

Example: 3.875  =>  (31 . 8)"
  (cfrac-cfr->fra (cfrac-flo->cfr flo maxstep maxelem)))

(defun cfrac-fra->cfr (fra)
  "Convert fraction FRA expressed as cons cell into a continued fraction.
Example: (31 . 8)  =>  [3 1 7]"
  (cfrac-flo->cfr (cfrac-fra->flo fra)))

(defun cfrac-cfr->flo (cfr)
  "Convert continued fraction CFR into a float.
Example: [3 1 7]  =>  3.875"
  (cfrac-fra->flo (cfrac-cfr->fra cfr)))


;;;;; Utilities

(defun cfrac-canon-fra (fra)
  "Canonicalize fraction FRA, expressed as cons cell.
Example: (36 . 8)  =>  (9 . 2)"
  (let* ((frst (car fra))
         (last (cdr fra))
         (gcd  (cfrac-gcd frst last)))
    (cons (/ frst gcd)
          (/ last gcd))))

(defun cfrac-gcd (a b)
  "Greatest common divisor of A and B.
Example: 36 8  =>  4"
  (if (= 0 b) a (cfrac-gcd b (% a b))))


;;;;; Misc

(defun cfrac--irrational-failures ()
  "This function does nothing.
It exists only so that we can automatically add to the README some
examples of conversion failures of irrational numbers under high
precision due to seemingly unavoidable floating-point errors."
  (ignore))


;;;;; See README

;;;###autoload
(defun cfrac-see-readme (&optional heading narrow)
  "Open cfrac's README.org file.
Search for the file in cfrac.el's directory.

If found, open it read-only.

If optional argument HEADING is passed, try to navigate to the
heading after opening it. HEADING should be a string.

If optional argument NARROW is non-nil, narrow to that heading.
This argument has no effect if HEADING is nil or not found."
  (interactive)
  (let ((readme cfrac--readme-org))
    (if (file-exists-p readme)
      (let ((pr (make-progress-reporter
                   (format "Opening %s ... "
                           (abbreviate-file-name readme)))))
          (find-file-read-only readme)
          (when heading
            (cfrac--goto-org-heading heading narrow))
          (progress-reporter-done pr))
      (message "Couldn't find %s's README.org" cfrac--name))))

;;;###autoload
(defun cfrac-see-news ()
  "See the News in cfrac's README.org file."
  (interactive)
  (cfrac-see-readme "News" 'narrow)
  (cfrac--display-org-subtree))

(defun cfrac--display-org-subtree ()
  "Selectively display org subtree."
  (let ((cmds '( outline-hide-subtree outline-show-children
                 outline-next-heading outline-show-branches)))
    (and (equal (mapcar #'fboundp cmds) '(t t t t))
         (mapc #'funcall cmds))))

(defun cfrac--goto-org-heading (heading &optional narrow)
  "Navigate to org HEADING and optionally NARROW to it."
  (let* ((hrx (format "^[*]+ %s" heading))
         (pos (save-match-data
                (save-excursion
                  (save-restriction
                    (widen)  (goto-char (point-max))
                    (re-search-backward hrx nil t 1))))))
    (when pos
      (widen)  (goto-char pos)
      (if (and narrow (fboundp 'org-narrow-to-subtree))
          (org-narrow-to-subtree)
        (recenter-top-bottom 1))
      (when (fboundp 'outline-show-subtree)
        (outline-show-subtree))
      (when (fboundp 'org-flag-drawer)
        (save-excursion
          (forward-line 1)
          (org-flag-drawer t))))))


;;;; Wrapping up

(provide 'cfrac)

;; Local Variables:
;; coding:                     utf-8
;; indent-tabs-mode:           nil
;; sentence-end-double-space:  nil
;; outline-regexp:             ";;;;* "
;; End:

;;; cfrac.el ends here