DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,155 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
tang
tang

Posted on

What I learned today (SICP 1.1)

Sadly, this series is not written for anyone except me, as a way of tracking my progress while I teach myself some computer science fundamentals. You've been warned.

I'm working through the venerable SICP, using the book and this playlist and doing the exercises in the book as homework. Today I've covered chapter 1.1

I'm using Jupyter Notebook with the MIT-Scheme-Kernel via a docker image. I've had to do a bit of digging to understand how to get it to persist, though. Here's a script I wrote to run the notebook, forward port 8888 (the one used by Jupyter), and persist the notebooks that I make at whatever you fill in for <host filepath>

This is, of course, assuming you've got docker installed. it'll handle the rest.

#!bin/bash

docker run --rm -it -p 8888:8888 -v <host filepath>:/work kkwok/jupyter-mit-scheme 
Enter fullscreen mode Exit fullscreen mode

So, what did I actually learn today?

We did an exercise where we built a function to do an approximation of the value of a square root. The initial version of this would start from some arbitrary guess, check if guess * guess is within some proximity of the number we're trying to sqrt, then improve it if not, and try the whole process over again.

One thing I learned was that we're making implicit assumptions about the problem when we decide on the threshold for a "close enough" guess. If we want the guess to be within 0.001 of the real target, well- what if our number is huge, like 123801983120? It'll take forever to get close enough to be within 1 of the target, let alone 0.001! Same goes for small numbers. If we're trying to find the square root of 0.0001, any number we guess will probably always be within the threshold, making it worthless!

So, what do we do? the answer is that we look not at an absolute closeness, but a relative closeness; what percent does our guess change? That'll scale regardless of whether the number itself is actually big or small. Brilliant.

Okay, so now that that's out of the way, what else is there to learn?

The sqrt function we wrote is composed of a couple of different pieces. it's composed of sqrt, the "main" function, and its dependencies close-enough? and improve-guess, which check if we're close enough to the target, and get us closer to our target respectively.

the main sqrt function itself- if you think about it, all of the domain specific stuff for finding a square root is encapsulated in close-enough and improve-guess, which are what determines where the number goes and when it's there. That's a process that isn't about square roots. it's about iterative approximation.

The last exercise of ch 1.2 was to build a cube root approximation function. we were given (x/(y^2) + 2y)/3 as a formula for improving a guess at a cube root, when we're trying to get to y^3 = x

All that we actually need to do is replace the improve-guess function with one that carries out this process, and it frickin' works.

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.