Skip to content

Instantly share code, notes, and snippets.

@grondilu
Created November 29, 2015 03:53
Show Gist options
  • Save grondilu/ba900191b018daf5cded to your computer and use it in GitHub Desktop.
Save grondilu/ba900191b018daf5cded to your computer and use it in GitHub Desktop.
trying to implement exponentiation by squaring efficiently on perl 6
# https://en.wikipedia.org/wiki/Exponentiation_by_squaring
sub exp-by-squaring-iterative(Numeric $x is copy, int $n is copy) {
return 1 if $n == 0;
if $n < 0 {
$x = 1 / $x;
$n = -$n;
}
my $y = 1;
while $n > 1 {
$y = $y * $x if $n +& 1;
$x = $x * $x;
$n = $n +> 1;
}
return $x * $y
}
my ($x, $n) = (2..10).pick, 1001;
my $now = now;
say (exp-by-squaring-iterative($x, $n) xx 10_000).pick;
say now - $now;
$now = now;
say ($x ** $n xx 10_000).pick;
say now - $now;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment