Detecting Squares Cheaply

So, moritz_ on #Perl6 asked about detecting squares cheaply, ie without just calling sqrt. A quick Google search led me to Detecting Squares, which has a nice discussion on quick filters you can use. moritz_ got me thinking about looking at the same problem in more computer-oriented terms. It's quickest to compute if you can just look at the least significant byte of the number instead of computing mod 100 (as the above page suggests). So here's a quick and dirty Perl 5 program to find the magic numbers:

	my $x;
	for ($x = 1; $x < 100000; $x++)
	{
	$count{($x*$x) % 256}++;
	}
	my $n = 0;
	foreach my $number (sort { $a <=> $b} keys %count)
	{
	print "$number => $count{$number}\n";
	$n++;
	}
	print "$n\n";

view raw squares.pl hosted with ❤ by GitHub

That determines there are 44 numbers that repeat if you look at the first hundred thousand squares mod 256. And in fact, you don't need to look at nearly that number. Say your number N = 256n + m, where m is less than 256. Then N squared is 65536n^2 + 512nm + m^2, which is congruent to m^2 mod 256. That is to say, the least significant byte of N is the only byte which contributes to the least significant byte of N squared.

This means that given a random number, you can determine 212 out of 256 times (about 82%) that the number is not a square by doing a simple table lookup on the last byte of the number.

(I think a really pretty little Perl 6 program could also be used to demonstrate it, but I'm not going to try while my Perl 6 build is broken.)