On 16 Jun 2011, at 06:38, 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
>
>