[Pharo-project] Integer>>#factorial

Levente Uzonyi leves at elte.hu
Thu Jun 16 10:00:59 EDT 2011


On Thu, 16 Jun 2011, 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 ?

IMHO no, but if you want really fast algorithms, then you should visit 
this page: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm


Levente

>
> Sven
>
>
>




More information about the Pharo-dev mailing list