# Justin Does SICP

**URL:** https://discuss.criticalfallibilism.com/t/justin-does-sicp/96
**Category:** Friendly
**Tags:** learning, coding
**Created:** [May 15, 2021, 1:34am UTC](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96 "2021-05-15T01:34:56Z")
**Posts on this page:** 1
**Showing post:** 41

<div class="post-metadata">

### Author: ![Max](https://discuss.criticalfallibilism.com/user_avatar/discuss.criticalfallibilism.com/max/32/97_2.png) [@Max](https://discuss.criticalfallibilism.com/u/Max)
#### Post date: [May 25, 2021, 4:25am UTC](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96/41 "2021-05-25T04:25:31Z")

</div>

From [https://blog.justinmallone.com/sicp-12-procedures-and-the-processes-they-generate-part-1/](https://blog.justinmallone.com/sicp-12-procedures-and-the-processes-they-generate-part-1/)

> What exactly was the relevance of the golden ratio in understanding the inefficiency of the recursive fibonacci procedure? Quote of relevant material:
> 
> > In fact, it is not hard to show that the number of times the procedure will compute `(fib 1)` or `(fib 0)` (the number of leaves in the above tree, in general) is precisely Fib(n + 1). To get an idea of how bad this is, one can show that the value of _Fib_(_n_) grows exponentially with _n_ . More precisely (see exercise [1.13](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%25_thm_1.13)), _Fib(n)_ is the closest integer to \phi^5/\sqrt{n}, where …

From the book (for context):

> **Exercise 1.13.** Prove that Fib(n) is the closest integer to \phi^n/\sqrt{5}, where \phi = (1+\sqrt{5})/2. Hint: let \psi = (1 - \sqrt{5})/2 Use induction and the definition of the Fibonacci numbers (see section [1.2.2](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%25_sec_1.2.2)) to prove that Fib(n) = (\phi^n - \psi^n)/\sqrt{5}.

I think the point of saying that Fib(n) \approx \phi^n/\sqrt{5} was to show specifically how Fib(n) grows exponentially with n and to ~foreshadow exercise 1.13.

Exercise 1.13 doesn’t seem _that_ useful as a coding exercise, except insofar as rigorously analyzing the complexity of the `fib` function, via Fib. That skill seems more relevant for like academics and ppl doing theoretical comp sci. That sort of thing doesn’t come up in day-to-day programming (though being able to analyze an algorithms complexity does; in this case the complexity is O(c^n) for some constant c; _edit: you don’t need to know what this means; I included it so that you could see the difference between more simplistic day-to-day complexity stuff and like in-depth analysis_)

IDK if that answers your q

---

_[View the full topic](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96)._