🚀 go-pugleaf

In article <1992Apr06.025126.33552@slate.mines.colorado.edu>, jgore@Mines.Colorado.Edu (Jacob Gore) writes:
> Consider the following function for computing x to the power of n:
> 
> fun power(x,n) =
>   if n=0 then 1.0
>   else if n mod 2 = 1 then x * power(x,n-1)
>   else power(x*x, n div 2);
> 
> What is the likelihood of an SML implementation doing it in O(1) space?
> 
> Jacob
> --
> Jacob Gore			Mathematical and Computer Sciences
> <JGore@Mines.Colorado.Edu>	Colorado School of Mines
> 
> 	-- Member of the League for Programming Freedom --

If you transform this into a tail-recursive form, i.e.

        fun power(x,n) =
          auxpower(x,n,1.0);

        fun auxpower(x,n,res) =
          if n=0 then res
          else if n mod 2 = 1 then power(x,n-1,res*x)
          else power(x*x, n div 2,res);

then a good compiler should recognize that it is a tail-recursion, and
convert it into an iterative form, which would need constant space.

-- Marc Najork

>>>>> 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