Discussion:
[Pharo-project] Integer>>#factorial
Sven Van Caekenberghe
2011-06-16 10:38:02 UTC
Hi,

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

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
2011-06-16 12:52:28 UTC
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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hernan Wilkinson
2011-06-16 15:03:43 UTC
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
Post by Alexandre Bergel
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
http://www.parcplace.net/list/vwnc-archive/1106/msg00080.html the goal
being to optimize the current, naive Integer>>#factorial implementation.
Post by Sven Van Caekenberghe
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
Post by Sven Van Caekenberghe
Integer>>#svcFactorial
self = 0 ifTrue: [ ^ 1 ].
self > 0 ifTrue: [ ^ 1 productUpTo: self ].
self error: 'Not valid for negative integers'
Integer>>#productUpTo: anInteger
(non-inclusive) up to anInteger (inclusive)."
Post by Sven Van Caekenberghe
| difference split |
self assert: (self between: 0 and: anInteger).
"the idea is to multiply LargePositiveIntegers of approximately the
same size"
Post by Sven Van Caekenberghe
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 ].
Post by Sven Van Caekenberghe
difference = 4 ifTrue: [ ^ (anInteger - 3) * (anInteger - 2) *
(anInteger - 1) * anInteger ].
Post by Sven Van Caekenberghe
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 ?
--
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
--
*Hern?n Wilkinson
Agile Software Development, Teaching & Coaching
Mobile: +54 - 911 - 4470 - 7207
email: hernan.wilkinson at 10Pines.com
site: http://www.10Pines.com <http://www.10pines.com/>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20110616/d0a27b38/attachment.html>
Alexandre Bergel
2011-06-16 15:08:40 UTC
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
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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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 at 10Pines.com
site: http://www.10Pines.com
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hernan Wilkinson
2011-06-16 15:13:51 UTC
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
Post by Hernan Wilkinson
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.
Post by Hernan Wilkinson
For me is a good example of a recursive "function"
I agree with you.
Post by Hernan Wilkinson
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
Post by Hernan Wilkinson
On Thu, Jun 16, 2011 at 9:52 AM, Alexandre Bergel <
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.
Post by Hernan Wilkinson
Your implementation could be next to the standard one though.
Cheers,
Alexandre
http://www.parcplace.net/list/vwnc-archive/1106/msg00080.html the goal
being to optimize the current, naive Integer>>#factorial implementation.
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
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
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
Integer>>#svcFactorial
self = 0 ifTrue: [ ^ 1 ].
self > 0 ifTrue: [ ^ 1 productUpTo: self ].
self error: 'Not valid for negative integers'
Integer>>#productUpTo: anInteger
(non-inclusive) up to anInteger (inclusive)."
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
| difference split |
self assert: (self between: 0 and: anInteger).
"the idea is to multiply LargePositiveIntegers of approximately
the same size"
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
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 ].
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
difference = 4 ifTrue: [ ^ (anInteger - 3) * (anInteger - 2) *
(anInteger - 1) * anInteger ].
Post by Hernan Wilkinson
Post by Sven Van Caekenberghe
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 ?
Post by Hernan Wilkinson
--
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
--
Hern?n Wilkinson
Agile Software Development, Teaching & Coaching
Mobile: +54 - 911 - 4470 - 7207
email: hernan.wilkinson at 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 at 10Pines.com
site: http://www.10Pines.com <http://www.10pines.com/>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20110616/17b441ed/attachment.html>
Alexandre Bergel
2011-06-16 15:17:18 UTC
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
Post by Hernan Wilkinson
oh, ok, I undestand now :-)... it is to show the limitations in Java.
Thanks!
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
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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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 at 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 at 10Pines.com
site: http://www.10Pines.com
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Lorenzo Schiavina
2011-06-16 17:46:34 UTC
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 at 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 at 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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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 at 10Pines.com
site: http://www.10Pines.com

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20110616/222acf42/attachment.html>
Andres Valloud
2011-06-18 19:36:57 UTC
But unfortunately we do not have tail recursion (that I know)...
Post by Lorenzo Schiavina
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 at 10pines.com>
*To:* Pharo-project at lists.gforge.inria.fr
<mailto:Pharo-project at 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
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
http://www.parcplace.net/list/vwnc-archive/1106/msg00080.html
the goal being to optimize the current, naive
Integer>>#factorial implementation.
Post by Sven Van Caekenberghe
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
Post by Sven Van Caekenberghe
Integer>>#svcFactorial
self = 0 ifTrue: [ ^ 1 ].
self > 0 ifTrue: [ ^ 1 productUpTo: self ].
self error: 'Not valid for negative integers'
Integer>>#productUpTo: anInteger
(non-inclusive) up to anInteger (inclusive)."
Post by Sven Van Caekenberghe
| difference split |
self assert: (self between: 0 and: anInteger).
"the idea is to multiply LargePositiveIntegers of
approximately the same size"
Post by Sven Van Caekenberghe
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 ].
Post by Sven Van Caekenberghe
difference = 4 ifTrue: [ ^ (anInteger - 3) * (anInteger - 2)
* (anInteger - 1) * anInteger ].
Post by Sven Van Caekenberghe
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 ?
--
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
--
*Hern?n Wilkinson
Agile Software Development, Teaching & Coaching
Mobile: +54 - 911 - 4470 - 7207
email: hernan.wilkinson at 10Pines.com
site: http://www.10Pines.com <http://www.10pines.com/>*
Levente Uzonyi
2011-06-16 14:00:59 UTC
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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

Levente
Nicolas Cellier
2011-06-16 20:21:33 UTC
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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
? ? ? ?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
Nicolas Cellier
2011-06-16 21:15:30 UTC
Hmm some methods are missing, but squeaksource seems down...

Nicolas
Post by Nicolas Cellier
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)
factorial
? self < 3 ifTrue: [^self].
? x := (self highBit - 1).
? p := (x + 1) * self // x >> 1 - 1.
? ^(p factorial)*(p+1 productUpTo: self)
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
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
? ? ? ?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
Stéphane Ducasse
2011-06-18 06:47:08 UTC
Is there an interest for security or other points?

Stef
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
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
Nicolas Cellier
2011-06-18 07:28:38 UTC
Mathematical recreation ?
The sake of complexifty ? (it's fun when you can't even understand

Nicolas
Is there an interest for security or other points?
Stef
Post by Sven Van Caekenberghe
Hi,
Integer>>#svcFactorial
? ? ? 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
Stéphane Ducasse
2011-06-18 12:30:12 UTC