Zach Rottman, PhD

Developer
Data Enthusiast
Art Historian

4 minute read

Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023

Today while meeting with my SICP group mates I learned about piecewise functions.

Some background

Some background before getting to the problem at hand. The initial task was to come up with a procedure for an infinite continued fraction like this:

\[f = \frac{N_1}{D_1 + \cfrac{N_2}{D_2 + \cfrac{N_3}{D_3 + ...}}}\]

In this case, N and D are not not meant to be numbers but functions of index i. As we’ll see, this will make the infinite fraction procedure more flexible and allow us to use it to approximate several things.

For example, when \(N_i\) and \(D_i\) always return 1, the result of this equation approximates \(\frac{1}{\phi}\), where \(\phi\) is the golden ratio. Since this equation (as its name implies) is infinite, the procedure we’re tasked with writing will compute a truncated version according to parameter k:

\[f = \frac{N_1}{D_1 + \cfrac{N_2}{... + \cfrac{N_k}{D_k}}}\]

In other words, it will iterate k times.

Here’s my implementation for both recursive and iterative approaches:

; recursive implementation
(define (cont-frac n d k)
  (define (iter n d k i)
    (if (= k 0)
      (/ (n i) (d i))
      (/ (n i)
         (+ (d i)
            (iter n d (- k 1) (+ i 1))))))
  (iter n d k 1))

; iterative implementation
(define (cont-frac-iter n d k)
  (define (iter n d k i cur)
    (if (= i k)
      cur
      (iter n d k (+ 1 i) (/ (n i) (+ (d i) cur)))))
  (iter n d k 0 (/ (n k) (d k))))

Either of these can be called to estimate \(\phi\) like so, where k is the number of iterations desired:

(/ 1 (cont-frac (lambda (i) 1.0)
                 (lambda (i) 1.0)
                 k))

Again, n and d are procedures, not variables. In the case of this golden ratio approximation algorithm, they are constant – \(N(\imath) = 1\) and \(D(\imath) = 1\) for all values i – but they are procedures nonetheless. That’s why we pass to cont-frac the two identical lambda functions for n and d respectively that return 1 regardless of i.

What’s cool is that the above approximates \(\phi\) to 4 decimal places in 11 iterations.

(/ 1 (cont-frac (lambda (i) 1.0)
                 (lambda (i) 1.0)
                 11))

;Value: 1.6180555555555558

Piecewise Functions

This brings us to the next puzzle. Using the same infinite fraction procedure cont-frac, we can approximate \(e - 2\) where \(N(\imath) = 1\) (that’s the same lambda function used above) and \(D(\imath)\) returns the following sequence: 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …

The latter pattern is obvious to me, but my question was how to derive a function that will result in such a sequence.

I’m very grateful that one of my group mates is a mathematician with a talent for patiently stepping through math problems. Turns out what we need is something called a piecewise function. Here’s my attempt to reconstruct his process for arriving at the answer.

His approach was to create a table with the index in one column and the expected value in the next:

i D(i)
1 1
2 2
3 1
4 1
5 4
6 1
7 1
8 6
9 1
10 1
11 8

The first observation to make is that D(i) is constant (\(D(\imath) = 1\)) when \(\imath \bmod 3 \neq 2\).

Let’s look at the remaining table:

i D(i)
2 2
5 4
8 6
11 8
14 10

What’s the rule here? Well, \(D(\imath) = (\imath // 3) \cdot 2 + 2\) where ‘//’ is integer division, meaning that the answer is rounded down. We can also write the equation using floor function notation like so: \(D(\imath) = 2 \cdot \lfloor \frac{\imath}{3} \rfloor + 2\)

i D(i) i // 3 (i // 3) * 2 + 2
2 2 0 0 * 2 + 2 = 2
5 4 1 1 * 2 + 2 = 4
8 6 2 2 * 2 + 2 = 6
11 8 3 3 * 2 + 2 = 8
14 10 4 4 * 2 + 2 = 10

Thanks to that insight, I managed to implement my own solution to this Euler number-estimation problem.

(define (euler k)
  (define (d-seq i)
    (if (not (= 2 (remainder i 3)))
      1
      (+ 2
         (* 2
            (floor (/ i 3))))))
  (+ 2 (cont-frac (lambda (i) 1.0)
                  d-seq
                  k)))

(euler 10)

;Value: 2.7182818352059925

Looks pretty Euler-y to me.

A Piecewise Approach to pi

Now that I understood how to approach a piecewise function, I could tackle the following approach to approximating \(\pi\):

\[\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdot ...}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdot ...}\]

The numerator and denominator sequences here look suspiciously piecewise.

Here’s my solution:

\[N(\imath) = 2 + 2 \cdot \lfloor \frac{\imath}{2} \rfloor \\ D(\imath) = 3 + 2 \cdot \lfloor \frac{(\imath - 1)}{2} \rfloor\]

Thus, in scheme:

(define (product term a next b)
  (if (> a b)
    1
    (* (term a)
       (product term (next a) next b))))

(define (inc x) (+ x 1))

(define (pi-term i)
  (let ((numer (+ 2. (* 2 (floor (/ i 2)))))
        (denom (+ 3. (* 2 (floor (/ (- i 1) 2))))))
    (/ numer denom)))

(define (pi-approx n)
  (* 4 (product pi-term 1 inc n)))

(pi-approx 200)

;Value: 3.149378473168593

Takes a while to converge, but we’re getting there.

Other stuff

  • paired on some EDA in prep for feature selection/engineering for a random forest project I have in the works
  • SICP meeting
  • data disco
  • weekly presentations