SICP по-русски

Идея Алисы проста и понятна. Более того, ее вариант процедуры (expmod) выдает те же результаты, что и исходный. Но в нем есть проблема, имя которой - эффективность.

Количество операций, производимых при вычислении по обеим процедурам, будет примерно одинаковым (иметь один порядок роста) только в том случае, если элементарные функции, такие как * и remainder, выполняются за время, не зависящее от значений своих аргументов. Но это не так, ведь это операции над числами произвольного размера, поддержка таких операций отсутствует на уровне процессора/сопроцессора. Следовательно каждая подобная операция не элементарна, а влечет выполнение некоторой процедуры, время работы которой увеличивается с ростом чисел, над которыми выполняется операция.

В варианте реализации (expmod), предложенном в тексте главы, все числа, с которыми идет работа, поддерживаются сравнительно небольшими на протяжении всего процесса вычислений. В варианте Алисы числа растут от шага к шагу при возведении в степень. Поэтому предложение Алисы неплохо для прототипа, но не годится в серьезном деле, где требуется не только правильный результат, но и эффективность (а в работе с простыми числами она, как правило, требуется).