#!/usr/bin/perl
use 5.016;
use warnings;
 
# ref: http://p...content-available-to-author-only...t.jp/2009/01/blog-post_22.html
 
sub _sq {
	my ($n, $q, $s) = @_;
 
	($s > 0) or return $q;
 
	return ($n >= $q + $s ?
		_sq($n - ($q + $s), $q / 2 + $s, int($s / 4)) :
		_sq($n, $q / 2, int($s / 4))
	);
}
 
sub _ss { ($_[1] * 4 > $_[0]) ? $_[1] : _ss($_[0], $_[1] * 4) }
 
sub f { _sq($_[0], 0, _ss($_[0], 1)) }
 
foreach(0, 1, 4, 100, 5929, 788544, 99980001){
	say $_, " => ", f($_);
}
 

IyEvdXNyL2Jpbi9wZXJsCnVzZSA1LjAxNjsKdXNlIHdhcm5pbmdzOwoKIyByZWY6IGh0dHA6Ly9wLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi50LmpwLzIwMDkvMDEvYmxvZy1wb3N0XzIyLmh0bWwKCnN1YiBfc3EgewoJbXkgKCRuLCAkcSwgJHMpID0gQF87CgoJKCRzID4gMCkgb3IgcmV0dXJuICRxOwoKCXJldHVybiAoJG4gPj0gJHEgKyAkcyA/CgkJX3NxKCRuIC0gKCRxICsgJHMpLCAkcSAvIDIgKyAkcywgaW50KCRzIC8gNCkpIDoKCQlfc3EoJG4sICRxIC8gMiwgaW50KCRzIC8gNCkpCgkpOwp9CgpzdWIgX3NzIHsgKCRfWzFdICogNCA+ICRfWzBdKSA/ICRfWzFdIDogX3NzKCRfWzBdLCAkX1sxXSAqIDQpIH0KCnN1YiBmIHsgX3NxKCRfWzBdLCAwLCBfc3MoJF9bMF0sIDEpKSB9Cgpmb3JlYWNoKDAsIDEsIDQsIDEwMCwgNTkyOSwgNzg4NTQ0LCA5OTk4MDAwMSl7CglzYXkgJF8sICIgPT4gIiwgZigkXyk7Cn0K