#!/usr/bin/php
<?php

define('MAX_POWER', 10);
define('MAX_DISTANCE', 99);
ini_set('memory_limit', '2G');

# ---

function bcabs($x) {
	return str_replace('-', '', $x);
}

function bcadd2($a,$b) {
	return gmp_add($a,$b);
}

function bcsub2($a,$b) {
	return gmp_sub($a,$b);
}

function bcmul2($a,$b) {
	return gmp_mul($a,$b);
}

function biquad_mul($a, $b) {

	/*
	According to multiplication table at
	https://www.naturalspublishing.com/files/published/e71f3zs34zg62q.pdf
	https://en.wikipedia.org/wiki/Biquaternion
	*/

	# $c0 = $a[0]*$b[0] - $a[1]*$b[1] - $a[2]*$b[2] - $a[3]*$b[3] - $a[4]*$b[4] + $a[5]*$b[5] + $a[6]*$b[6] + $a[7]*$b[7];
	# $c1 = $a[0]*$b[1] + $a[1]*$b[0] + $a[2]*$b[3] - $a[3]*$b[2] - $a[4]*$b[5] - $a[5]*$b[4] - $a[6]*$b[7] + $a[7]*$b[6];
	# $c2 = $a[0]*$b[2] - $a[1]*$b[3] + $a[2]*$b[0] + $a[3]*$b[1] - $a[4]*$b[6] + $a[5]*$b[7] - $a[6]*$b[4] - $a[7]*$b[5];
	# $c3 = $a[0]*$b[3] + $a[1]*$b[2] - $a[2]*$b[1] + $a[3]*$b[0] - $a[4]*$b[7] - $a[5]*$b[6] + $a[6]*$b[5] - $a[7]*$b[4];
	# $c4 = $a[0]*$b[4] - $a[1]*$b[5] - $a[2]*$b[6] - $a[3]*$b[7] + $a[4]*$b[0] - $a[5]*$b[1] - $a[6]*$b[2] - $a[7]*$b[3];
	# $c5 = $a[0]*$b[5] + $a[1]*$b[4] + $a[2]*$b[7] - $a[3]*$b[6] + $a[4]*$b[1] + $a[5]*$b[0] + $a[6]*$b[3] - $a[7]*$b[2];
	# $c6 = $a[0]*$b[6] - $a[1]*$b[7] + $a[2]*$b[4] + $a[3]*$b[5] + $a[4]*$b[2] - $a[5]*$b[3] + $a[6]*$b[0] + $a[7]*$b[1];
	# $c7 = $a[0]*$b[7] + $a[1]*$b[6] - $a[2]*$b[5] + $a[3]*$b[4] + $a[4]*$b[3] + $a[5]*$b[2] - $a[6]*$b[1] + $a[7]*$b[0];

	$c0 = bcadd2(bcadd2(bcadd2(bcsub2(bcsub2(bcsub2(bcsub2(bcmul2($a[0],$b[0]),bcmul2($a[1],$b[1])),bcmul2($a[2],$b[2])),bcmul2($a[3],$b[3])),bcmul2($a[4],$b[4])),bcmul2($a[5],$b[5])),bcmul2($a[6],$b[6])),bcmul2($a[7],$b[7]));
	$c1 = bcadd2(bcsub2(bcsub2(bcsub2(bcsub2(bcadd2(bcadd2(bcmul2($a[0],$b[1]),bcmul2($a[1],$b[0])),bcmul2($a[2],$b[3])),bcmul2($a[3],$b[2])),bcmul2($a[4],$b[5])),bcmul2($a[5],$b[4])),bcmul2($a[6],$b[7])),bcmul2($a[7],$b[6]));
	$c2 = bcsub2(bcsub2(bcadd2(bcsub2(bcadd2(bcadd2(bcsub2(bcmul2($a[0],$b[2]),bcmul2($a[1],$b[3])),bcmul2($a[2],$b[0])),bcmul2($a[3],$b[1])),bcmul2($a[4],$b[6])),bcmul2($a[5],$b[7])),bcmul2($a[6],$b[4])),bcmul2($a[7],$b[5]));
	$c3 = bcsub2(bcadd2(bcsub2(bcsub2(bcadd2(bcsub2(bcadd2(bcmul2($a[0],$b[3]),bcmul2($a[1],$b[2])),bcmul2($a[2],$b[1])),bcmul2($a[3],$b[0])),bcmul2($a[4],$b[7])),bcmul2($a[5],$b[6])),bcmul2($a[6],$b[5])),bcmul2($a[7],$b[4]));
	$c4 = bcsub2(bcsub2(bcsub2(bcadd2(bcsub2(bcsub2(bcsub2(bcmul2($a[0],$b[4]),bcmul2($a[1],$b[5])),bcmul2($a[2],$b[6])),bcmul2($a[3],$b[7])),bcmul2($a[4],$b[0])),bcmul2($a[5],$b[1])),bcmul2($a[6],$b[2])),bcmul2($a[7],$b[3]));
	$c5 = bcsub2(bcadd2(bcadd2(bcadd2(bcsub2(bcadd2(bcadd2(bcmul2($a[0],$b[5]),bcmul2($a[1],$b[4])),bcmul2($a[2],$b[7])),bcmul2($a[3],$b[6])),bcmul2($a[4],$b[1])),bcmul2($a[5],$b[0])),bcmul2($a[6],$b[3])),bcmul2($a[7],$b[2]));
	$c6 = bcadd2(bcadd2(bcsub2(bcadd2(bcadd2(bcadd2(bcsub2(bcmul2($a[0],$b[6]),bcmul2($a[1],$b[7])),bcmul2($a[2],$b[4])),bcmul2($a[3],$b[5])),bcmul2($a[4],$b[2])),bcmul2($a[5],$b[3])),bcmul2($a[6],$b[0])),bcmul2($a[7],$b[1]));
	$c7 = bcadd2(bcsub2(bcadd2(bcadd2(bcadd2(bcsub2(bcadd2(bcmul2($a[0],$b[7]),bcmul2($a[1],$b[6])),bcmul2($a[2],$b[5])),bcmul2($a[3],$b[4])),bcmul2($a[4],$b[3])),bcmul2($a[5],$b[2])),bcmul2($a[6],$b[1])),bcmul2($a[7],$b[0]));

	return [$c0, $c1, $c2, $c3, $c4, $c5, $c6, $c7];
}

