"FACT" ???



#16

I was playing around with my 12 yr old son while riding the Kinston Ferry. We did 40 "FACT", and stored the result.

Then we did it manually, 40x39x38x.......x2. When subtracting the two results we thought the answer should be "0," but it turned out to be -2.00.00000 38

I have repeated this with FACT 30 and the result is "0"

I wonder what is going on.

Karl
HP41CX


#17

You have chance ....

Because on my 32SII the difference is 4 E36

But I made a program rather than manually.

Fred


#18

What is strange .... is that for 29 there is a difference and not for 30 ..... Next step is a complete table of the difference for all the values from 2 to 69 for machine limited to 9.99999999 E99 and 253 for machine limited to 1.0000 E500.

By the way, what are the different range of our beloved calculators !!!!

My Program :

LBL A

STO A

STO B

LBL B

RCL A

1

-

x=0?

GTO C

STO A

x

GTO B

LBL C

RDN (roll down)

RCL B

x!

-

STOP


I promise my next version will only use the stack but I was in a hurry....

Fred


#19

It's funny to see that 18 is the first value which give a difference : 10000 for a result of 6,40237370573 E15 with FACT and 6,40237370574 E15 for the "manual" computation.

What is this "smallest special fact number" on different calculators. More seriously what are the different internal algorithm and internal calculus precision for the different CPU of our calculators ???

Fred


#20

One possibility: some machines (I know the 34C is one) use the Gamma function to calculate the factorial. This is an approximation method. You can read some good articles about it by Viktor Toth at www.rskey.org:

http://www.rskey.org/gamma.htm

http://www.rskey.org/calcsme.htm

If your calculator is using multiplication to calculate the factorial, another possibility is that the intermediate results are treated differently for internal functions than for the user-accessible multiply function, with regard to rounding and truncation. Remember that the calculator uses more digits than are displayed to help improve the accuracy of final results, also that once the number gets larger than the internal number of digits, the calculator has to begin using scientific notation, and some least significant digits are unavoidably lost. I just started reading a very interesting book that has at the beginning a chapter on the limitations of numerical calculations with computers. The book is "Numerical Methods for Scientists and Engineers", second edition, by R.W.Hamming (of the Hamming Code). It was originally published in 1973 and is available as a Dover paperback book, I got mine at a US bookstore chain called Bookstop which is now part of Barnes and Noble.

#21

I suspect that the Factorial function is handled with a look-up table, the values for which were derived on a machine with greater precision than the calculator. (Results for non-integer arguments are probably interpolated with some algorithm.)

Thus, error accumulates in sequential multiplication due to the relatively limited precision of the calculator, and after some point (between 30 & 40, no doubt) the results get large enough that that deviation from the look-up value is significant.

(Notice the difference has but one significant digit -- that implies the deviation is only in the last digit available in the calculator's internal base-10 representation.)

Anyway, that's what I SUSPECT is going on . . . (And I suspect that the function's pre-stored result is more accurate than a calculated one, for arguments > 30-something.)


#22

I note Fred's discovery that 18! is the first value returning a difference -- of "1" in the 12th digit. This leads one to suspect that the calculator's internal representation of real numbers is limited to 12 digits.


#23

Fred,

Sorry for the stupid question, but what are the "PGRM" keystrokes to:

STO A

Thanks,
Karl


#24

Hi, Karl;

it seems to me you are using an HP41, right? Almost all others use "!" for factorial. If so, you can change Fred's program to:

LBL A
STO 00
STO 01
LBL B
RCL 00
1
-
x=0?
GTO C
STO 00
*
GTO B
LBL C
RDN (roll down)
RCL 01
FACT (x!)
-
STOP
I think Fred used an HP32SII.
Hope it helps.

Cheers.


#25

Hi;

it's getting even better.

Try this simple program running in any HP41:

LBL"FAC"
1
X<>Y
ENTER^
LBL 00
ST* Z
DSE X
GTO 00
CLX
1 E3
/
1
+
1 (or LASTX)
LBL 01
RCL Y
INT
*
ISG Y
GTO 01
X<>Y
RDN
.END.
If you input any number from 1 to 69 it computes the sequential product (factorial) upwards (X-register), say, lower-to-upper, and downwards (Y-register), or upper-to-lower. As expected, results are different from each other after 24 FAC. When mantissa looses the first rightmost non-zero digit, everything else in not correct. And it happens with different values for each routine. And both results are different of the one obtained with 24 FACT.

Another thing: the difference that exists between the exponent of ten of both n FACT and the sequential product of n (n >23) is constant and its value is "9", one less of the number of significant digits (mantissa). Did anyone notice that?

Just a matter on numbers...

