The ratmath Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The ratmath Reference Manual

This is the ratmath Reference Manual, version 1, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Mar 25 19:02:54 2020 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Ratmath

Ratmath is a collection of utilities for working with rational numbers, approximations, and intervals in Common Lisp. Functions are included to calculate the closest single approximant given a maximum numerator/denominator (rat) or the smallest bounded rational interval (infsup). The infsup function can find the floating point constant pi with a denominator limit of, e.g. 256, to be within the interval 688/219 to 355/113, and the with-interval-math function can use this interval instead of exact values to carry out further interval arithmetic to yield interval results.

A Better (rational NUM) and (rationalize NUM) Function

In its simplest use case, it is an extension of Common Lisp's rationlize that can take keyword arguments :limd and :limn representing the maximum numerator/denominator:

CL-USER> (ratmath:rat pi :limd 255)
355/113

Calculating Rational Intervals

Interval arithmetic is a powerful and convenient way of doing calculations in engineering but is seldom accomodated in the base functionality of computer languages. Wikipedia

There are other libraries for interval math using floats, but this library instead uses rationals, a numerical data type not commonly appreciated as a base numerical type amongst the other languages. With Common Lisp's built-in infinite size integers, there is no limit to the precision of rational numbers which simplifies a lot of the inherent complexity of writing floating point interval libraries which have to worry about round off on every operation.

The disadvantage of using rationals rather than floats is that some calculations can end up generating extremely large numerators and denominators quickly. Conveniently, these large numbers can be rationally approximated into intervals of smaller numbers at any time in the middle or at the end of a calculation. As as example, the number representing e * pi using high precision rational constants on e and pi yields a rational result which has 72-bit numerator (which would cause overflow in anything other than Common Lisp). This bignum rational could be reduced to the following 16-bit rational interval with ratmath:

CL-USER> (* (rational pi) (rational (exp 1.0)))
2520484590068807905375/295147905179352825856
CL-USER> (ratmath:infsup * :limd 65535 :limn 65535)
(23749/2781 . 50077/5864)
32894771015794204823/36893488147419103232

You can usually ignore the second value returned from infsup. It represents an alpha, or a number between 0 and 1 representing the location of the original number inside the returned interval. The alpha calculation returns a rational that may be of higher order than even the original rational. For most cases, it would be recommended to coerce this rational into a float or use the rat function to reduce its precision.

Approximations From Rational Intervals

There are routines to work in reverse as well. That is, to go from an interval to the simplest rational number within that interval. The Common Lisp builtin rational differs only from its cousin rationalize by calculating a rational approximation from an interval about the original floating point number equal to the epsilon of the floating point representation. Here's how you do something similar, but with an explicitly bounded interval with ratmath:

