a の k乗 を m で割った余りを求める関数 powmod(a, k, m) をPHPで実装

gistfile1.php

<?php
// 愚直なパターン
function powmod($a, $k, $m)
{
	$t = 1;
	foreach (range(1, $k) as $r) {
		$t = $t * $a;
	}	
	return $t % $m;
}

gistfile2.php

<?php
// 愚直なパターン
function powmod($a, $k, $m)
{
	return _pow($a, $k) % $m;
}

function _pow($a, $k)
{
	if ($k === 0) return 1;
	return $a * _pow($a, $k -1);
}

gistfile3.php

<?php
// オーバーフローを考慮
// O(N)
function powmod($a, $k, $m)
{
	$t = 1;
	foreach (range(1, $k) as $r) {
		$t = ($t * $a) % $m;
	}	
	return $t;
}

gistfile4.php

<?php
// ループ回数を削減
// O(logN)
function powmod($a, $k, $m)
{
	if ((int)$k === 0) return 1;
	$t = powmod($a, $k / 2, $m);
	$t = ($t * $t) % $m;
	if ($k % 2 === 1) $t = ($t * $a) % $m;
	return $t;
}

gistfile5.php

<?php
// ループ回数を削減
// k = 3t のとき、 n^k = n^t * n^t * n^t
function powmod($a, $k, $m)
{
	if ((int)$k === 0) return 1;
	$t = powmod($a, $k / 3, $m);
	$t = (($t * $t) % $m * $t) % $m;
	switch ($k % 3) {
		case 1:
			$t = $t * $a % $m;
			break;
		case 2:
			$t = ($t * $a % $m) * $a % $m;
			break;
		default:
			break;
	}
	return $t;
}