HP Forums
Factorials and the 35s - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: Factorials and the 35s (/thread-173527.html)

Factorials and the 35s - Dieter - 10-19-2010

One thing I like about the 35s (and my first HP, the 34C) is the combined factorial and Gamma-function. One might think that a few multiplications to get 50! or 100! will be executed in almost no time while on the other hand evaluating a Gamma-function may take some time. So I was quite astonished when I noticed this:

  • 100! and 101! take about one second. However, 100.5! (i.e. Gamma(101.5)) is returned about twice as fast in just half a second.
  • 150! takes roughly 1.5 seconds - but 200! appears almost instantly.
So the 35s obviously uses at least three different algorithms. If n! is evaluated directly by 1*2*3*...*n I wonder why it takes almost two seconds in 35s machine language to do 150 multiplications. A similar RPN-program finishes in six seconds. I would have expected the internal function to run at least 10x as fast as my hand-written code.


However, the more interesting part is the obvious switch between two different algorithms that seems to take place near x=158 since 158! is slow while 159! is much faster.


The 35s seems to use a different method for factorials and the Gamma-function - which sounds quite obvious. The Gamma-algorithms seems to be somewhat faster. Which leads to the question why the 35s doesn't use this faster method for factorials as well.



Maybe someone out there can shed some light on all this. Or at least we can speculate a bit about what's going on here. :-)



Dieter

Re: Factorials and the 35s - David Hayden - 10-20-2010

Quote:
However, the more interesting part is the obvious switch between two different algorithms that seems to take place near x=158 since 158! is slow while 159! is much faster.
I'm going to guess that there are actually two algorithms, one that multiplies integers and one that computes gamma. It uses the first algo for non-negative integers less than 159 and the second for all other numbers.

The slow processing speed may be due to the fact that it's doing BCD arithmetic, but I'm just speculating there. I don't know the details of the processor, but it does seem rather slow.

Continuing my speculation, when using the gamma function, they might convert the BCD number to binary and then compute gamma using binary arithmetic, which is usually much faster. When done, the would convert the result back. This might explain why gamma is pretty fast.

Dave

Re: Factorials and the 35s - Marcus von Cube, Germany - 10-21-2010

It's always a good idea to consult Viktor T. Toth's page about Gamma. The approximations are shorter then the repetitive multiplications but they are "only" approximations. It makes sense to use Gamma(x+1) instead of x! if the result has more nonzero leading digits than the maximum mantissa length of the calculator because above that the result can no longer be a non integer and thus approximation errors become less of a problem. I don't know why the 35s starts using Gamma instead of multiplication as late as 159!. 17! would be a better margin.

Edited: 21 Oct 2010, 5:31 p.m.