CL-USER> (ratmath:rat '(110/333 . 221/333))
1/2

Trivial Interval Arithmetic

Intervals can be useful outside of rational approximation and used in the general arithmetic of non-exact measurements and numbers. For instance, on a calculation returning voltage measurements of an analog input, one usually needs to plug in numbers representing the voltage reference and any input resistor divider ratios. Using exact numbers for these is suboptimal as the truth is that these specifications are fuzzy and have non-zero tolerances. Interval math can be used instead to output an interval representing where the analog input true value might actually be between.

An interval at its core is simply a cons of two numbers. e.g. '(99/20 . 101/20). To facilitate creation, it is also possible to create the same interval with alternative notation:

CL-USER> (ratmath:infsup 5 :abstol 5/100)             ;; 5, +/-.05
(99/20 . 101/20)
CL-USER> (ratmath:infsup 99/20 :abstol '(0 . 1/10))   ;; 99/20, -0/+.1
(99/20 . 101/20)
CL-USER> (ratmath:infsup 101/20 :abstol '(1/10 . 0))  ;; 101/20, -.1/+0
(99/20 . 101/20)
CL-USER> (ratmath:infsup 5 :tol 1/100)                ;; 5, +/-1%
(99/20 . 101/20)
CL-USER> (ratmath:infsup 5 :tol '(0 . 1/100))         ;; 5, -0%/+1%
(5 . 101/20)

The gist is that :tol takes either an interval or an exact representing the percent tolerance and :abstol uses absolute values +/- rather than percentages. Refer to the documentation of the infsup function for further details.

with-interval-math Blocks

From within a ratmath:with-interval-math block, some of the basic arithmetic operations are replaced with interval aware variants. For instance:

CL-USER> (ratmath:with-interval-math
           (* '(1 . 2) 5 (ratmath:infsup 3.3 :tol .01)))
(16.335 . 33.329998)

Notice that the usual rules of floating point contagion apply. Since the infsup was given arguments in floats, the result is a float. We can turn this float back into rationals or exacts with:

CL-USER> (ratmath:infsup '(16.335 . 33.329998) :limd 100)
(49/3 . 3333/100)
CL-USER> (ratmath:rat *)
17

The rat function converts the interval '(16.335 . 33.329998) into the simplest number within. For this interval, it is 17. Simplest may not be the best term here, the full truth is its first number on the infinite Stern-Brocot fraction tree that is recursively traversed in the process of analyzing the best convergents and semi-convergents of a given continued fraction. What I mean to illustrate here is that, under this definition, this number will rarely be the midpoint of the interval, and also that mathematically correct rational approximation is not as trivial as it may seem at first glance. There is some really interesting algorithms and concepts (to math geeks, anyway) this library is abstracting that many programs might gloss over. In fact, in the beginning of 2020, the Linux kernel doesn't even have a fully correct implementation which it uses (amongst other things) to calculate correct PLL dividers for CPU clock rates. One that was close was published and posted, but abandoned for non-obvious reasons probably having to do with Linux kernel politics and style (or perhaps some microbenchmark suffered).

Syntactic Sugar

Within a with-interval-math block, the full power of the Common Lisp macro system is utilized to realize a cute feature regarding the parsing of numeric literals. This can be illustrated most succinctly in the following single-line piece of code:

CL-USER> (ratmath:with-interval-math (* 2 ~5))
(9 . 11)

The with-interval-math turns the numeric literal ~5 automatically into the interval '(4.5 . 5.5) which is then multiplied by exactly 2 to return the interval '(9 . 11). The rules of conversion for ~ literals should not be surprising. It should be noted that the interval will always result in rationals even when normal numeric literal parsing rules would have it be a float. The other key to remember regarding the tilde literal is they are parsed according to the rules of significant figures. e.g. ~5 is '(4.5 . 5.5) but ~5.00 is '(4.995 . 5.005) Exponential notation is honored as one might predict, ~1e3 is '(500 . 1500), always as rationals.

These numeric literals can also be parsed outside of a with-interval-math block by passing a string to parse-interval. In parse-interval the tilde character ornamentation is not necessary.

The tilde '~' character is also a function, but it behaves differently depending on the context. Inside a with-interval-math block it turns an exact into an interval and behaves the same way as the infsup function. Outside of this block, it turns intervals into exacts according to some &key argument controls. Refer to the documentation of the ~ function for full details, but here are a few examples:

Random numbers for (e.g.) Monte Carlo analysis using a uniform probability distribution within the interval:

CL-USER> (ratmath:~ '(1 . 2) :random t)  ;; this will always be a float
1.3231988

The :discrete boolean means to only return upper or lower limit. Assumes a 50/50 chance to return either, unless the :alpha option is supplied.

CL-USER> (ratmath:~ '(1 . 2) :random t :discrete t) ;; random select upper/lower
1
CL-USER> (ratmath:~ '(1 . 2) :random t :discrete t :alpha 3/4) ;; 75% chance of upper
2

Several types of calculations are only interested in worst-case/best-case which will be either the upper or lower limit of the interval, e.g.:

CL-USER> (ratmath:~ '(1/14 . 3/7) :upper t)
3/7
CL-USER> (ratmath:~ '(1/14 . 3/7) :lower t)
1/14

Other Tricks and Functions (useful in the REPL)

A common application of these algorithms are to print out a progression of rational approximations of a given number as the size of the numerator and denominator terms is allowed to increase. The following prints out the best convergents and semi-convergents and their error in PPM or PPB (parts-per-million/billion) on the way to system's pi constant:

CL-USER> (ratmath:fractions pi :order 10)
2'd3/1'd1 45070.341 PPM
5'd22/3'd7 -402.499 PPM
8'd179/6'd57 395.270 PPM
9'd355/7'd113 -8.491D+1 PPB
16'd52163/15'd16604 8.474D+1 PPB
19'd312689/17'd99532 -9.277D-3 PPB
20'd833719/19'd265381 2.774D-3 PPB
21'd1146408/19'd364913 -5.128D-4 PPB
23'd5419351/21'd1725033 -7.088D-6 PPB
27'd80143857/25'd25510582 1.453D-7 PPB
28'd245850922/27'd78256779 -1.410D-8 PPB
30'd817696623/28'd260280919 1.531D-9 PPB
32'd2698940791/30'd859099536 1.074D-10 PPB
34'd9978066541/32'd3176117225 -9.265D-12 PPB
35'd32633140414/34'd10387451211 3.833D-13 PPB
38'd238410049439/37'd75888275702 -2.047D-14 PPB
40'd747863288731/38'd238052278317 -2.855D-15 PPB
41'd1257316528023/39'd400216280932 4.860D-16 PPB
43'd5777129400823/41'd1838917402045 5.350D-17 PPB
44'd10296942273623/42'd3277618523158 6.901D-19 PPB
50'd884279719003555/49'd281474976710656 0.000D-1 PPB

The :order 10 argument says to only print a best convergent/semi-convergent at most once per decimal order of magnitude. This avoids flooding the output with semi-convergents. If not specified, the default order is 2, which prints the best approximation for every bit size width in the numerator and denominator.

The ##'d syntax at the beginning of each number is Verilog syntax to describe the bit width of the constant. I wrote these routines originally to facilitate writing Verilog in FPGAs for fractional clock dividers and PWM controllers. The Verilog syntax for size is more convenient than manually counting digits to figure how big of a register I have to instantiate.

It is worth noting that over half of the above convergents to pi will vary from implementation to implementation. The pi constant is defined as a floating point number in Common Lisp and the default behavior of ratmath is to convert floats into rationals using the rational function rather than rationalize, which takes into consideration the host machines limits of floating point precision. (i.e. epsilon) If we instead prefer to stop the approximation at the end of the floating point constant's precision, we can use:

CL-USER> (ratmath:fractions (rationalize pi) :order 10)
2'd3/1'd1 45070.341 PPM
5'd22/3'd7 -402.499 PPM
8'd179/6'd57 395.270 PPM
9'd355/7'd113 -8.491D+1 PPB
16'd52163/15'd16604 8.474D+1 PPB
19'd312689/17'd99532 -9.277D-3 PPB
20'd833719/19'd265381 2.774D-3 PPB
21'd1146408/19'd364913 -5.127D-4 PPB
23'd5419351/21'd1725033 -7.074D-6 PPB
27'd80143857/25'd25510582 1.594D-7 PPB
28'd245850922/27'd78256779 0.000D-1 PPB

Pipe functions

A few public ratmath functions utilize a pattern unique to Common Lisp and return whats described in chapter 25, "Streams and Delayed Evaluation", in the book "Lisp, 3rd Edition" by Winston/Horn. The chapter describes a stream data structure (that I have renamed to "pipe" to avoid name clash confusion), that utilizes Lisp's lexical closures to create something akin to an infinite list. I have modeled much of the internal implementation of this library around the simple concepts described therein. Utilities to manipulate, map, filter, and transform these data structures are included in pipe.lisp and are made public in the ratmath package, though not specifically relating to the ratmath primary interfaces. These routines are superficially documented in pipe.lisp, though depending on familiarity with the above book or Lisp's lexical enclosures and functional programming paradigms, might either seem extremely trivial or extremely obtuse. This library was coded partly as an athletic challenge/experiment in avoiding all usage of iteration/loops/assignments in favor of recursion and functional programming. This (arbitrary) implementation constraint was simultaneously pleasing and frustrating and the pipe construct was an invaluable aid in realizing this.

The most likely useful pipe function is ratmath:rat-pipe, which takes as argument an input number and optional exponent base number which defaults to 2. This optional arg n filters out semi-convergents from the same power-of-n and only outputs the best approximation for each power-of-n increase in denominator/numerator.

CL-USER> (ratmath:rat-pipe pi 10)
(3 #<COMPILED-LEXICAL-CLOSURE (:INTERNAL RATMATH::PIPE-TRANSFORM) #x15B1D73E>)

Seeing the REPL output for this function shows that function returns a pipe. In the above, the number 3 is the first element and the second element is actually not an element at all, but a lexical closure that upon funcalling, will calculate and expose another rational + lexical closure, ad infinitum.

Since we know that this pipe is not infinite and has an end, we can safely convert the pipe into an ordinary list with (ratmath:pipe-to-list *) Note that the real pi, as an irrational number, has an infinite continued fraction and therefore an infinite pipe of rational approximations, but we are doing a rational approximation on Common Lisp's floating point constant which has finite precision and, therefore, a finite continued fraction.

CL-USER> (ratmath:pipe-to-list *)
(3 22/7 179/57 355/113 52163/16604 312689/99532 833719/265381 1146408/364913 
5419351/1725033 80143857/25510582 245850922/78256779 817696623/260280919
2698940791/859099536 9978066541/3176117225 32633140414/10387451211
238410049439/75888275702 747863288731/238052278317 1257316528023/400216280932
5777129400823/1838917402045 10296942273623/3277618523158
884279719003555/281474976710656)

The rat-pipe does allow for irrational number approximation, you simply have to create an infinite pipe of continued fraction terms to send as the first argument instead of an atomic real number. An example generator is in fractions.lisp in the function ratmath:napiers-constant-generator which returns the infinite terms of the continued fraction expansion of Euler's number e

CL-USER> (ratmath:rat-pipe (ratmath:napiers-constant-generator))
(3 #<COMPILED-LEXICAL-CLOSURE (:INTERNAL RATMATH::PIPE-TRANSFORM) #x15C8111E>)
CL-USER> (ratmath::pipe-sink-until 
          (lambda (x) (> (integer-length (denominator x)) 4096)) 
          *)
(41720850604724578859 .... ;; cut to not flood output with a 4096bit rational

Generating 8kbit integer rationals like this makes a good benchmark of Common Lisp and how well it handles its bignums. Letting your rationals grow in size to bignum territory likely will hurt performance significantly. Indeed, I would predict large gains in speed sprinking declare forms throughout the implementation of ratmath signifying intent to only ever use fixnums inputs and outputs.

Another useful pipe function generates lists of ordered rational fractions called Farey sequences. Wikipedia. The function ratmath:farey-pipe is used mostly for the implementation of infsup, but it is possible to use on its own, e.g. to list out a farey sequence of order 7 (no fraction denominator greater than 7):

CL-USER> (ratmath:pipe-to-list (ratmath:farey-pipe 7))
(1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1 7/6 
6/5 5/4 4/3 7/5 3/2 5/3 7/4 2 7/3 5/2 3 7/2 4 5 6 7)

Todo


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 ratmath

Author

Jesse Off <jesseoff@me.com>

License

MIT

Description

Math utilities for working with rational numbers and intervals.

Version

1

Source

ratmath.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 ratmath.asd

Location

ratmath.asd

Systems

ratmath (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 ratmath/package.lisp

Parent

ratmath (system)

Location

package.lisp

Packages

ratmath


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 ratmath/fifo.lisp

Dependency

package.lisp (file)

Parent

ratmath (system)

Location

fifo.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 ratmath/pipe.lisp

Dependency

fifo.lisp (file)

Parent

ratmath (system)

Location

pipe.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.5 ratmath/ratmath.lisp

Dependency

pipe.lisp (file)

Parent

ratmath (system)

Location

ratmath.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 ratmath

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Macros

Macro: infsup &rest ARGS

Returns infimum/supremum intervals. All strings and numbers in tree are converted keeping everything else intact. Exacts are fuzzified according to :tol and :abstol first, and then potentially widened further with :limd and :limn, which performs a rational approximation. Intervals already present in the structure, whether by explicit cons or via a string, will not be fuzzified further by :abstol and :tol, but they may be widened if rational approximation is called out via :limd/:limn args. Exact rationals will only convert to intervals if 1) their numerators/denominators exceed :limn/:limd or 2) an :open t arg is given. When the arg is an exact and rational approximation is called out, a 2nd value, alpha, is returned which is a number from 0-1 representing the location of the original exact in the returned interval.

Package

ratmath

Source

ratmath.lisp (file)

Macro: pipe-cons OBJECT PIPE
Package

ratmath

Source

pipe.lisp (file)

Macro: pipe-sink-until-condition PIPE &rest CONDS

Exposes elements of pipe until one of the condition types in conds is signalled. Returns nil for end of pipe, or 3 values: #1 being the interrupted pipe, #2 being the condition object, and #3 being the particular condition clause type in the original args that matched.

Package

ratmath

Source

pipe.lisp (file)

Macro: rat &rest ARGS

Performs a rational approximation of an exact number or interval. Takes keyword args :limn and :limd to represent max numerator and max denominator. Also will parse numeric strings into intervals ala parse-interval. Always returns an exact (i.e. not another interval).

Package

ratmath

Source

ratmath.lisp (file)

Macro: with-interval-math &rest BODY

Replaces arithmetic calls like *-/+ with interval*-/+ and turns ~##.## symbols into literal rational intervals with implied precision based on the number of digits after the decimal point. (as in parse-interval)

Package

ratmath

Source

ratmath.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Functions

Function: farey-pipe ()

Returns a farey sequence; 2nd value is an encapsulated reverse sequence

Package

ratmath

Source

ratmath.lisp (file)

Function: fractions ARG &key ORDER

Prints out rational approximations, one per line, with the PPM or PPB error.

Package

ratmath

Source

ratmath.lisp (file)

Function: hull &rest ARGS

Takes exacts and intervals as arguments and returns an interval enclosure containing the min/max. If the range between min and max is 0, hull will return an exact.

Package

ratmath

Source

ratmath.lisp (file)

Function: interval L U

Constructs an interval from the given lower/upper bounds

Package

ratmath

Source

ratmath.lisp (file)

Function: list-to-pipe ()

Returns a pipe from a list input argument.

Package

ratmath

Source

pipe.lisp (file)

Function: lower X

Returns the lower limit of an interval

Package

ratmath

Source

ratmath.lisp (file)

Function: napiers-constant-generator ()

Returns an infinite/irrational continued fraction expansion of Euler’s number ’e’

Package

ratmath

Source

ratmath.lisp (file)

Function: parse-interval ()

Turns strings of rationals or floats into rational intervals. Infers interval radius from number specification. e.g. 1.000 implies an interval of [.9995, 1.0005) whereas just 1 implies [.5, 1.5). Exponent notation is also recognized; 1e3 is [500, 1500) whereas 1000 is [999.5, 1000.5). A rational specified as 22/7 is converted as (43/14, 45/14).

Package

ratmath

Source

ratmath.lisp (file)

Function: pipe-append ()

Appends two pipes together

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-apply ()

Runs procedure on every element as they are exposed, but does not transform the element.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-end-after ()

Runs test on each element. When it returns t, the pipe is truncated after that element

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-end-before ()

Runs test on each element. When it returns t, the pipe is truncated before that element

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-endp PIPE
Package

ratmath

Source

pipe.lisp (file)

Function: pipe-filter ()

If procedure returns t, that particular pipe element is removed from the sequence.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-first PIPE
Package

ratmath

Source

pipe.lisp (file)

Function: pipe-head ()

Truncates a pipe after n (default: 1) elements

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-last ()
Package

ratmath

Source

pipe.lisp (file)

Function: pipe-mapc ()

Runs function on each element. Returns nothing.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-printer PIPE
Package

ratmath

Source

pipe.lisp (file)

Function: pipe-rest ()

Analogous to the rest function except works on a pipe rather than list

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-signaler ()

For each condition object in pipe, set up some useful restarts and signal it. If nothing handles it, the default behavior is to ignore. If the use-value restart is invoked, that value will be returned as a pipe datum element.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-sink ()

Exposes elements of pipe forever, ignoring the elements. Similar to pipe-mapc with a no-op procedure. Useful to provoke the pipeline processing of an infinite pipe.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-sink-until ()

Exposes elements of pipe until test returns t. When that happens, returns the (non-empty) pipe. If the pipe goes empty, returns nil. The test procedure is called with the current element as arg.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-to-list ()

Returns a list from the given pipe input argument. Infinite recursion results if the pipe is infinite.

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-transform ()

Runs procedure on each element of pipe; replacing each original element

Package

ratmath

Source

pipe.lisp (file)

Function: pipe-uniq ()

Removes duplicates according to optional predicate func. Only dups in sequence are removed.

Package

ratmath

Source

pipe.lisp (file)

Function: rat-pipe ()

Returns a pipe of best rational approximations for every power-of-mult numerator/denominator. If arg is not a number, assumes it is a continued fraction pipe.

Package

ratmath

Source

ratmath.lisp (file)

Function: upper X

Returns the upper limit of an interval

Package

ratmath

Source

ratmath.lisp (file)

Function: ~ &rest ARGS

Converts intervals into an exacts. :random picks a random value within the interval instead of the midpoint. :rat picks the first convergent rational fraction (which may not be the midpoint) :upper or :lower selects the upper or lower limit. :alpha modifies whats considered the midpoint of the interval. :discrete requests to only return one of either the lower or upper interval limit. By default, returns the midpoint. If passed in a list/tree, recursively modifies everything that looks like an interval and leaves everything else intact.

Package

ratmath

Source

ratmath.lisp (file)

Function: ~= A B

Compares either exacts or intervals for possible equality.

Package

ratmath

Source

ratmath.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Macros

Macro: best-convergent-test-fn &rest ARGS
Package

ratmath

Source

ratmath.lisp (file)

Macro: encapsulate FORM
Package

ratmath

Source

pipe.lisp (file)

Macro: expose PROCEDURE
Package

ratmath

Source

pipe.lisp (file)

Macro: fifo-get F

Removes and returns object from fifo. If fifo becomes empty, struct is destroyed, i.e. setf nil

Package

ratmath

Source

fifo.lisp (file)

Macro: fifo-put F OBJ

Adds obj to fifo, instantiating new fifo struct if necessary. Returns new count of fifo

Package

ratmath

Source

fifo.lisp (file)

Macro: interval~ &rest ARGS

When the ~ function is encounted within a with-interval-math block, it converts exacts to intervals. Outside of the lexical scope of a with-interval-math block, ~ converts intervals into exacts.

Package

ratmath

Source

ratmath.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: %infsup X &key LIMN LIMD TOL ABSTOL OPEN TEST-FN
Package

ratmath

Source

ratmath.lisp (file)

Function: %rat X &key LIMN LIMD TEST-FN
Package

ratmath

Source

ratmath.lisp (file)

Function: best-convergent ()

From a rationalized continued-fraction-pipe arg, returns best convergent honoring limits. 2nd value being the next best ignoring limits.

Package

ratmath

Source

ratmath.lisp (file)

Function: calc-stern-brocot N
Package

ratmath

Source

ratmath.lisp (file)

Function: continued-fraction-pipe ()

Returns a pipe of continued fraction terms from the input rational arg.

Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-a INSTANCE
Function: (setf convergent-a) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-cf INSTANCE
Function: (setf convergent-cf) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-denominator C
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-equal A B
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-fract C
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-numerator C
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-p OBJECT
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-q C
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-q-offset INSTANCE
Function: (setf convergent-q-offset) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-r0 INSTANCE
Function: (setf convergent-r0) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-r1 INSTANCE
Function: (setf convergent-r1) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-rat INSTANCE
Function: (setf convergent-rat) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-ratio C &aux F
Package

ratmath

Source

ratmath.lisp (file)

Function: convergent-stern-brocot C

From a convergent struct, make a Stern-Brocot struct by calculating the left and right parents

Package

ratmath

Source

ratmath.lisp (file)

Function: convergents-pipe ()

From a continued-fraction-pipe return a pipe of the resultant convergents.

Package

ratmath

Source

ratmath.lisp (file)

Function: copy-convergent INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: copy-fifo INSTANCE
Package

ratmath

Source

fifo.lisp (file)

Function: copy-stern-brocot INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: eval-constants ARGS &optional PURE-FUNCTION-SYMBOLP
Package

ratmath

Source

ratmath.lisp (file)

Function: fifo-count F
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-data INSTANCE
Function: (setf fifo-data) VALUE INSTANCE
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-endp F
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-head F
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-n INSTANCE
Function: (setf fifo-n) VALUE INSTANCE
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-p OBJECT
Package

ratmath

Source

fifo.lisp (file)

Function: fifo-tail INSTANCE
Function: (setf fifo-tail) VALUE INSTANCE
Package

ratmath

Source

fifo.lisp (file)

Function: functionalp FN &optional ARGS
Package

ratmath

Source

ratmath.lisp (file)

Function: infsup-limd ARG &key LIMD LIMN TEST-FN OPEN

Returns an infimum/supremum interval; 2nd value is alpha (>.5 when supremum is closer)

Package

ratmath

Source

ratmath.lisp (file)

Function: infsup-tol X ABSTOL &optional TOL

Returns an infimum/supremum interval given a tolerance.

Package

ratmath

Source

ratmath.lisp (file)

Function: interval* &rest ARGS
Package

ratmath

Source

ratmath.lisp (file)

Function: interval+ &rest ARGS
Package

ratmath

Source

ratmath.lisp (file)

Function: interval- &rest ARGS
Package

ratmath

Source

ratmath.lisp (file)

Function: interval/ &rest ARGS
Package

ratmath

Source

ratmath.lisp (file)

Function: intervalabs X
Package

ratmath

Source

ratmath.lisp (file)

Function: intervalexp X
Package

ratmath

Source

ratmath.lisp (file)

Function: intervalexpt X Y
Package

ratmath

Source

ratmath.lisp (file)

Function: intervallog X &optional N
Package

ratmath

Source

ratmath.lisp (file)

Function: intervalsqrt X
Package

ratmath

Source

ratmath.lisp (file)

Function: make-convergent CF R0 R1 A &optional Q-OFFSET
Package

ratmath

Source

ratmath.lisp (file)

Function: make-fifo &key (DATA DATA) (TAIL TAIL) (N N)
Package

ratmath

Source

fifo.lisp (file)

Function: make-semi-convergent Q-OFFSET C &aux CF R0 R1 A
Package

ratmath

Source

ratmath.lisp (file)

Function: make-stern-brocot LEFT-PARENT RIGHT-PARENT
Package

ratmath

Source

ratmath.lisp (file)

Function: my- A B
Package

ratmath

Source

ratmath.lisp (file)

Function: my-min &rest REST
Package

ratmath

Source

ratmath.lisp (file)

Function: my/ A B
Package

ratmath

Source

ratmath.lisp (file)

Function: rationalize-continued-fraction-pipe GENERATOR-PIPE

The normal continued-fraction-pipes have each term annotated with a lexical closure that returns the remainder to the terminal value. This value is used to qualify visiting iffy semi-convergents in a denominator/numerator limited rational approximation. With irrational numbers there is no end-value so we can give downpipe logic no insight as to whether an iffy semi-convergent is worthy.

Package

ratmath

Source

ratmath.lisp (file)

Function: semi-convergent-closest-to-lim ()

From a specific convergent, check semi-convergents for one below num/denom limits

Package

ratmath

Source

ratmath.lisp (file)

Function: semi-convergent-iffy-p C

Iffy semi-convergents are the exactly 1/2 CF semi-convergent of even terms.

Package

ratmath

Source

ratmath.lisp (file)

Function: semi-convergent-p C

Semi-convergents are convergents with a truncated (up to 1/2) CF term

Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-denominator SB
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-fract SB
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-left-parent INSTANCE
Function: (setf stern-brocot-left-parent) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-numerator SB
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-p OBJECT
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-ratio SB
Package

ratmath

Source

ratmath.lisp (file)

Function: stern-brocot-right-parent INSTANCE
Function: (setf stern-brocot-right-parent) VALUE INSTANCE
Package

ratmath

Source

ratmath.lisp (file)

Function: truncate-within-interval ()

Takes 2 continued-fraction-pipes and returns one that stops at the simplest rational inbetween

Package

ratmath

Source

ratmath.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Structures

Structure: convergent ()

Represents a (semi-)convergent in the rational approximation of a continued fraction.

Package

ratmath

Source

ratmath.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: cf
Readers

convergent-cf (function)

Writers

(setf convergent-cf) (function)

Slot: r0
Readers

convergent-r0 (function)

Writers

(setf convergent-r0) (function)

Slot: r1
Readers

convergent-r1 (function)

Writers

(setf convergent-r1) (function)

Slot: q-offset
Type

integer

Initform

0

Readers

convergent-q-offset (function)

Writers

(setf convergent-q-offset) (function)

Slot: a
Readers

convergent-a (function)

Writers

(setf convergent-a) (function)

Slot: rat
Readers

convergent-rat (function)

Writers

(setf convergent-rat) (function)

Structure: fifo ()
Package

ratmath

Source

fifo.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: data
Type

list

Readers

fifo-data (function)

Writers

(setf fifo-data) (function)

Slot: tail
Type

list

Readers

fifo-tail (function)

Writers

(setf fifo-tail) (function)

Slot: n
Type

fixnum

Initform

0

Readers

fifo-n (function)

Writers

(setf fifo-n) (function)

Structure: stern-brocot ()

Stern-Brocot left/right parent used to address a node in the Stern-Brocot fraction tree.

Package

ratmath

Source

ratmath.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: left-parent
Readers

stern-brocot-left-parent (function)

Writers

(setf stern-brocot-left-parent) (function)

Slot: right-parent
Readers

stern-brocot-right-parent (function)

Writers

(setf stern-brocot-right-parent) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   R  
Index Entry  Section

F
File, Lisp, ratmath.asd: The ratmath․asd file
File, Lisp, ratmath/fifo.lisp: The ratmath/fifo․lisp file
File, Lisp, ratmath/package.lisp: The ratmath/package․lisp file
File, Lisp, ratmath/pipe.lisp: The ratmath/pipe․lisp file
File, Lisp, ratmath/ratmath.lisp: The ratmath/ratmath․lisp file

L
Lisp File, ratmath.asd: The ratmath․asd file
Lisp File, ratmath/fifo.lisp: The ratmath/fifo․lisp file
Lisp File, ratmath/package.lisp: The ratmath/package․lisp file
Lisp File, ratmath/pipe.lisp: The ratmath/pipe․lisp file
Lisp File, ratmath/ratmath.lisp: The ratmath/ratmath․lisp file

R
ratmath.asd: The ratmath․asd file
ratmath/fifo.lisp: The ratmath/fifo․lisp file
ratmath/package.lisp: The ratmath/package․lisp file
ratmath/pipe.lisp: The ratmath/pipe․lisp file
ratmath/ratmath.lisp: The ratmath/ratmath․lisp file

Jump to:   F   L   R  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (   ~  
B   C   E   F   H   I   L   M   N   P   R   S   T   U   W  
Index Entry  Section

%
%infsup: Internal functions
%rat: Internal functions

(
(setf convergent-a): Internal functions
(setf convergent-cf): Internal functions
(setf convergent-q-offset): Internal functions
(setf convergent-r0): Internal functions
(setf convergent-r1): Internal functions
(setf convergent-rat): Internal functions
(setf fifo-data): Internal functions
(setf fifo-n): Internal functions
(setf fifo-tail): Internal functions
(setf stern-brocot-left-parent): Internal functions
(setf stern-brocot-right-parent): Internal functions

~
~: Exported functions
~=: Exported functions

B
best-convergent: Internal functions
best-convergent-test-fn: Internal macros

C
calc-stern-brocot: Internal functions
continued-fraction-pipe: Internal functions
convergent-a: Internal functions
convergent-cf: Internal functions
convergent-denominator: Internal functions
convergent-equal: Internal functions
convergent-fract: Internal functions
convergent-numerator: Internal functions
convergent-p: Internal functions
convergent-q: Internal functions
convergent-q-offset: Internal functions
convergent-r0: Internal functions
convergent-r1: Internal functions
convergent-rat: Internal functions
convergent-ratio: Internal functions
convergent-stern-brocot: Internal functions
convergents-pipe: Internal functions
copy-convergent: Internal functions
copy-fifo: Internal functions
copy-stern-brocot: Internal functions

E
encapsulate: Internal macros
eval-constants: Internal functions
expose: Internal macros

F
farey-pipe: Exported functions
fifo-count: Internal functions
fifo-data: Internal functions
fifo-endp: Internal functions
fifo-get: Internal macros
fifo-head: Internal functions
fifo-n: Internal functions
fifo-p: Internal functions
fifo-put: Internal macros
fifo-tail: Internal functions
fractions: Exported functions
Function, %infsup: Internal functions
Function, %rat: Internal functions
Function, (setf convergent-a): Internal functions
Function, (setf convergent-cf): Internal functions
Function, (setf convergent-q-offset): Internal functions
Function, (setf convergent-r0): Internal functions
Function, (setf convergent-r1): Internal functions
Function, (setf convergent-rat): Internal functions
Function, (setf fifo-data): Internal functions
Function, (setf fifo-n): Internal functions
Function, (setf fifo-tail): Internal functions
Function, (setf stern-brocot-left-parent): Internal functions
Function, (setf stern-brocot-right-parent): Internal functions
Function, best-convergent: Internal functions
Function, calc-stern-brocot: Internal functions
Function, continued-fraction-pipe: Internal functions
Function, convergent-a: Internal functions
Function, convergent-cf: Internal functions
Function, convergent-denominator: Internal functions
Function, convergent-equal: Internal functions
Function, convergent-fract: Internal functions
Function, convergent-numerator: Internal functions
Function, convergent-p: Internal functions
Function, convergent-q: Internal functions
Function, convergent-q-offset: Internal functions
Function, convergent-r0: Internal functions
Function, convergent-r1: Internal functions
Function, convergent-rat: Internal functions
Function, convergent-ratio: Internal functions
Function, convergent-stern-brocot: Internal functions
Function, convergents-pipe: Internal functions
Function, copy-convergent: Internal functions
Function, copy-fifo: Internal functions
Function, copy-stern-brocot: Internal functions
Function, eval-constants: Internal functions
Function, farey-pipe: Exported functions
Function, fifo-count: Internal functions
Function, fifo-data: Internal functions
Function, fifo-endp: Internal functions
Function, fifo-head: Internal functions
Function, fifo-n: Internal functions
Function, fifo-p: Internal functions
Function, fifo-tail: Internal functions
Function, fractions: Exported functions
Function, functionalp: Internal functions
Function, hull: Exported functions
Function, infsup-limd: Internal functions
Function, infsup-tol: Internal functions
Function, interval: Exported functions
Function, interval*: Internal functions
Function, interval+: Internal functions
Function, interval-: Internal functions
Function, interval/: Internal functions
Function, intervalabs: Internal functions
Function, intervalexp: Internal functions
Function, intervalexpt: Internal functions
Function, intervallog: Internal functions
Function, intervalsqrt: Internal functions
Function, list-to-pipe: Exported functions
Function, lower: Exported functions
Function, make-convergent: Internal functions
Function, make-fifo: Internal functions
Function, make-semi-convergent: Internal functions
Function, make-stern-brocot: Internal functions
Function, my-: Internal functions
Function, my-min: Internal functions
Function, my/: Internal functions
Function, napiers-constant-generator: Exported functions
Function, parse-interval: Exported functions
Function, pipe-append: Exported functions
Function, pipe-apply: Exported functions
Function, pipe-end-after: Exported functions
Function, pipe-end-before: Exported functions
Function, pipe-endp: Exported functions
Function, pipe-filter: Exported functions
Function, pipe-first: Exported functions
Function, pipe-head: Exported functions
Function, pipe-last: Exported functions
Function, pipe-mapc: Exported functions
Function, pipe-printer: Exported functions
Function, pipe-rest: Exported functions
Function, pipe-signaler: Exported functions
Function, pipe-sink: Exported functions
Function, pipe-sink-until: Exported functions
Function, pipe-to-list: Exported functions
Function, pipe-transform: Exported functions
Function, pipe-uniq: Exported functions
Function, rat-pipe: Exported functions
Function, rationalize-continued-fraction-pipe: Internal functions
Function, semi-convergent-closest-to-lim: Internal functions
Function, semi-convergent-iffy-p: Internal functions
Function, semi-convergent-p: Internal functions
Function, stern-brocot-denominator: Internal functions
Function, stern-brocot-fract: Internal functions
Function, stern-brocot-left-parent: Internal functions
Function, stern-brocot-numerator: Internal functions
Function, stern-brocot-p: Internal functions
Function, stern-brocot-ratio: Internal functions
Function, stern-brocot-right-parent: Internal functions
Function, truncate-within-interval: Internal functions
Function, upper: Exported functions
Function, ~: Exported functions
Function, ~=: Exported functions
functionalp: Internal functions

H
hull: Exported functions

I
infsup: Exported macros
infsup-limd: Internal functions
infsup-tol: Internal functions
interval: Exported functions
interval*: Internal functions
interval+: Internal functions
interval-: Internal functions
interval/: Internal functions
intervalabs: Internal functions
intervalexp: Internal functions
intervalexpt: Internal functions
intervallog: Internal functions
intervalsqrt: Internal functions
interval~: Internal macros

L
list-to-pipe: Exported functions
lower: Exported functions

M
Macro, best-convergent-test-fn: Internal macros
Macro, encapsulate: Internal macros
Macro, expose: Internal macros
Macro, fifo-get: Internal macros
Macro, fifo-put: Internal macros
Macro, infsup: Exported macros
Macro, interval~: Internal macros
Macro, pipe-cons: Exported macros
Macro, pipe-sink-until-condition: Exported macros
Macro, rat: Exported macros
Macro, with-interval-math: Exported macros
make-convergent: Internal functions
make-fifo: Internal functions
make-semi-convergent: Internal functions
make-stern-brocot: Internal functions
my-: Internal functions
my-min: Internal functions
my/: Internal functions

N
napiers-constant-generator: Exported functions

P
parse-interval: Exported functions
pipe-append: Exported functions
pipe-apply: Exported functions
pipe-cons: Exported macros
pipe-end-after: Exported functions
pipe-end-before: Exported functions
pipe-endp: Exported functions
pipe-filter: Exported functions
pipe-first: Exported functions
pipe-head: Exported functions
pipe-last: Exported functions
pipe-mapc: Exported functions
pipe-printer: Exported functions
pipe-rest: Exported functions
pipe-signaler: Exported functions
pipe-sink: Exported functions
pipe-sink-until: Exported functions
pipe-sink-until-condition: Exported macros
pipe-to-list: Exported functions
pipe-transform: Exported functions
pipe-uniq: Exported functions

R
rat: Exported macros
rat-pipe: Exported functions
rationalize-continued-fraction-pipe: Internal functions

S
semi-convergent-closest-to-lim: Internal functions
semi-convergent-iffy-p: Internal functions
semi-convergent-p: Internal functions
stern-brocot-denominator: Internal functions
stern-brocot-fract: Internal functions
stern-brocot-left-parent: Internal functions
stern-brocot-numerator: Internal functions
stern-brocot-p: Internal functions
stern-brocot-ratio: Internal functions
stern-brocot-right-parent: Internal functions

T
truncate-within-interval: Internal functions

U
upper: Exported functions

W
with-interval-math: Exported macros

Jump to:   %   (   ~  
B   C   E   F   H   I   L   M   N   P   R   S   T   U   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   A   C   D   L   N   Q   R   S   T  
Index Entry  Section

A
a: Internal structures

C
cf: Internal structures

D
data: Internal structures

L
left-parent: Internal structures

N
n: Internal structures

Q
q-offset: Internal structures

R
r0: Internal structures
r1: Internal structures
rat: Internal structures
right-parent: Internal structures

S
Slot, a: Internal structures
Slot, cf: Internal structures
Slot, data: Internal structures
Slot, left-parent: Internal structures
Slot, n: Internal structures
Slot, q-offset: Internal structures
Slot, r0: Internal structures
Slot, r1: Internal structures
Slot, rat: Internal structures
Slot, right-parent: Internal structures
Slot, tail: Internal structures

T
tail: Internal structures

Jump to:   A   C   D   L   N   Q   R   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   F   P   R   S  
Index Entry  Section

C
convergent: Internal structures

F
fifo: Internal structures

P
Package, ratmath: The ratmath package

R
ratmath: The ratmath system
ratmath: The ratmath package

S
stern-brocot: Internal structures
Structure, convergent: Internal structures
Structure, fifo: Internal structures
Structure, stern-brocot: Internal structures
System, ratmath: The ratmath system

Jump to:   C   F   P   R   S