4 Custom Continued Fractions

7.7

top ← prev up next →

4 Custom Continued Fractions

(require continued-fractions/create)
	package: continued-fractions

4.1 Creation Concepts

4.1.1 Creation Introduction

There are two standard types of continued fractions. Simple continued fractions are of the form a0 + 1/(a1 + 1/(a2 + ...)). General continued fractions are of the form d0 + n0/(d1 + n1/(d2 + ...)). This library offers some procedures, sequence utilities, and sequences to help you make your own continued fractions.

4.1.2 Creation Caveats

As mentioned in the main introduction, continued fractions in this library generally only allow the first non-zero term to be negative. Short of enumerating all the terms of a sequence, there is no way to guarantee this. Thus, hand-crafted continued fractions for exploratory purposes may violate some assumptions of this library.

This library operates under the additional assumption that all generated terms of continued fractions are exact integers. One may always transform an arbitrary continued fraction with rational terms to one with integer terms. For instance, in the continued fraction 1 + (3/2)/(1 + ...) the denominator of 2 can be eliminated by multiplying this portion of the continued fraction by 2/2, giving 1 + 3/(2 + (2* ...)).

4.2 Provided Sequences

The forms provided by racket/sequence are recommended but not provided. In particular, many continued fractions have initial terms that do not follow a pattern, while subsequent terms do, so sequence-append is helpful. Additionally, some specific sequences are given.

4.2.1 Sequence Utilities

procedure
(sequence-map* p s ...) → sequence?
p : procedure?
s : sequence?

Like map, but for sequences. If any sequence dies, then this sequence dies, since it can no longer be guaranteed to succeed in applying the procedure argument.

Examples:

> (require racket/sequence)
> (let ((S (sequence-map* + (in-naturals 0) (in-naturals 0) (in-range 5))))
(sequence->list S))
'(0 3 6 9 12)

procedure
(every-other s) → sequence?
s : sequence?

Omits every other term.

Example:

> (sequence->list (every-other (in-range 10)))
'(0 2 4 6 8)

procedure
(interleave s ...) → sequence?
s : sequence?

Takes a term from each sequence in argument order before continuing any sequence. If any sequence dies it is culled from the interleaving action and the main sequence continues until there are no inner sequences left producing terms.

Example:

> (sequence->list
(interleave (in-range 0 10) (in-range 10 15) (in-range 100 103)))
'(0 10 100 1 11 101 2 12 102 3 13 4 14 5 6 7 8 9)

4.2.2 Specific Sequences

procedure
(endless-values v) → sequence?
v : any/c

Endless values of the argument.

procedure
(in-evens v) → sequence?
v : (and/c exact-integer? even?)

procedure
(in-odds v) → sequence?
v : (and/c exact-integer? odd?)

Sequences of even and odd numbers, respectively.

Examples:

> (for/list ((t (in-evens 10))
             (i (in-range 10)))
    t)
'(10 12 14 16 18 20 22 24 26 28)
> (for/list ((t (in-odds 9))
             (i (in-range 10)))
    t)
'(9 11 13 15 17 19 21 23 25 27)

procedure
(in-squares v) → sequence?
v : number?

An endless sequence of squares, starting with the first square that is greater than or equal to the argument.

Examples:

> (for/list ((s (in-squares 9))
             (i (in-range 10)))
    s)
'(9 16 25 36 49 64 81 100 121 144)
> (for/list ((s (in-squares 8))
             (i (in-range 10)))
    s)
'(9 16 25 36 49 64 81 100 121 144)

procedure
(in-cubes v) → sequence?
v : number?

Like sqaures.

Example:

> (for/list ((c (in-cubes 0))
(i (in-range 10)))
c)
'(0 1 8 27 64 125 216 343 512 729)

procedure
(in-triangle v) → sequence?
v : number?

A sequence of triangle numbers. Triangle numbers are of the form (n*(n+1))/2.

procedure
(in-double-triangle v) → sequence?
v : number?

A sequence of triangle numbers multiplied by 2.

Examples:

> (for/list ((t (in-triangle 0))
             (i (in-range 10)))
    t)
