Exercise1-23 <---> Exercise1-25

Exercise 1.24

Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

Ru: Модифицируйте процедуру timed-prime-test из упражнения 1.22 так, чтобы она использовала fast-prime? (метод Ферма) и проверьте каждое из 12 простых чисел, найденных в этом упражнении. Исходя из того, что у теста Ферма порядок роста , то какого соотношения времени Вы бы ожидали между проверкой на простоту поблизости от 1 000 000 и поблизости от 1000? Подтверждают ли это Ваши данные? Можете ли Вы объяснить наблюдаемое несоответствие, если оно есть?

Scheme solution:

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

(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) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (prime? n)
  (fast-prime? n 20000))

(define (timed-prime-test n)
  (newline)
  (display n)  
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))
  
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

Here are test results of the program listed above. I've set the number of tries for fast-prime? to 20,000 to create a mesurable running time delay on my PC. Tests have been executed once for each n. The results are as follows:

n₀ = 31; t₀ = 250ms
n₁ = 1013; t₁ = 484ms

Since , I would expect the time to test primes near 1,000,000 to be twice longer than time needed to test primes near 1000. However, the test shows:

n₂ = 1000003; t₂ = 2046ms ~ 2 * (2 * t₁)

So, when n grows, the execution time overruns my first expectation.

In fact, - the big omega notation - describes running time growth rate only, but not the exact number of operations in the algorithm. In the worst case in the expmod iterations even exp values will alternate with odd ones, so the actual number of steps will be closer to (which correlates with test results for n₁ and n₂). Also we should consider additional overhead on oddness checks, recursion and so on.

Exercise1-23 <---> Exercise1-25

Comments

Add your comment Markup