scheme - Without definition of "square" why this function slower? -


this question located in sicp(exercise 1.26) says without definition of "square",it runs slower. aims checking whether number prime. quicker version:

scheme,prime check,o(log n)

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