1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    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:
    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