I'm doing exercise 1.18 in SICP and I face some trouble. The goal is to make a procedure based on 2 previous exercises. This procedure implements so-called Russian peasant method (or Ancient Egyptian multiplication). I wrote a code, but one procedure just doesn't want to execute. Here's my code:
#lang sicp
(define (double a) (+ a a))
(define (halve a) (/ a 2))
(define (r_m a b)
(iter a b 0))
(define (iter a b n)
(cond ((= b 0) 0)
((even? a) (iter (halve a) (double b) (+ n b)))
(else (iter (halve a) (double b) n))))
So, when I call my procedure (r_m) with such arguments (r_m 13 19) it stops after 1st iteration.
(iter (halve a) (double b) (+ n b) (with arguments 13 and 19) gives this result: iter (13/2) 38 19
After that, program tries to check if 13/2 is odd. But it can't check such number (13/2), because odd? expects an integer, not this undone division.
For some reason, the halve procedure doesn't work when called. I don't really understand why, because other procedures (double and simple + n b) work fine.
Thank you in advance and I hope my grammar doesn't hurt you too much.
There are several things wrong with your program. Apart from anything else, even if halve worked the way you want it to work, how would b become zero? This is not the only problem!
However the particular case of halve happens because you are assuming programming languages to do what they normally do: incorrect arithmetic which is convenient for the machine, rather than correct arithmetic which is convenient for humans. Scheme tries hard to do correct arithmetic. What, mathematically, is 13/2? It's not 6, or 7, or 3, it's 13/2, or 6 + 1/2: it's a rational number, not an integer.
If you want the next integer below 13/2, the way you want to get it is by subtracting 1 before you divide: (halve (- 13 1)) is 6, exactly. So if you change that cond clause to have (halve (- a 1)) your program will be closer to working (but, in fact it will then fail to terminate, so in a sense it will be further from working...).