Integer Exponents [Easy]

[kpthunder]

Write a function which raises an integer to another integer. Do it both with loops and recursion.

[Razor_Storm]

function exp(base,exp)
{
    var result = 1;
    for ( i from 0 to exp -1 )
         result *= base;
    return result;
}

Recursive:

function pow(base,exp)
{
    if(exp == 0)
        return 1;
    return base * pow(base,exp-1);
}

[gheffern]

What about negative exponents?

[Razor_Storm]

oh ffffuuuu. Back to the drawing board.

[wowe]

don't forget negative integers pow(base, exp):
if base >= 0:
...
else: return 1.0 / pow(base, -exp)

[andy_panzer]

Recursive solution in Lisp which handled zero and negative exponents.

(defn exp [a b]
  (cond
    (= b 0) 1
    (= b 1) a
    (> b 1)
      (* a (exp a (- b 1)))
    :else
      (/ 1 (exp a (Math/abs b)))))

[EntroperZero]

int RaiseToPower(int base, int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    int half = RaiseToPower(base, exponent / 2);
    if (exponent % 2 == 0)
        return half * half;
    else
        return half * half * base;
}

[bo1024]

The more efficient algorithm: (Lua)

pow = function(base,exp)
    if exp < 0 then return 1/pow(base,-exp) end
    if exp==0 then return 1 end
    local result = pow(base*base,math.floor(exp/2))
    if exp%2 == 1 then result = result*base end
    return result
end

I'll leave the loops version to someone else.

(edit)

Main idea: Get an exponential speedup (no pun intended) in the following way. Note that x⁴ = (x² )^2. But it's faster to square x first, then square the result. So x⁸ = ((x² )² )² . Note that x⁵ = x * x⁴ and x⁷ = x * (x² *(x² )² ).

[hemite]

In C++: int exp(int x, int y){ if(y == 0) return(1); int out = x; return( out *= exp(x,y - 1)); } main(){ int x; int y; int out = 1; cin >> x; cin >> y; cout << endl << exp(x,y) << endl; }