# RC19. Piecewise Functions

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

:

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