Skip to content

Instantly share code, notes, and snippets.

@edadma
Created April 4, 2020 03:58
Show Gist options
  • Save edadma/a08cf3857b5094dd9ae1dfe9f49300f5 to your computer and use it in GitHub Desktop.
Save edadma/a08cf3857b5094dd9ae1dfe9f49300f5 to your computer and use it in GitHub Desktop.
Tail recursive exponentiation by squaring
def pow(x: Int, n: Int) = {
def pow(y: Int, x: Int, n: Int): Int =
n match {
case 0 => 1
case 1 => x * y
case _ if n % 2 == 0 => pow(y, x * x, n / 2)
case _ => pow(x * y, x * x, (n - 1) / 2)
}
if (n < 0) sys.error(s"pow: negative exponent: $n") else pow(1, x, n)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment