Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Clojure

Idiom #32 Integer exponentiation by squaring

Create function exp which calculates (fast) the value x power n.
x and n are non-negative integers.

(defn exp [x n]
  (let [x-squared (* x x)]
    (cond
      (= n 0) 1
      (= n 1) x
      (= (mod n 2) 0) (exp x-squared (/ n 2))
      :else (* x (exp x-squared (/ (- n 1) 2))))))
unsigned int exp(unsigned int x,unsigned int n)
{
    if(n==0)
    {
        return 1;
    }
    if(n==1)
    {
        return x;
    }
    if(!(n%2))
    {
        return exp(x*x,n/2);
    }
    return x*exp(x*x,(n-1)/2);
}

New implementation...