Lina

Hello all...

How we can calculate and output the value of 500!. Namely, how one can deal with a huge values which does not fit to any known data types because of it limitation?

Thanks...

grumpy

If I was to do this in C (which I wouldn't: C++ is better for managing this sort of thing, IMHO), I would use some form of data structure that is able to represent the range of integers you want. For example, a structure of the form
can probably store up to MAX_INT*MAX_INT distinct integers (where MAX_INT is the maximum value that can be stored in an integer). If you write a set of helper functions that allow you to manipulate such structures (eg add them, subtract them, multiply them, print them, etc etc) your problem will be solved. To store 500! you will probably need a VERY large structure, so will probably resort to a dynamically allocated array of int's (or unsigned's) in your structure, and your manipulation function will need to make the array grow as required.

Aphex_Twin

500! fits on something like 137 kb. So you need to use more than two ints. I never handled such large factorials, but I did play around with multiplications of very large numbers (I got it up to 15000 decimal digits, probably could have gone MUCH further). What you need is a structure to represent large chunks of bits (preferably a memory mapped file) and a multiplication algorithm (try Karatsuba, FFT multiplication)...

The simplest way I can think of doing it is to do a recursive function to handle the factorials.

The recursive definition of the factorial is:
factorial(0) = 1
factorial(n+1) = factorial(n) * n+1

One thing to remember: multiplying two numbers of length a and b would get a result of size <= (a+b), so you don't have to use up all the memory from the beginning.

DaWei

Caveat: the recursive approach may use up your allotted stack before it uses up the memory you've alloted for the result. Most likely not for a factorial operation, though; the result grows rapidly, to indulge in an understatement.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Aphex_Twin

Recursion on a predefined chunk of memory with passing just a pointer at a time is basically cost-less in terms of stack space.

But yes, it can be done at about the same complexity level by iterative means.

DaWei

Well, perhaps I posted unclearly, but I thought it showed that I was speaking of recursion in general, and not as applied to the factorial problem. "Cost" is a relative term (as is "low"), but "costless" is quite absolute and inapplicable.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Ancient Dragon

This math library might help

stevengs

all y'all's (hehe) avatars look mighty peculiar! (mine is fine )

__________________
-Steven
"Is this a piece of your brain?" - Basil Fawlty

OpenLoop

I agree with DaWei. I had the same problem with a Hex-Dec converter where i used a recursive function to implement multiplication and I got a stack overflow error.

mackenga

I'd use an iterative approach (in C) and store the big integers in int-sized chunks in a singly linked list. You'd only need to implement a couple of operations on these big integers anyway; might as well not implement what you aren't going to use. I tackled a similar problem (well, it was huge Fibonacci numbers rather than factorials, but with the same large integer storage problems) in Ada a couple of years ago - a class assignment at Uni. I'd see if I could dig out the solution, but it'd probably not be very useful here.