working with big numbers

[Bl0ckeduser]

I got bored after a minute of no output. Note that 100!
has nowhere near this number of digits. ....
I have a tentative rule not to allocate more than 256 bytes of
automatic storage if possible. ....
Since we only need a factorial, and since we only need decimal
output, here's a simple way of calculating in blocks of 4 digits
at a time. I'll leave it as an exercise to modify it to work on
numbers higher than 9999!

Thanks for critiquing my code and for writing a smarter version from
which I (and other noobs reading this) may learn. As a hobbyist, I
always appreciate advice from experts.

As for the exercise, I guess using a larger type for *f and increasing
the block size accordingly would work.

 

[Guest]

Good idea. I think a good dynamic allocation scheme
would save memory and allow my program to calculate larger
factorials much faster.

I don't see why. It's unlikely to save memory. In most implementations dynamically allocated objects take up slightly more space than auto objects. And dynamic memory to the best of my knowledge is rarely quicker.

But many implementations limit the size of the stack (where auto variables are usually allocated).

 

[Edwin van den Oetelaar]

Dear Friends,
i need to know how to calculate big numbers i.e. factorial of 100. i
google and found a solution but didn`t understand how it is done.and
some others solution is using some library .but i actually want to
develop a solution witch i understand. kindly give me some logic?
atleast i need to know how to start with.
thankx

Since the factorial of 100 is a constant, do not calculate it.
Use a lookup table for constants.
Best solution for speed, code and memory optimization.
Have a happy day,
Edwin

PS, spell check is broken?

 

[BartC]

Since the factorial of 100 is a constant, do not calculate it.
Use a lookup table for constants.

Please give an example for 100! in C. Then perhaps one for 10000! or
1000000!

See, it's not so easy! You first need to *know* what the answer is. It's
that step we're trying to do.

Also, we don't know exactly which factorial we want; it could be 100!, or it
could be 3531! We need a table of all factorials up to some arbitrary upper
limit.

Best solution for speed, code and memory optimization.

1000000! has over five million digits. Then you have all the factorials
below 1000000! And all the ones above that, up to our limit. I'm not sure
that's the most optimal way of using memory!

PS, spell check is broken?

(The spell-checker seems to be working fine.)

 

[Nobody]

But many implementations limit the size of the stack (where auto variables
are usually allocated).

Also, heap allocation failure is usually easier to catch than stack
allocation failure.

 

[Bl0ckeduser]

I don't see why. It's unlikely to save memory. In most implementations dynamically allocated objects take up slightly more space than auto objects. And dynamic memory to the best of my knowledge is rarely quicker.

The reason I thought that is that dynamically allocating only as much as
needed (or roughly as much) instead of allocating 1000000 as I did
originally would save memory if the factorial is not too big. And the
reason I thought it would be faster is that only allocating roughly as
many digits as needed prevents the program from wasting lots of time on
leading zeros in the case of smaller factorials (as it currently does).

Anyways thanks for the advice.

 

[Joe keane]

Also, heap allocation failure is usually easier to catch than stack
allocation failure.

If you are writing code that is supposed to be reliable, it's much
better. Check for no-mem, if so, clean up and report 'we're sorry, we
are unable to fulfill your request at this time'; or get SEGV...

well great now you screwed up the shared memory too

....

So this one time, some customer had a problem, they were running
thousands of threads and their requirements for stack were tight.

Then i found the problem:

int smash_page(PAGE *page)
{
PAGE tmppage;

...(page, tmppage)...

memcpy(page, &tmppage, sizeof PAGE);
}

Perfectly sensible, but when i switched it to use heap their problem
fixed itself. I confirmed that the run-time was negligible.

For multi-thread, heap memory needs as much memory as is needed at one
time, while stack memory needs as much memory as all of them will need
at some time.