## Self-Locating Strings In Pi

### January 4, 2019

We have written several programs that compute the digits of π, including this one just a week after the inception of Programming Praxis, based on a spigot algorithm of Jeremy Gibbons:

(define (pi-spigot z) (let loop ((z z) (ds '()) (q 1) (r 0) (t 1) (k 1) (n 3) (m 3)) (cond ((zero? z) (reverse ds)) ((< (+ q q q q r (- t)) (* n t)) (loop (- z 1) (cons n ds) (* 10 q) (* 10 (- r (* n t))) t k (- (quotient (* 10 (+ q q q r)) t) (* 10 n)) m)) (else (loop z ds (* q k) (* (+ q q r) m) (* t m) (+ k 1) (quotient (+ (* q (+ k k k k k k k 2)) (* r m)) (* t m)) (+ m 2))))))

It takes about ten minutes to compute the first 50,000 digits of π:

> (define pi (pi-spigot 50000))

Then it’s just a matter of indexing through the digits and checking for self-locating indices:

> (do ((n 0 (+ n 1)) (ps (cdr pi) (cdr ps))) ((null? ps)) (let* ((ds (digits n)) (len (length ds))) (when (equal? ds (take len ps)) (display n) (newline)))) 0 6 27 13598 43611

The initial 0 surprised me. When *n* = 0, `digits`

returns `()`

. But then the length of the digit string is 0, so `take`

returns a null list, which is `equal?`

to `ds`

, so 0 is a proper result. Which it isn’t. I guess that’s a design bug in `digits`

.

You can run the program at https://ideone.com/TnoBhB.

I’m glad your getting better, back at work, and had family time at Christmas.

I came across your website because mine’s called https://www.praxismachinecodinglessons.com

Adapting your coding challenges to developing curriculum for high school computer science teachers and students will be a main theme of mine in 2019.

I’ll keep you posted,

Peter L.

________________________________

Hi Phil, welcome back.

I cheated a little with this exercise and downloaded 1 million digits from the internet. Results were the same as from @programmingpraxis. Running time is about 4 seconds.

$ date && awk ‘END { for (i = 0; i <= 999999; i++) { len = log(i)/log(10); len = int(len) + 1; str = substr($0,i+1,len); if (str ==i) print str } }’ value_of_pi.txt && date

Fri, Jan 4, 2019 10:32:49 AM

6

27

13598

43611

Fri, Jan 4, 2019 10:32:50 AM

AWK version

test

Welcome back @programmingpraxis, and Hacky New Year to all.

For the digits of pi, I cheated and used Simon Tatham’s excellent

‘spigot’ program to do the real work, so my main code isn’t much worth

posting. However, apropos the digits bug you mention, here’s the

simple implementation in R7RS Scheme and SRFI 8 (for receive) from my

homegrown utility library.

Great to have you back again! Hope recovery continues to go well.

Interesting problem, never really looked at generation of digits of pi before. The Gibbons spigot is neat but seems to slow down drastically as we get further into the number – lots of very large numbers in the internal state that presumably are needed for later digits. The Machin formula is neat as we can just sum lot of reciprocals to get our approximation, using some sort of fixed-point representation. I tried some of the “optimal” Machin formulas, but there wasn’t an enormous speedup that I saw (maybe 20-30%) so stuck with the original 1706 method: