#TUNING by cg
class: LargeInteger
added: #isPerfectSquare
changed: #mightBeASquare
--- a/LargeInteger.st Mon Dec 02 12:36:27 2019 +0100
+++ b/LargeInteger.st Mon Dec 02 13:20:25 2019 +0100
@@ -5547,10 +5547,34 @@
"Modified: 5.11.1996 / 16:12:56 / cg"
!
+isPerfectSquare
+ self mightBeASquare ifFalse:[^ false].
+ ^ super isPerfectSquare.
+
+ "
+ 2r1010101101010110101010101010101010101010101010101010 isPerfectSquare
+ 123456789012345678901234567890 isPerfectSquare
+ 123456789012345678901234567890 squared isPerfectSquare
+ 100 factorial isPerfectSquare
+ 100 factorial squared isPerfectSquare
+ 1000 factorial isPerfectSquare
+ 1000 factorial squared isPerfectSquare
+
+ Time millisecondsToRun:[
+ |n|
+ n := 100 factorial squared.
+ 1000 timesRepeat:[
+ n isPerfectSquare
+ ]
+ ]
+ "
+!
+
mightBeASquare
"a quick (and cheap) check if the receiver is possibly a square"
- | lsb |
+ | lsb "{ Class: SmallInteger}"
+ lHdigit|
self negative ifTrue:[ ^ false ].
@@ -5570,6 +5594,20 @@
Also, the receiver must be an aven power of two."
lsb := self byteAt: 1.
+ lHdigit := lsb bitAnd:16r0F.
+ lHdigit > 9 ifTrue:[^ false].
+ "/ 0..9
+ lHdigit > 1 ifTrue:[
+ "/ 2..9
+ lHdigit == 4 ifFalse:[
+ "/ 2,3,5..9
+ lHdigit == 9 ifFalse:[
+ "/ 2,3,5..8
+ ^ false
+ ]
+ ]
+ ].
+
^ (lsb == 0 and: [ self lowBit odd ]) "00 (and even power of 2)"
or: [ lsb = 16r40 "40"
or: [ (lsb bitAnd: 16r7) = 1 "any|1 or any|9"
@@ -5578,8 +5616,21 @@
"
+ 2r1010101101010110101010101010101010101010101010101010 mightBeASquare
123456789012345678901234567890 mightBeASquare
- 123456789012345678901234567890 squared mightBeASquare
+ 123456789012345678901234567890 squared mightBeASquare
+ "
+ "
+ |n s1 s2|
+ n := 100000.
+ [n <= 200000] whileTrue:[
+ s1 := n squared.
+ s2 := (n+1) squared.
+ self assert:s1 isPerfectSquare.
+ s1+1 to:s2-1 do:[:nonSquares |
+ self assert:(nonSquares isPerfectSquare not)
+ ].
+ ]
"
!