Exponentiation by Squaring (Iterative)¶

This is an iterative version of the “Exponentiation by Squaring” algorithm. For a good explanation of that, refer to the simpler recursive page: Exponentiation by Squaring (Recursive).

“Iterative” methods of “Recursive” methods just mean that instead of calling the function itself again (“powers(num, pow)” in this case), everything is handled in one function call, and typically this means putting in a loop where there would normally be a recursive call.

Here, instead of calling “powers()” again, a loop is made with an exit condition of either the power being negative (in which case this function wouldn’t work anyways), or the power being one, in which case our function is finished and we can break the loop.

Note

Making a function “Iterative” instead of “Recursive” has the advantage of not exceeding “recursive depth”, a limit which would cause a crash in most languages. For example, in python, the limit for recursive depth is set around 1000 calls. This means that any function that calls itself, then that function calls itself, then that one … and does that more than 1000 times will crash, regardless of how much memory or processing resources are used. “Iterative” solutions avoid this entirely, which is why they are typically preferred.

#include <iostream>
using namespace std;

long long powers(long long num, long long pow){
  long result = 1;
  if(pow < 0){
    num = 1 / num;
    pow = -pow;
  }
  while (pow > 0){
    cout << num << " , " << pow << endl;
    if(pow == 1){
      break;
    }else if(pow % 2 == 0){
      num = num * num;
      pow = pow / 2;
    }else{
      result = result * num;
      num = num * num;
      pow = (pow - 1) / 2;
    }
  }
  return result * num;
}

int main(){
  cout << powers(4, 25) << endl;
  return 0;
}

class Program {
  static long powers(long num, long pow){
    long result = 1;
    if(pow < 0){
      num = 1 / num;
      pow = -pow;
    }
    while (pow > 0){
      System.Console.WriteLine(num + " , " + pow);
      if(pow == 1){
        break;
      }else if(pow % 2 == 0){
        num = num * num;
        pow = pow / 2;
      }else{
        result = result * num;
        num = num * num;
        pow = (pow - 1) / 2;
      }
    }
    return result * num;
  }

  static void Main(string[] args){
    System.Console.WriteLine(powers(4, 25));
  }
}

public class powersIterative {
  public static long powers(long num, long pow){
    long result = 1;
    if(pow < 0){
      num = 1 / num;
      pow = -pow;
    }
    while (pow > 0){
      System.out.println(num + " , " + pow);
      if(pow == 1){
        break;
      }else if(pow % 2 == 0){
        num = num * num;
        pow = pow / 2;
      }else{
        result = result * num;
        num = num * num;
        pow = (pow - 1) / 2;
      }
    }
    return result * num;
  }
  public static void main(String[] args) {
    System.out.println(powers(4, 25));
  }
}

function powers(num, pow) {
  result = 1;
  if(pow < 0){
    num = 1 / num;
    pow = -pow;
  }
  while (pow > 0){
    console.log(num + " , " + pow);
    if(pow === 1){
      break;
    }else if(pow % 2 === 0){
      num = num * num;
      pow = pow / 2;
    }else{
      result = result * num;
      num = num * num;
      pow = (pow - 1) / 2;
    }
  }
  return result * num;
}
console.log(powers(4, 25));

def power(num, pow):
  result = 1
  if pow < 0:
    num = 1 / num
    pow = -pow
  while pow > 0:
    print(num, pow)
    if(pow == 1):
      break
    elif pow % 2 == 0:
      num = num * num
      pow = pow / 2
    else:
      result = result * num
      num = num * num
      pow = (pow - 1) / 2
  return result * num
print(power(4,25))

func powers(_ num: Int,_ pow: Int) -> Int {
  var result = 1;
  var num = num
  var pow = pow
  if(pow < 0){
    num = 1 / num
    pow = -pow
  }
  while (pow > 0){
    print(num, pow)
    if(pow == 1){
      break
    }else if(pow % 2 == 0){
      num = num * num
      pow = pow / 2
    }else{
      result = result * num
      num = num * num
      pow = (pow - 1) / 2
    }
  }
  return result * num
}
print(powers(4, 25))

Notes¶

long long here is a number type, just like int, but it can store larger numbers. The expression pow % 2 == 0 means there is no remainder when divided by two repeatedly, or the number is even.

The only case left, of course, is that the number is odd, since the cases negative, zero, one, and even are accounted for.

In C#, the long type is like the C++ long long type, a 64 bit (or larger) integer.

long here is a 64 bit (or larger) integer, nothing else here of note.

Because javascript is loosely typed (no types such as int are specified), be careful not to pass in a decimal number because this relies on equality comparisons, which is very not recommended for floating-point types. To quote Wikipedia,

“The use of the equality test (if (x==y) …) requires care when dealing with floating-point numbers. Even simple expressions like 0.6/0.2-3==0 will, on most computers, fail to be true (in IEEE 754 double precision, for example, 0.6/0.2-3 is approximately equal to -4.44089209850063e-16). Consequently, such tests are sometimes replaced with “fuzzy” comparisons (if (abs(x-y) < epsilon) …, where epsilon is sufficiently small and tailored to the application, such as 1.0E−13).”

In python, elif is used instead of the typical else if, because python would have you indent twice with that, and it would take another line.

The underscore beside the parameter names make them unrequired when calling the function instead of the default required with swift.

(powers(4,25) can be called instead of powers(num: 4, pow:25) which is standard in swift).