P38: Euler's totient function phi(m)の改善効果

L-99 Common Lisp

ACLで動作確認。
P34の実装はconsしまくっている模様。

CL-USER> (time (totient-phi 65535))
; cpu time (non-gc) 540 msec user, 10 msec system
; cpu time (gc)     130 msec user, 0 msec system
; cpu time (total)  670 msec user, 10 msec system
; real time  679 msec
; space allocation:
;  2,785,258 cons cells, 84,413,592 other bytes, 0 static bytes
32768
CL-USER> (time (totient-phi-v2 65535))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  0 msec
; space allocation:
;  1,679 cons cells, 20,896 other bytes, 0 static bytes
32768
CL-USER>

SBCLでも効果はある様子。

CL-USER> (time (totient-phi 65535))
Evaluation took:
  0.014 seconds of real time
  0.013733 seconds of user run time
  5.1e-5 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
32768
CL-USER> (time (totient-phi-v2 65535))
Evaluation took:
  0.0 seconds of real time
  9.e-6 seconds of user run time
  1.e-6 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
32768
CL-USER>