diff -r 803a48c7a8c5 -r 9fd9ea890de1 LargeInteger.st --- 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) + ]. + ] " !