'Build Your Own Lisp' Solutions: 3.12

Q: What does the 'typedef' keyword do exactly?


A: 'typedef' lets you define a type, which is to say, it lets you give a new name to a pre-existing type (which can be useful for organizational/readability purposes), or to define a struct as a new type, unique to your program.



SICP Solutions - 1.7

Q: Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value:

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)


A:

;; The setup is the same, except for the names.
(define (cbrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (cbrt-iter (improve guess x)
               x)))

(define (cube x)
  (* x x x))

(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

(define (cbrt x)
  (cbrt-iter 1.0 x))

;; The formula in scheme.
(define (improve guess x)
  (/ 
    (+ (/ x (* guess guess)) (* 2 guess))
    3))

;; A few guesses.
(display (cbrt 8))
(newline)
(display (cbrt 27))
(newline)
(display (cbrt 60))
(newline)
2.0000049116755
3.00000054106418
3.91487458417134 ; My calculator gives 3.91486764117


'Build Your Own Lisp' Solutions: 3.11

Q: What is the continue keyword and what does it do?


A: In a while or for loop, 'continue' will skip the rest of the block and go straight to the next iteration of the loop. Here is a program that counts to twenty, using 'continue' to filter out undesirable multiples of three:

#include <stdio.h>

int main(void)
{
  int i = 0;

  while (++i <= 20) {
    if (i % 3 == 0) {
      continue;
    }
    printf("%d\n", i);
  }

  return 0;
}
1
2
4
5
7
8
10
11
13
14
16
17
19
20


'Build Your Own Lisp' Solutions: 3.10

Q: What is the break keyword and what does it do?


A: Break breaks out of a while loop or a for loop, from within the body of that loop. Here is a program that will run a loop over nine quintillion times on most computers, before the number gets too bug for 'unsigned int' and goes back to zero:

#include <stdio.h>

int main(void)
{
  unsigned int i = 0;

  while (++i) {
    printf("%d: Looping...\n", i);
  }

  return 0;
}
1: Looping...
2: Looping...
3: Looping...
4: Looping...
5: Looping...
6: Looping...
7: Looping...
8: Looping...
9: Looping...
10: Looping...
...
9223372036854775806: Looping...

Since nine quintillion is overkill for most programs, we can use a break statement to stop it at, say, three.

#include <stdio.h>

int main(void)
{
  unsigned int i = 0;

  while (++i) {
    printf("%d: Looping...\n", i);
    if (i == 3) {
      break;
    }
  }

  return 0;
}
1: Looping...
2: Looping...
3: Looping...


'Build Your Own Lisp' Solutions: 3.9

Q: What is the switch statement and how does it work?

A: A switch statement syntactic sugar for certain combinations of 'if' and 'else', which is typically used where there are very many different possible conditions.

It is wildly controversial. Some feel that it is extremely convenient and clear, others feel that it can cause unexpected bugs (and they dislike it for other reasons a bit too technical for this post). I'm part of the former group, but I sympathize with the latter.

Here is an example:

#include <stdio.h>

void c_finder(char c)
{
  switch(c) {
    case 'a':
    case 'b':
      printf("The letter is too small!\n");
      break;
    case 'c':
      printf("The letter is just right!\n");
      break;
    default:
      printf("The letter is too large!\n");
  }
}

int main(void)
{
  c_finder('a');
  c_finder('b');
  c_finder('c');
  c_finder('z');

  return 0;
}
The letter is too small!
The letter is too small!
The letter is just right!
The letter is too large!

That switch statement is equivalent to:

  if (c == 'a' || c == 'b') {
    printf("The letter is too small!\n");
  } else if (c == 'c') {
    printf("The letter is just right!\n");
  } else {
    printf("The letter is too large!\n");
  }

Notice that 'switch' only tests equality with a constant. Something like 'else if (a > b)' doesn't really have a direct equivalent.

The reason some people dislike switch is the fall-through behaviour in the example. If a case is true, switch will execute all code down to the next 'break'. If you forget to write your breaks, you can end up with unexpected bugs. I think switch can be a useful tool, and can make code more readable, but caution and discipline are heavily recommended.



SICP Solutions - 1.7

Q: The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?


A: This is best demonstrated through examples using perfect squares:

> (sqrt 1000000000000)
1000000.0
> (sqrt 10000000000000)
; Infinite loop. 
> (sqrt 0.01)
0.100325785109606
> (sqrt 0.001)
0.0412454260749911 ; Good enough for government work.
> (sqrt 0.0001)
0.0323084483304812 ; Uh oh!
> (sqrt 0.0001)
0.0323084483304812
> (sqrt 0.00001)
0.0313564901077172
> (sqrt 0.000001)
0.0312606555254453

Very big numbers run into the limitations of your implementation of Scheme and/or how your machine handles decimals, and good-enough? doesn't work for numbers less than its threshold. Now, let's try changing good-enough? as the question suggests:

(define (good-enough? guess old-guess)
  (< (abs (- guess old-guess)) (* guess 0.001)))

; It's a good thing I already read Little Schemer,
; because this book really glosses over recursion.
(define (sqrt-iter guess old-guess x)
  (if (good-enough? guess old-guess)
    guess
    (sqrt-iter (improve guess x) guess x)))

(define (sqrt x)
  (sqrt-iter 1.0 2.0 x))
> (sqrt 1000000000000)
1000000.10346124 ; Not better, but carrying on...
> (sqrt 10000000000000)
3162277.66401048
> (sqrt 100000000000000)   
10000000.000044
> (sqrt 1000000000000000)  
31622779.2799952 ; And so on. Wowie!
; Now the small numbers
> (sqrt 0.01)
0.100000000001399
> (sqrt 0.001)
0.031622782450701
> (sqrt 0.0001)
0.0100000000254907
> (sqrt 0.00001)
0.0031622776602039
> (sqrt 0.000001)
0.00100000015330166 ; And so on.

This new way is obviously better. To get some intuition as to why, you can modify the new good-enough? to print each iteration, and play around in a REPL. This post is already pretty long, so I'll leave it as an exercise to the answer-reader.

(define (good-enough? guess old-guess)
  (display (abs (- guess old-guess)))
  (newline)
  (display (* guess 0.001))
  (newline)
  (newline)
  (< (abs (- guess old-guess)) (* guess 0.001)))


'Build Your Own Lisp' Solutions: 3.8

Q: What is the do loop, and how does it work?

A: A do loop is like a while loop, except that it checks the while condition after the block. In practice, this means that the block will always execute at least once. For example:


#include <stdio.h>

int main(void)
{
  int n = 1;

  while (n != 1) {
    printf("This will not be printed.\n");
  }

  do {
    printf("This will be printed.\n");
  } while(n != 1);

  return 0;
}
This will be printed.


'Build Your Own Lisp' Solutions: 3.7

Q: What other mathematical operators are there other than add +, and subtract -?

A: "n += 3" is equivalent to "n = n + 3". For example:


#include <stdio.h>

int main(void)
{
  int a, b;
  a = b = 0;

  a = a + 3;
  b += 3;

  printf("%d\n", a);
  printf("%d\n", b);

  return 0;
}
3
3


'Build Your Own Lisp' Solutions: 3.6

Q: What other mathematical operators are there other than add +, and subtract -?


A: