this question located in sicp(exercise 1.26) says without definition of "square",it runs slower. aims checking whether number prime. quicker version:
without definition of "square",use
(* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
it said o(n)
you need evaluate (expmod base (/ exp 2) m)
twice if don't use square
. if bind result let
, pass square
, it'd same complexity.
Comments
Post a Comment