#!/usr/bin/php
<?php

define('MAX_POWER', 10);
define('MAX_DISTANCE', 9);
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_sub($a, $b) {
	for ($i=0; $i<8; $i++) $a[$i] = bcsub2($a[$i],$b[$i]);
	return $a;
}

function biquad_add($a, $b) {
	for ($i=0; $i<8; $i++) $a[$i] = bcadd2($a[$i],$b[$i]);
	return $a;
}

function biconjugation($biquad) {
	// s* = w-xi-yj-zk  where w,x,y,z are bivectors (= complex numbers with imaginary part h)

	// https://en.wikipedia.org/wiki/Biquaternion#Algebraic_properties
	// The order of $biquad is "1, 1h, i, ih, j, jh, k, kh" (h is the imaginary unit of the complex numbers w,x,y,z)
	$w = [ $biquad[0], $biquad[1]/*h*/ ];
	$x = [ $biquad[2], $biquad[3]/*h*/ ];/*i*/
	$y = [ $biquad[4], $biquad[5]/*h*/ ];/*j*/
	$z = [ $biquad[6], $biquad[7]/*h*/ ];/*k*/

	// Negate complex numbers w, x, y, z :  Component wise, i.e.  -(a+bi) = -a-bi
	return [ $w[0], $w[1], bcsub2(0,$x[0]), bcsub2(0,$x[1]), bcsub2(0,$y[0]), bcsub2(0,$y[1]), bcsub2(0,$z[0]), bcsub2(0,$z[1]) ];
}

function bioct_mul($bioct1, $bioct2) {
	$p = $bioct1[0];
	$q = $bioct1[1];
	$r = $bioct2[0];
	$s = $bioct2[1];

	// https://en.wikipedia.org/wiki/Bioctonion
	// Multiplication:
	// (p,q)(r,s) = (pr-s*q, sp+qr*)
	// p, q, r, s are biquaternions. A pair of two biquaternions form a bioctonion
	$p_res = biquad_sub(biquad_mul($p,$r),biquad_mul(biconjugation($s),$q));
	$q_res = biquad_add(biquad_mul($s,$p),biquad_mul($q,biconjugation($r)));

	return [ $p_res, $q_res ];
}

function bioct_int_power($bioct, $n) {
	assert($n >= 1);
	$res = $bioct;
	for ($p=2; $p<=$n; $p++) $res = bioct_mul($res, $bioct);
	return $res;
}

function bioct_is_immortal($bioct, $power) {
	$bioctpow = bioct_int_power($bioct, $power);
	for ($i=0; $i<8; $i++) {
		for ($j=0; $j<2; $j++) {
			$x1 = bcabs($bioct[$j][$i]);
			$x2 = bcabs($bioctpow[$j][$i]);
			if (substr($x2, -strlen($x1)) != $x1) return false;
		}
	}
	return $bioctpow;
}

function _go($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, &$progr, &$found) {
	$bioct = [ [$a, $b, $c, $d, $e, $f, $g, $h], [$i, $j, $k, $l, $m, $n, $o, $p] ];
	$bioctpower = bioct_is_immortal($bioct, $power);
	if ($bioctpower !== false) {
		$a_ = $bioctpower[0][0];
		$b_ = $bioctpower[0][1];
		$c_ = $bioctpower[0][2];
		$d_ = $bioctpower[0][3];
		$e_ = $bioctpower[0][4];
		$f_ = $bioctpower[0][5];
		$g_ = $bioctpower[0][6];
		$h_ = $bioctpower[0][7];
		$i_ = $bioctpower[1][0];
		$j_ = $bioctpower[1][1];
		$k_ = $bioctpower[1][2];
		$l_ = $bioctpower[1][3];
		$m_ = $bioctpower[1][4];
		$n_ = $bioctpower[1][5];
		$o_ = $bioctpower[1][6];
		$p_ = $bioctpower[1][7];
		if (($i!=0) || ($j!=0) || ($k!=0) || ($l!=0) || ($m!=0) || ($n!=0) || ($o!=0) || ($p!=0)) {
			$str = "BIOC ";
		// 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
		} else 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), ($i, $j, $k, $l, $m, $n, $o, $p)] ^ $power = [($a_, $b_, $c_, $d_, $e_, $f_, $g_, $h_), ($i_, $j_, $k_, $l_, $m_, $n_, $o_, $p_)]";
		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++) {
	for ($i=0; $i<=$distance; $i++) {
	for ($j=0; $j<=$distance; $j++) {
	for ($k=0; $k<=$distance; $k++) {
	for ($l=0; $l<=$distance; $l++) {
	for ($m=0; $m<=$distance; $m++) {
	for ($n=0; $n<=$distance; $n++) {
	for ($o=0; $o<=$distance; $o++) {
	for ($p=0; $p<=$distance; $p++) {
	if ($p == 0) echo "\r".round(memory_get_usage()/1024/1024, 2)." MiB (".count($found)." found); ($a), $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p                                ";
	for ($power=2; $power<=MAX_POWER; $power++) {
	_go($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $a, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $a, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $a, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $a, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $a, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $a, $h, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $a, $i, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $a, $j, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $a, $k, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $a, $l, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $a, $m, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $a, $n, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $a, $o, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $a, $p, $power, $distance, $progr, $found);
	_go($b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n, $o, $p, $a, $power, $distance, $progr, $found);
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}

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