'(0 1 3 6 10 15 21 28 36 45)
> (equal? (for/list ((t (in-triangle 0))
                     (i (in-range 10)))
            (* 2 t))
          (for/list ((t (in-double-triangle 0))
                     (i (in-range 10)))
            t))
#t

procedure
(in-common-difference init
base-sequence
[ #:strip-until strip]) → sequence?
  init : (and/c exact? integer?)
  base-sequence : sequence?
  strip : (or/c #f (and/c exact? integer?)) = #f

The first term is init. The second term is init plus the first term of the base-sequence. The third term is the second term plus the second term of the base-sequence. And so on. The optional argument, if present, will automatically go through the sequence until the term is greater than or equal to strip.

Examples:

> (sequence->list (in-common-difference 0 (in-range 10)))
'(0 0 1 3 6 10 15 21 28 36 45)
> (for/list ((t (in-common-difference
                 0 (in-common-difference
                    1 (in-common-difference
                       6 (endless-values 6)))))
             (i (in-range 10)))
    t)
'(0 1 8 27 64 125 216 343 512 729)

4.3 Continued Fraction Creation

4.3.1 Continued Fraction Procedures

Two main forms are provided for continued fractions.

procedure
(sequence->simple-continued-fraction s
[ #:force count])
→ continued-fraction?
  s : sequence?
   count :
(or/c #f
      (and/c exact? positive? integer?))
= #f

Creates the continued fraction a0 + 1/(a1 + 1/(a2 + ...)) from the given sequence. For the keyword argument, see Forcing.

procedure
(sequences->general-continued-fraction d
n
[ #:force count])
→ continued-fraction?
  d : sequence?
  n : sequence?
   count :
(or/c #f
      (and/c exact? positive? integer?))
= #f

Creates the continued fraction d0 + n0/(d1 + n1/(d2 + ...)) from the d and n sequences. For the keyword argument, see Forcing.

4.3.2 Forcing

Well-behaved continued fractions have terms which are always positive or always negative. Unfortunately this is not always the case. Sometimes there is a crossover where some terms switch from being positive to being negative. A sequence provided may at some point emit a zero at a known location. Such terms can cause havoc with continued fraction arithmetic. For that reason, the #:force keyword is provided. It allows the user to internally force the consumption of the specified number of terms before any arithmetic or other output is attempted. This overrides any precision or consume-limit parameters.

As an example, the continued fraction (-3 -2 -1 0 1 2 3 ...) is equivalant to (-3 -2 0 2 3 ...) which is eventually just (0 4 5 6 ...). Since internal algorithms assume that no zeros will appear, emission of a term from a continued fraction sequence may occur prematurely if #:force is not used.

Such emission does not affect the accuracy of continued fraction arithmetic, but it does invalidate guarantees of precision-emit or the correctness of terms given by base-emit.

Examples:

> (define bad-cf
    (sequence->simple-continued-fraction (in-range -5 15)))
> (sequence->list bad-cf)
'(-6 1 3 3 0 -4 1 3 5 6 7 8 9 10 11 12 13 14)
> (define good-cf
    (sequence->simple-continued-fraction (in-range -5 15) #:force 11))
> (sequence->list good-cf)
'(0 6 7 8 9 10 11 12 13 14)
; The overall accuracy of arithmetic is not affected:
; these are both valid representations of the same rational.
> (= (cf-terms->rational (sequence->list bad-cf))
     (cf-terms->rational (sequence->list good-cf)))
#t
> (for/list ((t (base-emit bad-cf 10))
             (i (in-range 20)))
    t)
'(-5 -2 536 2 8 5 6 2 5 7 6 5 8 9 0 6 5 1 0 5)
> (for/list ((t (base-emit good-cf 10))
             (i (in-range 20)))
    t)
'(0 1 6 2 8 5 6 2 5 7 6 5 8 9 0 6 5 1 0 5)

top ← prev up next →

1	Concepts
2	Use
3	Base Conversion Package
4	Custom Continued Fractions

4.1	Creation Concepts
4.2	Provided Sequences
4.3	Continued Fraction Creation