Factorials and the 35s



#4

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

#5

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


#6

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  New Blog: Factorials Eddie W. Shore 6 537 10-21-2012, 11:27 AM
Last Post: Eddie W. Shore
  Factorials on the Free42 Timespace 8 497 09-27-2006, 09:50 PM
Last Post: Karl Schneider
  The pace of progress - exact factorials and the past! Gene 15 783 04-30-2005, 04:05 AM
Last Post: .
  Factorials of Large Numbers Gordon Dyer 2 248 12-07-2002, 12:43 PM
Last Post: Gordon Dyer

Forum Jump: