<?php

//Szybka rekurencja modularna
//Marek Rynarzewski
//www.algorytm.org

	echo("test_mulmat: ".(test_mulmat()?"true":"false").'<br/>');
	
	//Oblicz pietnascie pierwszych wartosci ciagu Fibonacciego
	for($i = 0; $i != 15; $i++)
	{
		$a = fibonaccilog($i);
		echo 'Obliczy�em '.$i.'. ty wyraz w '.round($end - $start, 10000).' sekund.<br/>';
		echo $a.'<br/>';
	}

	//Testuje mnozenie macierzy
	function test_mulmat()
	{
		$a = array(
			array(1, 1),
			array(1, 0)
		);
		$b = array(
			array(1, 1),
			array(1, 0)
		);
		$c = mulmat($a, $b);
		$result = true;
		if ($c[0][0] != 2) $result = false;
		if ($c[0][1] != 1) $result = false;
		if ($c[1][0] != 1) $result = false;
		if ($c[1][1] != 1) $result = false;
		//table($a); table($b); table($c);
		return $result;
	}

	//Mnozenie macierzy a * b
	function mulmat(array $a, array $b)
	{
		$c = array();
		for ($i=0;$i <= count($a)-1; $i ++)
		{
			//echo("i = $i;");
			for ($j=0;$j <= count($b[0])-1; $j ++)
			{
				//echo("j = $j;");
				$suma = 0;
				for ($k = 0; $k <= count($b)-1; $k ++)
				{
					$suma += $a[$i][$k] * $b[$k][$j];
				}
				$c[$i][$j] = $suma;
			}
		}
		return $c;
	}
	
	//Podnosi macierz a do potegi n
	function powmat($a, $n)
	{
		echo('run powmat with<br/>a =('.table($a).', '.$n.')<br/>');
		if ($n == 0)
			return unimat(count($a));
		if ($n == 1)
			return $a;
		if ($n % 2 != 0)
			return mulmat($a, powmat($a, $n - 1));
		else
		{
			$a = powmat($a, floor($n/2));
			return mulmat($a, $a);
		}
	}

	//Tworzy macierz jednostkowa o rozmiarze n
	function unimat($n)
	{
		$c = array();
		for ($i = 0; $i < $n; $i ++)
		{
			for ($j = 0; $j < $n; $j ++)
			{
				if ($i == $j)
				{
					$c[$i][$j] = 1;
				}
				else
				{
					$c[$i][$j] = 0;
				}
			}
		}
		return $c;
	}
	
	//Oblicza n-ty wyraz ciagu Fibonacciego uzywajac szybkiej rekurencji modularnej
	function fibonaccilog($n)
	{
		global $start, $end;
		$start = microtime();
		$a = array(
			array(1, 1),
			array(1, 0)
		);
		$a = powmat($a, $n);
		$end = microtime();
		return $a[0][0];
	}
	
	//Wypisuje wartosc macierzy c w tabeli
	function table($c)
	{
		$result = '<br/><table border="1">';
		foreach($c as $row)
		{
			$result .= '<tr>';
			foreach($row as $cell)
			{
				$result .= '<td>'.$cell.'</td>';
			}
			$result .= '</tr>';
		}
		$result .= '</table><br/>';
		return $result;
	}