Sven Van Caekenberghe

2011-06-16 10:38:02 UTC

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

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