Hi Jasen! :-)

 PS>> Thus, no integer ending in 2, 3, 7, or 8 can be the square of any 
 PS>> other integer. This reduces the problem space by 40%. ;)
 JB> hmm, to do that I'd need to divide by 10...
Well, you didn't say anything about the representation of your bignums. ;)

[...]
 JB> but it seems though that the more terminal bits I examine the less
 JB> cost-effective it becomes.
I don't think there's a good heuristic besides really doing a square root,
but doing an approximation can be costly on bignums.

Ciao
Pascal

--- Msged/LNX 6.1.1