#26

I was using an HP32SII where storage is done in alphanumeric register (from A to Z plus i for indirection and the Sigma registers for statistics)

Fred

#27

Actually, the factorial function is only defined for integer arguments (maybe only positive integers?). The Gamma function is a generalization of the factorial for positive real numbers. See Viktor Toth's article:

http://www.rskey.org/gamma.htm

I don't think a calculator would use a lookup table for the factorial, because a program using multiplication is so short compared to the ROM space (always at a premium in a calculator) required for even just a few full precision constants. The 34C uses the Gamma function to provide the factorial function, but they fully document the Gamma function because it has important applications in statistics.


#28

Wellllllllll . . .

If I enter 5.15 on my HP-32S and hit Shift-<Prob> <x!> I get 155.311235965 . (Which is sorta like the Gamma function result, I'd guess?) Maybe the HP-32S factorial algorithm is actually the Gamma function? (I don't have a manual for the thing, so I don't know what HP says about this.)

5.15 and Shift-<PROB> <N!> on my HP-42S gives "INVALID DATA". On my TI-83+SE, similar problem ("Error -- DOMAIN" or some such).

On the HP-48G, it gives (exactly) the same result as was offered by the HP-32S.


#29

I don't know all implementations on all HP calcs, but I do
know how it's done on a 48/49. The rest is probably similar.
The factorial function for integer arguments is calculated with a simple loop - but it is executed with the internal 15-digit accuracy, so the rounded 12-digit result
is accurate. Doing it with 12-digit numbers in a user program inevitably introduces rounding errors for n>17
(17! still has only 12 significant digits, but 18! has 13),
and of course the rounding errors are different if your
order of operatios is different (1*2*3*.. vs. n*(n-1)*(n-2))

The factorial function for a non-integer argument x calculates gamma(x+1) using a rational approximation,
which is actually something that has bothered me from the
beginning: FACT (or '!') should accept only integers, and
to calculate GAMMA the function itself should have been provided - the way it was on a 42S. (the 49 provides GAMMA,
but of course FACT still accepts reals)

Werner Huysegoms


#30

Thank you, Ellis, for the info and insightful links on this subject.

I believe that Werner is on the mark regarding the algorithms.

On the 34C, 15C, and 32Sii, "x!" is a dual-use key, calculating factorial(x) for non-negative integer-valued x and gamma(x+1) for real x < 69.96 other than negative integers. (The 15C will ignore the imaginary part of complex x). On the 34C and 15C, x! takes much longer to execute for non-integer values of x than for integer-valued x, indicating use of different algorithms -- presumably using looped-multiplication for integer x and some estimating method for non-integer x. I suspect that the same is true of the 32Sii.

On the 42S, the algorithms are separated into the functions "n!" for n < 254 and "gam" for x < 254.12, which allows gamma(x) to be directly executed according to its definition without adjusting the input argument. Surprisingly, "gam" is almost instantaneous -- much faster than "n!" for n and x that are large and roughly equal. However, "gam" will execute (x-1)! instead if x is an integer.

On the 28C and 48G, one can execute factorial(x) or gamma(x+1) by entering x, keying in "FACT", then hitting <EVAL>. x < 253.12 for a *correct* answer (within range of 1E500) and x must not be a negative integer (or else, "infinite result" is the answer).

On the 41C-, however, any value of x other than a non-negative integer will give a "DATA ERROR" message, and I know of no HP Pac ROM that provides the gamma function.

Finally, the 17Bii provides only the n! function.

There you have it -- implementation of factorial and gamma for eight different machines. Who can explain the fast performance of gamma for the 42S?

-- Karl


#31

Hi Karl,
depending on the argument, the gamma function is approximated by a rational function, or a continuous fraction. The operations count to calculate GAMMA(250.1),
is only 5 div/mult and a logarithm and an exponential,
both of which take an additional (say) 8 multiplications.
FACT(250), on the other hand, takes 249 multiplications or more than 10 times more. Makes one wonder why large
factorials are not computed with ROUND(GAMMA(n)) or so.


#32

Never mind my last suggestion. GAMMA is one of the functions that is apparently not correct to 12 digits over its entire range (as SIN, COS etc are) , and ROUND(x) has little meaning if x >1.E12. eg FACT(100) - GAMMA(100) (calculated on a 48, using the GAMMA code itself) = -2.E146, meaning there's
an error of two units in the 12th position.


Possibly Related Threads...
Thread Author Replies Views Last Post
  SIGMA(N:0:100:1:FACT(N))-X speed test on the 17BII+ Bob Wang 0 155 06-04-2005, 04:43 PM
Last Post: bobwang

Forum Jump: