Ex-1.22, 1.23, 1.24

Ex-1.22:

;changed runtime to get-universal-time
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (get-universal-time)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (get-universal-time) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))


; its assumed that start and end are odd numbers
; start <= end
(define (search-for-primes start end)
  (if (not (= start end))
      (begin
        (timed-prime-test start)
        (search-for-primes (+ start 2) end))))

3 primes above 1000:
1009, time-taken: 0
1013, time-taken: 0
1019, time-taken: 0

3 primes above 10000:
10007, time-taken: 0
10009, time-taken: 0
10037, time-taken: 0

3 primes above 100000:
100003, time-taken: 0
100019, time-taken: 0
100043, time-taken: 0

3 primes above 1000000:
1000003, time-taken: 0
1000033, time-taken: 0
1000037, time-taken: 0 

machines now a days are quite faster, I can see the observable difference at following numbers

3 primes above 1000000000000:
1000000000039, time-taken: 4 s
1000000000061, time-taken: 4 s
1000000000063, time-taken: 4 s

3 primes above 10000000000000:
10000000000037, time-taken: 13 s
10000000000051, time-taken: 13 s
10000000000099, time-taken: 13 s

3 primes above 100000000000000:
100000000000031, time-taken: 41 s
100000000000067, time-taken: 41 s
100000000000097, time-taken: 42 s 

and indeed the (sqrt 10) factor is visible for above 3 data-sets. So, yes execution time on the machine is proportional to the number of steps required for the computation.

Ex-1.23:

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))
(define (next test-divisor)
  (if (= test-divisor 2) 3
      (+ test-divisor 2)))

3 primes above 1000000000000:
1000000000039, time-taken: 2 s
1000000000061, time-taken: 2 s
1000000000063, time-taken: 3 s

3 primes above 10000000000000:
10000000000037, time-taken: 7 s
10000000000051, time-taken: 8 s
10000000000099, time-taken: 7 s

3 primes above 100000000000000:
100000000000031, time-taken: 23 s
100000000000067, time-taken: 25 s
100000000000097, time-taken: 24 s 

If we compare these results with those in Ex-1.22, they're indeed halved(not exactly but close).

Ex-1.24-

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (get-universal-time)))
(define (start-prime-test n start-time)
  (if (fast-prime? n 10)
      (report-prime (- (get-universal-time) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

3 primes above 1000000000000:
1000000000039, time-taken: 0 s
1000000000061, time-taken: 0 s
1000000000063, time-taken: 0 s

3 primes above 10000000000000:
10000000000037, time-taken: 0 s
10000000000051, time-taken: 0 s
10000000000099, time-taken: 0 s

3 primes above 100000000000000:
100000000000031, time-taken: 0 s
100000000000067, time-taken: 0 s
100000000000097, time-taken: 0 s 

no observable time difference at these numbers using fermat's test

Conclusion: Execution time on the machine is roughly proportional to the number of steps required in doing the computation.