🚀 go-pugleaf

>>>>> On 6 Apr 92 02:51:26 GMT, jgore@Mines.Colorado.Edu (Jacob Gore) said:

Jacob> fun power(x,n) =
Jacob>   if n=0 then 1.0
Jacob>   else if n mod 2 = 1 then x * power(x,n-1)
Jacob>   else power(x*x, n div 2);

Jacob> What is the likelihood of an SML implementation doing it in O(1) space?

well, i don't know the internals of any SML implementations, but one
would assume that the answer is 0% due to the non-tail recursive call
in the second case.  you can easily rewrite the function so that most
compilers will take O(1) space: 

 fun power(x,n,r) : int =
   if n=0 then r
   else if n mod 2 = 1 then power(x,n-1,x*r)
   else power(x*x, n div 2,r);

call it with r=1
-- 
			conform
scott draves		deform
spot@cs.cmu.edu		explode