#!/usr/bin/php
<?php

// ATTENTION: THIS OPTIMIZED SCRIPT VARIANT ONLY WORKS WITH BASE 10, POWER 2

# -------------------------------------------------

define('FIX_PAD',       18);
define('ONLY_IM',     true);
define('SHOW_RESULT', true);
define('SHOW_DIST',   true);
define('CHECKED_LOOKUP_READ',  false); // true = Much faster. Requires previous LOOKUP_WRITE,
define('CHECKED_LOOKUP_WRITE', false); // true = Prevent that a check is made more than one time. Requires much memory
define('CHECKED_LOOKUP_SAVE',  false); // true = Increases size of SAV file, but keeps performance after restart of the program
define('CHECKED_LOOKUP_SIZELIMIT', 10); // X+"/"+Y
define('OUT_FILE', 'complex_power2_search_hyperspeed.out');
define('SAV_FILE', 'complex_power2_search_hyperspeed.sav');
define('MIN_X_SIZE', 0);
define('MIN_Y_SIZE', 0);

// TODO: Make a better continue-option ($progress backup) when nothing is found for a long time
// TODO: when something was found on ba1020 and ba3020, then it will also find something on ba5020, ba7020 and ba9020
define('BEGIN_PROGRESS', 0);

define('AUTO_ZEROS', 0);

# -------------------------------------------------

if (file_exists(SAV_FILE)) {
	list($found_x, $found_y, $checked, $found) = unserialize(file_get_contents(SAV_FILE));
} else {
	$found_x = array();
	$found_y = array();
	$checked = array();
	$found = array();
	echo "COMPLEX IMMORTAL NUMBER SEARCH 1.0\n";
	echo "\n";
	echo "Parameters:  Min base     = 10\n";
	echo "             Max base     = 10\n";
	echo "             Min power    = 2\n";
	echo "             Max power    = 2\n";
	echo "             Only Im(z)>0 = ".(ONLY_IM ? 'Yes' : 'No')."\n";
	echo "\n";
}

refilter_found_xy();

for ($progress=BEGIN_PROGRESS; true; $progress++) {
	$something_found = false;

	echo "Round: $progress                                              \r";

	$new_y = 0;
	$prog2 = $progress*2;

	for ($i=0; $i<$progress; $i++) {
		if (_go($progress, $i, $progress, $new_y, 'A')) $something_found = true; # X<Y (this case is not possible? but I cannot proove it)
		if (_go($progress, $progress, $i, $new_y, 'B')) $something_found = true; # X>Y
		$new_y += $prog2;
	}

	for ($i=0; $i<$progress; $i++) {
		foreach ($filtered_found_x as $x_suffix) {
			foreach ($filtered_found_y as $y_suffix) {
				for ($zeros_x=0; $zeros_x<=AUTO_ZEROS; $zeros_x++) {
					for ($zeros_y=0; $zeros_y<=AUTO_ZEROS; $zeros_y++) {
						$x = $i;
						$y = $progress;
						$x .= str_repeat('0', $zeros_x);
						$y .= str_repeat('0', $zeros_y);
						if (_go($progress, $x.$x_suffix, $y.$y_suffix, null, 'aa'.$progress)) $something_found = true;
						#if (_go($progress, $x.$x_suffix, $y,           null, 'ab'.$progress)) $something_found = true;
						#if (_go($progress, $x,           $y.$y_suffix, null, 'ac'.$progress)) $something_found = true;

						$x = $progress;
						$y = $i;
						$x .= str_repeat('0', $zeros_x);
						$y .= str_repeat('0', $zeros_y);
						if (_go($progress, $x.$x_suffix, $y.$y_suffix, null, 'ba'.$progress)) $something_found = true;
						#if (_go($progress, $x.$x_suffix, $y,           null, 'bb'.$progress)) $something_found = true;
						#if (_go($progress, $x,           $y.$y_suffix, null, 'bc'.$progress)) $something_found = true;
					}
				}
			}
		}
	}

	foreach ($filtered_found_x as $x_suffix) {
		foreach ($filtered_found_y as $y_suffix) {
			for ($zeros_x=0; $zeros_x<=AUTO_ZEROS; $zeros_x++) {
				for ($zeros_y=0; $zeros_y<=AUTO_ZEROS; $zeros_y++) {
					$x = $progress;
					$y = $progress;
					$x .= str_repeat('0', $zeros_x);
					$y .= str_repeat('0', $zeros_y);
					if (_go($progress, $x.$x_suffix, $y.$y_suffix, null, 'ca'.$progress)) $something_found = true;
					#if (_go($progress, $x.$x_suffix, $y,           null, 'cb'.$progress)) $something_found = true;
					#if (_go($progress, $x,           $y.$y_suffix, null, 'cc'.$progress)) $something_found = true;
				}
			}
		}
	}

	if ($something_found) $progress = 0; // Restart, because the $found_x / $found_y arrays have been changed!
}

function endswith($string, $test) {
	// https://stackoverflow.com/questions/619610/whats-the-most-efficient-test-of-whether-a-php-string-ends-with-another-string?lq=1
	$strlen = strlen($string);
	$testlen = strlen($test);
	#if ($testlen > $strlen) return false;
	return substr_compare($string, $test, $strlen - $testlen, $testlen) === 0;
}

