SICP Exercise 1.22

A procedure that checks a prime number.

(define (prime? n)
  (= n (smallest-divisor n)))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (square n)
  (* n n))

A procedure that measures the time for "prime?".
I rewrite a bit.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))
      #f))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time)
  #t)

DrScheme doesn't have "runtime".

(define (runtime)
  (current-milliseconds))

My answer.

(define (search-for-primes min max cnt)
  (cond ((> min max))
        ((= cnt 3))
        ((even? min) (search-for-primes (+ min 1) max cnt))
        (else
         (if (timed-prime-test min)
             (search-for-primes (+ min 2) max (+ cnt 1))
             (search-for-primes (+ min 2) max cnt)))))

(search-for-primes 1000 9999 0)
(search-for-primes 10000 99999 0)
(search-for-primes 100000 999999 0)
(search-for-primes 1000000 9999999 0)

It's impossible to measure the time.

SICP Exercise 1.21

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (square n)
  (* n n))

(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)

199
1999
7

SICP Exercise 1.17 - 1.18

A multiplication procedure.

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

Exercise 1.17.
Rewrite to a code that uses a logarithmic number of steps.
(Use "double" and "halve".)

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* a (- b 1))))))

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))

Exercise 1.18.
Rewrite to a code that generates an iterative process.

(define (* a b)
  (*-iter a b 0))

(define (*-iter a b n)
  (cond ((= b 0) n)
        ((even? b) (*-iter a (halve b) (double n)))
        (else (*-iter a (- b 1) (+ n a)))))

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))

There will be an answer.

Japanese Programmer's: From recursion to iteration.

I found an answer.

(define (fast-expt2 b n)
  (fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter a (square b) (/ n 2)))
        (else (fast-expt-iter (* a b) b (- n 1)))))

From recursion to iteration.

Exercise 1.16 of 1.2.4 Exponentation in SICP.

Recursion.

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (even? n)
  (= (remainder n 2) 0))

(define (square n)
  (* n n))

How do I rewrite this code to iterative process?

SICP Exercise 1.10.

Ackermann's function

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536

SICP Exercise 1.9.

A.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

B.

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

A.

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5))))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

This is a recursive process.

B.

(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
9

This is a iterative process.

Linear Recursion and Iteration Sample.

A linear recursion code.

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

A linear iteration code.

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Lazy Evaluation of Haskell.

From Exercise 1.5 of SICP.

What the result is this Scheme code.

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

(test 0 (p))

It's an infinite loop.

The case of Haskell.

p = p

test x y = case x of
  0 -> 0
  _ -> y

test 0 p

The result is zero.
This is Lazy Evaluation of Haskell.

Square Roots by Newton's Method.

Square Roots by Newton's Method.

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

"x" is a free variable in the internal definitions.It gets its value from the argument with which the enclosing procedure sqrt is called.This dicipline is called "lexical scoping".

(SICP) 1 Building Abstractions with Procedures

I'm trying to read "Structure and Interpretation of Computer Programs" (SICP).
Today, I read "1 Building Abstractions with Procedures".
It's be summarized as follows.

Programming in Lisp is great fun.

Foreword of SICP.

I'm trying to read "Structure and Interpretation of Computer Programs" (SICP).
Today, I read "Foreword".
It's described about programming, Lisp and so on.

The SICP Web Site.

We can read "Structure and Interpretation of Computer Programs" (SICP) on web.

Welcome to the SICP Web Site

I'll try to read it.
But I'm not good at English...