[squeak-dev] 4.1 - hashed collections still a problem

Levente Uzonyi leves at elte.hu
Fri Mar 26 10:34:41 UTC 2010


The prime table is from the hash changes you made for Pharo.
>From HashChangesI1.1.cs:

Set class methodsFor: 'sizing' stamp: 'SqR 10/25/2009 02:17'!
goodPrimes
 	"Answer a sorted array of prime numbers less than one billion that 
make good
 	hash table sizes. Should be expanded as needed.  See comments 
below code"

 	^#(5 11 17 23 31 43 59 79 107 149 199 269 359 479 641 857 1151 1549 2069
 		...lines with primes...
 		1073741789)

"The above primes past 2096 were chosen carefully so that they do not 
interact badly with 1664525 (used by hashMultiply), and so that gcd(p, 
(256^k) +/- a) = 1, for 0<a<=32 and 0<k<=8.  See Knuth's TAOCP for 
details.  Use the following Integer method to check primality.

isDefinitelyPrime

 	| guess guessSquared delta selfSqrtFloor |
 	self <= 1 ifTrue: [^self error: 'operation undefined'].
 	self even ifTrue: [^self = 2].
 	guess := 1 bitShift: self highBit + 1 // 2.
 	[
 		guessSquared := guess * guess.
 		delta := guessSquared - self // (guess bitShift: 1).
 		delta = 0
 	] whileFalse: [guess := guess - delta].
 	guessSquared = self ifFalse: [guess := guess - 1].
 	selfSqrtFloor := guess.
 	3 to: selfSqrtFloor by: 2 do: [:each | self \\ each = 0 ifTrue: 
[^false]].
 	^true"! !


!


Levente


On Thu, 25 Mar 2010, Andres Valloud wrote:

> I don't have Squeak handy right now, I just meant to say that the code in the 
> VisualWorks method will work correctly as long as isPrime is deterministic.
>
> On 3/23/10 18:58 , David T. Lewis wrote:
>> On Tue, Mar 23, 2010 at 06:18:23PM -0700, Andres Valloud wrote:
>> 
>>> You can look at the bottom of the prime
>>> table in VisualWorks and see an expression that finds them from scratch
>>> (but note that isPrime *MUST BE DETERMINISTIC*).
>>> 
>> Andres,
>> 
>> Is this a reference to the #isPrime in Squeak trunk, which calls
>> #isProbablyPrime for LargePositiveInteger? If so, can you say if
>> there is any difference in the actual results of computing a prime
>> table with a Squeak trunk image compared to the VisualWorks results?
>> 
>> If there is an difference in the results in Squeak versus VisualWorks,
>> this would be important to know.
>> 
>> Thanks,
>> Dave
>> 
>>
>> 
>
>



More information about the Squeak-dev mailing list