function _go($round, $x, $y, $new_y=null, $info='') {
#	if ($y%2 == 1) return; // y must be even because "2xy === y"

	// For Base 10 power 2, X can only end with 3 or 8
	// 2*x*y        == y
	// 2*3*2 ==  12 == 2
	// 2*3*4 ==  24 == 4
	// 2*3*6 ==  36 == 6
	// 2*3*8 ==  48 == 8
	// 2*8*2 ==  32 == 2
	// 2*8*4 ==  64 == 4
	// 2*8*6 ==  96 == 6
	// 2*8*8 == 128 == 8
#	if (ONLY_IM) {
#		$last_digit = substr($x,-1);
#		if (($last_digit != '3') && ($last_digit != '8')) return;
#	}

	$x = ltrim($x, "0");
	$y = ltrim($y, "0");

	global $checked;
	$search_key = $x.'/'.$y;
	if (is_null(CHECKED_LOOKUP_SIZELIMIT) || (strlen($search_key) <= CHECKED_LOOKUP_SIZELIMIT)) {
		if (CHECKED_LOOKUP_READ && isset($checked[$search_key])) return false;
		if (CHECKED_LOOKUP_WRITE) $checked[$search_key] = 1;
	}

	//echo "Round $round, Checking: (".$x." + ".$y."i)^2                            \r";

	// Power 2:
	// (x+yi)^2 = x^2 + 2xyi - y^2 = (x^2-y^2 + 2xyi)
	// Therefore:
	// (x+yi) is immortal if
	// (x^2-y^2)^2 === x^2-y^2 mod 2^...
	// (2xy)^2     === 2xy     mod 2^...

	if (is_null($new_y)) {
		$new_y = bcmul(bcmul($x,$y),2);
		#if ($new_y[0] == '-') $new_y = substr($new_y, 1);
	}
	if (($new_y == 0) && (ONLY_IM)) return false;
	if (!endswith($new_y,$y)) return false;

	$new_x = bcsub(bcmul($x,$x),bcmul($y,$y));
	#if ($new_x[0] == '-') $new_x = substr($new_x, 1);
	if (!endswith($new_x,$x)) return false;

	//echo "Round $round, Candidate: (".$x." + ".$y."i)^2                                \r";

	global $found;
	if (isset($found[$x.'/'.$y])) return false;
	$found[$x.'/'.$y] = 1;

	global $found_x;
	if (/* ($new_x != 0) && */(!in_array($x,$found_x))) { $found_x[] = $x; refilter_found_xy(); }
	global $found_y;
	if (/* ($new_y != 0) && */(!in_array($y,$found_y))) { $found_y[] = $y; refilter_found_xy(); }

	file_put_contents(SAV_FILE, serialize(array($found_x,$found_y,CHECKED_LOOKUP_SAVE ? $checked : array(),$found)));

	$line = '';
	$dist = bcround(bcsqrt(bcadd(bcmul($x,$x),bcmul($y,$y)),2));
	if (SHOW_DIST) $line .= "[".str_pad($dist,FIX_PAD,'0',STR_PAD_LEFT)."] ";
	$line .= "IMMORTAL($info): (".str_pad($x,FIX_PAD,' ',STR_PAD_LEFT)." + ".str_pad($y,FIX_PAD,' ',STR_PAD_LEFT)."i) ^ 2";
	if (SHOW_RESULT) $line .= " = (".$new_x." + ".$new_y."i)";
	$line .= "\n";
	file_put_contents(OUT_FILE, $line, FILE_APPEND);
	echo "\r$line";

	return true;
}

function bcceil($val) {
	// https://stackoverflow.com/questions/1642614/how-to-ceil-floor-and-round-bcmath-numbers
	if (($pos = strpos($val, '.')) !== false) {
		if ($val[$pos+1] != 0 && $val[0] != '-')
			return bcadd(substr($val, 0, $pos), 1, 0);
		else
			return substr($val, 0, $pos);
	}
	return $val;
}

function bcfloor($val) {
	// https://stackoverflow.com/questions/1642614/how-to-ceil-floor-and-round-bcmath-numbers
	if (($pos = strpos($val, '.')) !== false) {
		if ($val[$pos+1] != 0 && $val[0] == '-')
			return bcsub(substr($val, 0, $pos), 1, 0);
		else
			return substr($val, 0, $pos);
	}
	return $val;
}

function bcround($val, $precision = 0) {
	// https://stackoverflow.com/questions/1642614/how-to-ceil-floor-and-round-bcmath-numbers
	if (($pos = strpos($val, '.')) !== false) {
		if ($precision > 0) {
			$int = substr($val, 0, $pos);
			$pos2 = ++$pos+$precision;
			if ($pos2 < strlen($val)) {
				$val2 = sprintf('%s.%s', substr($val, $pos, $pos2-$pos), substr($val, $pos2));
				$val2 = $val2[0] >= 5 ? bcceil($val2) : bcfloor($val2);
				if (strlen($val2) > $precision)
					return bcadd($int, $val[0] == '-' ? -1 : 1, 0);
				else
					return sprintf('%s.%s', $int, rtrim($val2, '0'));
			}
			return $val;
		} else {
			if ($val[$pos+1] >= 5)
				return ($val[0] == '-' ? bcfloor($val) : bcceil($val));
			else
				return ($val[0] == '-' ? bcceil($val) : bcfloor($val));
		}
	}
	return $val;
}

function refilter_found_xy() {
	global $filtered_found_x;
	global $filtered_found_y;
	global $found_x;
	global $found_y;

	$filtered_found_x = array();
	foreach ($found_x as $x_suffix) {
		if (strlen($x_suffix) < MIN_X_SIZE) continue;
		$filtered_found_x[] = $x_suffix;
	}

	$filtered_found_y = array();
	foreach	($found_y as $y_suffix) {
		if (strlen($y_suffix) < MIN_Y_SIZE) continue;
		$filtered_found_y[] = $y_suffix;
	}
}