function biquad_int_power($biquad, $n) {
	assert($n >= 1);
	$res = $biquad;
	for ($p=2; $p<=$n; $p++) $res = biquad_mul($res, $biquad);
	return $res;
}

function biquad_is_immortal($biquad, $power) {
	$biquadpow = biquad_int_power($biquad, $power);
	for ($i=0; $i<8; $i++) {
		$x1 = bcabs($biquad[$i]);
		$x2 = bcabs($biquadpow[$i]);
		if (substr($x2, -strlen($x1)) != $x1) return false;
	}
	return $biquadpow;
}

function _go($a, $b, $c, $d, $e, $f, $g, $h, $power, $distance, &$progr, &$found) {
	$biquad = [$a, $b, $c, $d, $e, $f, $g, $h];
	$biquadpower = biquad_is_immortal($biquad, $power);
	if ($biquadpower !== false) {
		$a_ = $biquadpower[0];
		$b_ = $biquadpower[1];
		$c_ = $biquadpower[2];
		$d_ = $biquadpower[3];
		$e_ = $biquadpower[4];
		$f_ = $biquadpower[5];
		$g_ = $biquadpower[6];
		$h_ = $biquadpower[7];
		// Since BiQuad is (1, 1h, i, ih, j, jh, k, kh):
		//       A true quaternion would be a, 0, c, 0, e, 0, g, 0
		//       A true complex would be    a, 0, c, 0, 0, 0, 0, 0
		if (($b!=0) || ($d!=0) || ($f!=0) || ($h!=0)) {
			$str = "BIQU ";
		} else if (($e!=0) || ($g!=0)) {
			$str = "QUAD ";
		} else if ($c!=0) {
			$str = "CPLX ";
		} else {
			$str = "REAL ";
		}
		$str .= "| Distance=$distance | ";
		$str .= "[$a, $b, $c, $d, $e, $f, $g, $h] ^ $power = [$a_, $b_, $c_, $d_, $e_, $f_, $g_, $h_]";
		if (!in_array($str,$found)) {
#			echo "$str\n";
			$found[] = $str;
		}
	}
	#if ($progr++ % 10000 == 0) {
	#	echo "(Dist=$distance) Processing ($a, $b, $c, $d, $e, $f, $g, $h) with power $power                 \r";
	#}
}

if (file_exists(__DIR__.'/savestate.txt')) {
	$start_distance = trim(file_get_contents(__DIR__.'/savestate.txt'));
} else {
	$start_distance = 0;
}
for ($distance=$start_distance; $distance<=MAX_DISTANCE; $distance++) {
	$str = "--------- Distance: $distance ---------";
	echo "                                                                              \r";
	echo "$str\n";
	$found = [ $str ];
	$progr = 0;

	$a = $distance;
	for ($b=0; $b<=$distance; $b++) {
	for ($c=0; $c<=$distance; $c++) {
	for ($d=0; $d<=$distance; $d++) {
	for ($e=0; $e<=$distance; $e++) {
	for ($f=0; $f<=$distance; $f++) {
	for ($g=0; $g<=$distance; $g++) {
	for ($h=0; $h<=$distance; $h++) {
	if ($h == 0) echo "\r".round(memory_get_usage()/1024/1024, 2)." MiB (".count($found)." found); ($a), $b, $c, $d, $e, $f, $g, $h                                ";
	for ($power=2; $power<=MAX_POWER; $power++) {
	_go($a, $b, $c, $d, $e, $f, $g, $h, $power, $distance, $progr, $found);
	_go($b, $a, $c, $d, $e, $f, $g, $h, $power, $distance, $progr, $found);
	_go($b, $c, $a, $d, $e, $f, $g, $h, $power, $distance, $progr, $found);
	_go($b, $c, $d, $a, $e, $f, $g, $h, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $a, $f, $g, $h, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $a, $g, $h, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $a, $h, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $a, $power, $distance, $progr, $found);
	}
	}
	}
	}
	}
	}
	}
	}
	echo "\n";

	file_put_contents(__DIR__.'/result.txt', implode("\n",$found)."\n", FILE_APPEND);
	file_put_contents(__DIR__.'/savestate.txt', $distance+1);
}