[Cuis-dev] Problems in class Number

Andres Valloud ten at smallinteger.com
Thu Oct 10 20:16:04 PDT 2019


Another 10% or so.  Looks like this is finally hitting diminishing returns.

On 10/10/19 20:04, Andres Valloud via Cuis-dev wrote:
> Do you see any way to improve upon it?  If not... maybe it's time to 
> integrate the thing already.
> 
> On 10/10/19 20:02, Agustín Sansone via Cuis-dev wrote:
>> With this last improvement:
>> Time millisecondsToRun:
>>         [10000 timesRepeat: [1 to: 1600 do: [:e | e isPrimeFast2]] ]  
>> 3502
>>
>> Without it:
>> Time millisecondsToRun:
>>          [10000 timesRepeat: [1 to: 1600 do: [:e | e isPrimeFast]] ]  
>> 4982
>>
>> It is indeed a 30% speed increase for numbers up to 1521.
>>
>> El jue., 10 oct. 2019 a las 23:35, Andres Valloud via Cuis-dev 
>> (<cuis-dev at lists.cuis.st <mailto:cuis-dev at lists.cuis.st>>) escribió:
>>
>>     Hmmm, in here,
>>
>>              self < 384 ifTrue: [
>>                      "Approximate sqrtFloor to avoid computational 
>> expense"
>>                      3 to: (self bitShift: -3) + 1 by: 2 do:
>>                              [:each | self \\ each = 0 ifTrue: [ 
>> ^false ]].
>>                      ^true
>>              ].
>>
>>
>>     the loop should start at 7 because the factors 3 and 5 have already
>>     been
>>     excluded.  This gains noticeable speed for smallish integers (because
>>     384 sqrtFloor is just 19).  Looking into this further led to another
>>     30%
>>     speed increase.  Would you mind checking?
>>
>>     On 10/10/19 18:40, Agustín Sansone via Cuis-dev wrote:
>>      >     Here's something really important: doing too much
>>     micro-optimization
>>      >     detracts from the motivation to implement better things.  I'd
>>     say we
>>      >     leave things with the round of 30.
>>      >
>>      >
>>      > Okay. This is the 30*k version.
>>      >
>>     --     Cuis-dev mailing list
>>     Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>
>>     https://lists.cuis.st/mailman/listinfo/cuis-dev
>>
>>
-------------- next part --------------
'From Cuis 5.0 [latest update: #3866] on 10 October 2019 at 8:14:53 pm'!

!Integer methodsFor: 'testing' stamp: 'sqr 10/10/2019 20:14:05'!
isPrimeFast2g

	self < 3 ifTrue: [^self = 2].
	self even ifTrue: [^false].
	self \\ 3 = 0 ifTrue: [^self = 3].
	self \\ 5 = 0 ifTrue: [^self = 5].
	self < 3970 ifTrue: [
		"Approximate sqrtFloor to avoid computational expense"
		self \\ 7 = 0 ifTrue: [^self = 7].
		self \\ 11 = 0 ifTrue: [^self  = 11].
		self \\ 13 = 0 ifTrue: [^self  = 13].
		17 to: (self bitShift: -6) + 16 by: 2 do:
			[:each | self \\ each = 0 ifTrue: [^false]].
		^true
	].
	"Now 2, 3 and 5 do not divide self. So, self is of the form
	30*k + {1, 7, 11, 13, 17, 19, 23, 29} for integer k >= 0.
	The 31 case below is the 30k+1 case, excluding k = 0"
	0 to: self sqrtFloor by: 30 do: [:each |
		self \\ (each+7) = 0 ifTrue: [^false].
		self \\ (each+11) = 0 ifTrue: [^false].
		self \\ (each+13) = 0 ifTrue: [^false].
		self \\ (each+17) = 0 ifTrue: [^false].
		self \\ (each+19) = 0 ifTrue: [^false].
		self \\ (each+23) = 0 ifTrue: [^false].
		self \\ (each+29) = 0 ifTrue: [^false].
		self \\ (each+31) = 0 ifTrue: [^false].
	].
	^true! !


More information about the Cuis-dev mailing list