[Pharo-project] Integer>>#factorial
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
Hi Sven, I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP. Your implementation could be next to the standard one though. Cheers, Alexandre 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
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...) For me is a good example of a recursive "function" I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation? On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <alexandre.bergel@me.com>wrote:
Hi Sven,
I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP.
Your implementation could be next to the standard one though.
Cheers, Alexandre
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
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- *Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com <http://www.10pines.com/>*
I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...)
This is not something that can be done in Java, the language used for teaching OO in my university. Having methods like #abs, #factorial, #+ defined on Integer is an excellent reason why we do not need a class java.util.Math. These methods look natural to us, but they are not for other people.
For me is a good example of a recursive "function"
I agree with you.
I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation?
Because it is a natural distribution of responsibility, that cannot be easily done in Java or C#. Alexandre
On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <alexandre.bergel@me.com> wrote: Hi Sven,
I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP.
Your implementation could be next to the standard one though.
Cheers, Alexandre
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
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
oh, ok, I undestand now :-)... it is to show the limitations in Java. Thanks! On Thu, Jun 16, 2011 at 12:08 PM, Alexandre Bergel <alexandre.bergel@me.com>wrote:
I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...)
This is not something that can be done in Java, the language used for teaching OO in my university. Having methods like #abs, #factorial, #+ defined on Integer is an excellent reason why we do not need a class java.util.Math.
These methods look natural to us, but they are not for other people.
For me is a good example of a recursive "function"
I agree with you.
I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation?
Because it is a natural distribution of responsibility, that cannot be easily done in Java or C#.
Alexandre
On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel < alexandre.bergel@me.com> wrote: Hi Sven,
I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP.
Your implementation could be next to the standard one though.
Cheers, Alexandre
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
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- *Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com <http://www.10pines.com/>*
One problem that I see in programming in general, that a piece of code can never be well done in the absolute, but it can always be badly written. Cheers, Alexandre On 16 Jun 2011, at 11:13, Hernan Wilkinson wrote:
oh, ok, I undestand now :-)... it is to show the limitations in Java.
Thanks!
On Thu, Jun 16, 2011 at 12:08 PM, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...)
This is not something that can be done in Java, the language used for teaching OO in my university. Having methods like #abs, #factorial, #+ defined on Integer is an excellent reason why we do not need a class java.util.Math.
These methods look natural to us, but they are not for other people.
For me is a good example of a recursive "function"
I agree with you.
I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation?
Because it is a natural distribution of responsibility, that cannot be easily done in Java or C#.
Alexandre
On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <alexandre.bergel@me.com> wrote: Hi Sven,
I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP.
Your implementation could be next to the standard one though.
Cheers, Alexandre
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
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
IMHO factorial is a good OO example because you have not the usual limitation of "traditional" languages and you can understand the OOP power. Try, for example 1000 factorial in ST and in other languages. Cheers Lorenzo ----- Original Message ----- From: Hernan Wilkinson To: Pharo-project@lists.gforge.inria.fr Sent: Thursday, June 16, 2011 5:03 PM Subject: Re: [Pharo-project] Integer>>#factorial I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...) For me is a good example of a recursive "function" I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation? On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <alexandre.bergel@me.com> wrote: Hi Sven, I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP. Your implementation could be next to the standard one though. Cheers, Alexandre 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 > > -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. -- Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com
But unfortunately we do not have tail recursion (that I know)... On 6/16/11 10:46 , Lorenzo Schiavina wrote:
IMHO factorial is a good OO example because you have not the usual limitation of "traditional" languages and you can understand the OOP power. Try, for example 1000 factorial in ST and in other languages. Cheers Lorenzo
----- Original Message ----- *From:* Hernan Wilkinson <mailto:hernan.wilkinson@10pines.com> *To:* Pharo-project@lists.gforge.inria.fr <mailto:Pharo-project@lists.gforge.inria.fr> *Sent:* Thursday, June 16, 2011 5:03 PM *Subject:* Re: [Pharo-project] Integer>>#factorial
I agree with Alex, but I don't see why, alex, you say it is a good example for teaching OO (the smalltalk factorial implementation...) For me is a good example of a recursive "function" I think it would be a good OO example it it was using "object recursion" or the one that could be implemented in a prototyped language... why do you think it is a good oo example the smalltalk factorial implementation?
On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <alexandre.bergel@me.com <mailto:alexandre.bergel@me.com>> wrote:
Hi Sven,
I am not sure it should replace the standard implementation. Integer>>factorial is essentially there for teaching purpose in my opinion. I am not sure how often factorial is used in practice. The most important for me is not it to be fast, but to be an excellent example of OOP.
Your implementation could be next to the standard one though.
Cheers, Alexandre
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 > >
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- *Hernán Wilkinson Agile Software Development, Teaching & Coaching Mobile: +54 - 911 - 4470 - 7207 email: hernan.wilkinson@10Pines.com site: http://www.10Pines.com <http://www.10pines.com/>*
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
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@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
Hmm some methods are missing, but squeaksource seems down... Nicolas 2011/6/16 Nicolas Cellier <nicolas.cellier.aka.nice@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@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
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
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@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
participants (8)
-
Alexandre Bergel -
Andres Valloud -
Hernan Wilkinson -
Levente Uzonyi -
Lorenzo Schiavina -
Nicolas Cellier -
Stéphane Ducasse -
Sven Van Caekenberghe