[Pharo-project] Integer>>#factorial

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Sat Jun 18 03:28:38 EDT 2011


Mathematical recreation ?
The sake of complexifty ? (it's fun when you can't even understand
your own question after reading the answers).
Maybe you should ask Paul Bauman about his motivation.

Nicolas

2011/6/18 Stéphane Ducasse <stephane.ducasse at inria.fr>:
> Is there an interest for security or other points?
>
> Stef
>
> On Jun 16, 2011, at 12:38 PM, Sven Van Caekenberghe wrote:
>
>> Hi,
>>
>> On Planet Smalltalk I read about this challenge: http://www.parcplace.net/list/vwnc-archive/1106/msg00080.html the goal being to optimize the current, naive Integer>>#factorial implementation.
>>
>> I had some old Lisp code hanging around, implementing an algorithm that I once found somewhere, and I ported it to Smalltalk. I am sure there are faster solutions, but this one is twice as fast as the original while still being easy to understand and it has a useful, safe helper method:
>>
>> Integer>>#svcFactorial
>>       "Answer the factorial of the receiver."
>>
>>       self = 0 ifTrue: [ ^ 1 ].
>>       self > 0 ifTrue: [ ^ 1 productUpTo: self ].
>>       self error: 'Not valid for negative integers'
>>
>> Integer>>#productUpTo: anInteger
>>       "Answer the product of all integers from the receiver (non-inclusive) up to anInteger (inclusive)."
>>
>>       | difference split |
>>       self assert: (self between: 0 and: anInteger).
>>       "the idea is to multiply LargePositiveIntegers of approximately the same size"
>>       difference := anInteger - self.
>>       difference = 0 ifTrue: [ ^ 1 ].
>>       difference = 1 ifTrue: [ ^ anInteger ].
>>       difference = 2 ifTrue: [ ^ (anInteger - 1) * anInteger ].
>>       difference = 3 ifTrue: [ ^ (anInteger - 2) * (anInteger - 1) * anInteger ].
>>       difference = 4 ifTrue: [ ^ (anInteger - 3) * (anInteger - 2) * (anInteger - 1) * anInteger ].
>>       split := (self + anInteger) bitShift: -1.
>>       ^ (self productUpTo: split) * (split productUpTo: anInteger)
>>
>> Would it be a good idea to replace the current implementation with this one ?
>>
>> Sven
>>
>>
>
>
>




More information about the Pharo-dev mailing list