Iterative Function To Find X to the power N

Discussion in 'Perl' started by pradeep, Mar 14, 2008.

  1. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    In rashida.par's Recursive function to find X to the power n (http://www.go4expert.com/showthread.php?t=9307) I see that she intelligently used recursion to find the power of x to n. So, I was wondering whether we can do this iteratively also, I always do that - trying to find a iterative solution to a recursive one.

    Being more of a Perl programmer than C, I wrote my code in Perl - can be understood by any programmer. I also benchmarked the recursive function to the iterative version.

    The Iterative Solution



    Code:
     sub power_iterative
     {
         my ($x,$n) = @_; ## take in parameters
         my $result = 1;
     
         while($n--)
         {
             $result *= $x;
         }
     
         return $result;
     }
     
    Test run of the code:
    Code:
     printf("\n %.4f to the power of % d is %.4f",$x,$n,power_iterative($x,$n));
     
    Code:
     [pradeep@go4expert perl_test]$ perl power_iterative.pl
     
      4.0000 to the power of  10 is 1048576.0000
     

    Benchmarking



    I also benchmarked the recursive function to the iterative version to see which one performs better.

    Code:
     use Benchmark;
     
     sub power_iterative
     {
         my ($x,$n) = @_; ## take in parameters
         my $result = 1;
     
         while($n--)
         {
             $result *= $x;
         }
     
         return $result;
     }
     
     sub power_recursive
     {     
         my ($x,$n) = @_; ## take in parameters
         
         if ($x==0)     
         {         
             return 0;     
         }     
         elsif($n==0)     
         {         
             return 1;     
         }     
         elsif ($n>0)     
         {         
             return( $x* power_recursive($x,$n-1));     
         }     
         else     
         {         
             return ((1/$x)*power_recursive($x,$n+1));     
         } 
     }
     
     my ($x,$n) = (4,10);
     
     timethese(400000,{
     'iterative'=> sub{my $power = power_iterative($x,$n);},
     'recursive'=> sub{my $power = power_recursive($x,$n);}});
     
    Result:
    Code:
     [pradeep@go4expert perl_test]$ perl power_iterative.pl
     Benchmark: timing 400000 iterations of iterative, recursive...
      iterative:  2 wallclock secs ( 1.28 usr +  0.00 sys =  1.28 CPU) @ 312500.00/s (n=400000)
      recursive:  6 wallclock secs ( 5.90 usr +  0.00 sys =  5.90 CPU) @ 67796.61/s (n=400000)
     
    As we see here, the iterative version performs much better than the recursive one, the reason being the recursive version need more memory for function call stacks etc.

    I hope this was helpful to you all.
     
  2. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    As was evident from the Recursive implementation, there was tail recursion, which is both redundant & inefficient. Tail recursion must always be replaced with a more efficient, easier to comprehend iterative counter-part, as you have done here.

    Only, you have done it in Perl - a language which I do not know much about - so I got to learn the basics of a new language as well!

    Regards,
    Rajiv
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice