Enhancement Request: Adding population count for Integers to
the standard image
Markus Gaelli
gaelli at emergent.de
Fri Dec 10 17:49:54 UTC 2004
I might offer something to this discussion (actually I programmed that
method long time ago, for my beginnings of the fractal music generator
Musinum, see Squeakmap
and http://reglos.de/musinum/ )
Counting up digits in a number translates from German "Quersumme" to
"cross sum"
Integer >> crossSumBase: aBase
self < aBase ifTrue: [^self].
^self \\ aBase + (self // aBase crossSumBase: aBase)
So your method would become:
Integer >> popCount
^self crossSumBase:2
I checked with your test cases and they still run :-)
My solution is more general and some might like that it is recursive -
according to "bench" it is also six times slower... :-/
Mine would currently also allow cross sums of negative numbers and
LargeInteger.
[123456789123456789 popCount] bench '6411.31773645271 per second.'
[123456789123456789 crossSumBase: 2] bench '1138.572285542891 per
second.'
(I am on a G5)
Alans idea about having optimized code in parallel with more abstract
code comes to mind here, so if anybody needs a nice test case to
implement this, here it was.
Markus
On Dec 10, 2004, at 4:55 PM, Matthew S. Hamrick wrote:
> So the idea for using the name 'popCount' comes from the fact that the
> community that's likely to use the instruction recognizes that name.
>
> On the other hand, however, yes, the name is a little cryptic, and
> Squeak's role in education should not be under-appreciated. Maybe we
> could:
>
> 1. define a method called numberOfOnes in Integer that performs the
> operation.
> 1.a. this method would raise an error if we attempted to send it to
> a negative integer.
> 2. define a method called numberOfZeros in Integer that performs the
> converse operation (counting the number of zeros in a negative
> integer.)
> 2.a this method would raise an error if we attempted to send it to a
> positive integer.
> 3. define a method called popCount in Integer that simply calls
> numberOfOnes.
>
> This would have the benefit of providing a clearer name for the
> operation for people who might happen upon it while browsing the
> source. And considering that the implementation makes use of number
> theory that is definitely NOT taught in high-schools, a serendipitous
> encounter by a secondary school student and this method might lead to
> motivation to study more number theory and less arithmetic. At the
> same time, the cryptanalysis community will see the function using the
> 'typical' name: popCount.
>
>
More information about the Squeak-dev
mailing list
|