Exercise1-24 <---> Exercise1-26

Exercise 1.25

Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

Ru: Лиза П. Хакер жалуется, что при написании expmod мы делаем много лишней работы. В конце концов, говорит она, раз мы уже знаем, как вычислять степени, можно просто написать

  (define (expmod base exp m)
    (remainder (fast-expt base exp) m))

Права ли она? Стала бы эта процедура столь же хорошо работать при проверке простых чисел? Объясните.

Solution:

Obviously, she is not correct. Using fast-expt here is mathematically equivalent and its time growth rate is logarithmic as well. However, arithmetic with exponentially growing numbers makes it greatly slower.

In the worst case the base argument equals n, so we have to calculate nⁿ. The number of digits in the binary representation of nⁿ is log (nⁿ) = n * log (n). The growth rate of multiplication with long arithmetic is O(p²), where p is the count of bits in a number. The growth rate of multiplications in the fast-expt is O(log (n)), therefore, total growth rate of fast-expt with long arithmetic is O(n² * log³(n)).

For the algorithm without fast-expt the multipliers on each step are bounded with n², because of the constant modulus reduction. Therefore, total growth rate is only O(log³(n)).

Exercise1-24 <---> Exercise1-26

Comments

Проверяйте, кто нибудь, мои решения, плиз! Я тут в роли ученика и часто жестоко ошибаюсь.

Posted by DmitryTiagulskyi at 2007-09-22 12:05:37

Агащаз! :о) Мы сами ещё не волшебники, а тока учимся... ;о) Вся надежда, что придёт кто-то очень умный и всех нас научит! )))

Posted by Geniepro at 2007-09-22 14:39:24

Ага, может Сассман придёт

Posted by IvanVeselov at 2007-09-22 20:41:06

Add your comment Markup