[Pharo-project] Integer>>#factorial

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Thu Jun 16 17:15:30 EDT 2011


Hmm some methods are missing, but squeaksource seems down...

Nicolas

2011/6/16 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
> Anyway, algorithm will be dominated by multiplication cost, so you
> need at least a Karatsuba algorithm or Toom-Cook or Fourier transform
> for monsters factorials.
>
> For Karatsuba, the best is to multiply well equilibrated LargeIntegers
> (some having aproximately same size).
>
> It would be optimal to split n! at p!*(n!/p!) such that p! = (n!/p!)
> (approximately)
> That means n! = p! squared
> Using a Stirling like  n! log = (n*n log - n), we find a rough
> approximation for the ratio
> p/n  = ( n log + 1 ) / (2 * n log)
>
> Thus we can use this approximation:
> factorial
>   self < 3 ifTrue: [^self].
>   x := (self highBit - 1).
>   p := (x + 1) * self // x >> 1 - 1.
>   ^(p factorial)*(p+1 productUpTo: self)
>
> For spliting (n!/p!) I suggest using this ratio:
> productUpTo: n
>   n > self ifFalse: [^n].
>   x := (n highBit - 1)*self highBit.
>   p = x * (n + self) + (n - self)  // x >> 1.
>   ^(self productUpTo: p)*(p+1 productUpTo: n)
>
> But the highBit and // evaluations cost, so it's not that usefull...
>
> John Brant strategy is more efficient (evaluate 1 out of 2 and recursively).
>
> But the Prime Swing wins on Cog (not the case in VWNC 7.7).
>
> Just play with http://www.squeaksource.com/FactorialContest.html if you want.
>
> Nicolas
>
> 2011/6/16 Sven Van Caekenberghe <sven at beta9.be>:
>> 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