問題1.25

結果の同一性に関しては正しいが、計算の効率で劣る。

例えば、2¹⁰⁰を3で割った剰余を計算する場合、Alyssaのexpmodでは、

> (expmod-alyssa 2 100 3)
0> Calling (REMAINDER 1267650600228229401496703205376 3) 
<0 REMAINDER returned 1
1
> (time (iter (for i below 10000000) (expmod-alyssa 2 100 3)))
(ITER (FOR I BELOW 10000000) (EXPMOD-ALYSSA 2 100 3)) took 11,578 milliseconds (11.578 seconds) to run 
                    with 2 available CPU cores.
During that period, 11,406 milliseconds (11.406 seconds) were spent in user mode
                    78 milliseconds (0.078 seconds) were spent in system mode
860 milliseconds (0.860 seconds) was spent in GC.
 800,000,032 bytes of memory allocated.
NIL

となり、remainderで2¹⁰⁰ = 1267650600228229401496703205376に対する計算をしなければならない。対して、本来のexpmodでは、

> (expmod 2 100 3)
0> Calling (REMAINDER 2 3) 
<0 REMAINDER returned 2
0> Calling (REMAINDER 4 3) 
<0 REMAINDER returned 1
0> Calling (REMAINDER 2 3) 
<0 REMAINDER returned 2
0> Calling (REMAINDER 4 3) 
<0 REMAINDER returned 1
0> Calling (REMAINDER 1 3) 
<0 REMAINDER returned 1
0> Calling (REMAINDER 1 3) 
<0 REMAINDER returned 1
0> Calling (REMAINDER 2 3) 
<0 REMAINDER returned 2
0> Calling (REMAINDER 4 3) 
<0 REMAINDER returned 1
0> Calling (REMAINDER 1 3) 
<0 REMAINDER returned 1
1
> (time (iter (for i below 10000000) (expmod 2 100 3)))
(ITER (FOR I BELOW 10000000) (EXPMOD 2 100 3)) took 10,000 milliseconds (10.000 seconds) to run 
                    with 2 available CPU cores.
During that period, 10,000 milliseconds (10.000 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 32 bytes of memory allocated.
NIL

といったように、最大でも4に対する計算で済む。実（被除数）に対するremainderのステップ数の増加の程度が大きいほど、Alyssaのexpmodは速度において大きな問題を抱えることになる。また、一般的に計算機では大きい数の計算は遅いため、その意味でも不利になる。

例外として、法が極端に大きい場合、大きな数の計算の遅さから、Alyssaのexpmodの方が効率が良くなる場合がある。

> (time (iter (for i below 10000000) (expmod 2 2 (expt 2 100))))
(ITER (FOR I BELOW 10000000) (EXPMOD 2 2 (EXPT 2 100))) took 1,781 milliseconds (1.781 seconds) to run 
                    with 2 available CPU cores.
During that period, 1,781 milliseconds (1.781 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 32 bytes of memory allocated.
NIL
> (time (iter (for i below 10000000) (expmod-alyssa 2 2 (expt 2 100))))
(ITER (FOR I BELOW 10000000) (EXPMOD-ALYSSA 2 2 (EXPT 2 100))) took 1,297 milliseconds (1.297 seconds) to run 
                    with 2 available CPU cores.
During that period, 1,297 milliseconds (1.297 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 32 bytes of memory allocated.
NIL