Help coderanch get a
new server
by contributing to the fundraiser
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# factorial of huge huge numbers

Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
Next Problem of mine..

Need to calculate factorial of huge huge numbers suppose 10,00,000 (10^6) ...how it could be done either in C language or java ....because I tried different data types in C , I couldn't reach to the output which contains that many digits.
Even tried with atoi methods in C but after a certain limit that also fails..tell me.

Marshal
Posts: 28271
95
• Number of slices to send:
Optional 'thank-you' note:
Here's a calculation for you to do before you start: How many digits will there be in the factorial of 10^6?

You don't need to produce a precise value for this, just a rough estimate.

Greenhorn
Posts: 5
• Number of slices to send:
Optional 'thank-you' note:
So, you're talking about a data type that hold that long of value so that it doesn't fail. Am I right?

My suggestion is that you use java and the long data type. That is under the int category which means that it accepts/takes whole number only. I'm sure that accepts the huge huge numbers for your factorial. Try to search about it. Hope it helps.

Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Dindy Oreeda wrote:
My suggestion is that you use java and the long data type. That is under the int category which means that it accepts/takes whole number only. I'm sure that accepts the huge huge numbers for your factorial.

Before you post advice like this you should confirm that it's valid. The long data type is nowhere near large enough to hold what the OP is talking about.

Prashant Mathur
Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:Here's a calculation for you to do before you start: How many digits will there be in the factorial of 10^6?.

It would be 8.2639316883 * 10^5,565,708 (approx)

Now tell what next ??

Saloon Keeper
Posts: 7618
177
• Number of slices to send:
Optional 'thank-you' note:
Which Java data type can hold a number that large?

Bartender
Posts: 1558
5
• Number of slices to send:
Optional 'thank-you' note:
Well, I really don't know the solution to this, but I'm quite curious about:

1) What kind of application is this (which requires operations with 5.5 million digit numerical data)? Even in astronomy (from where the word 'astronomically large' came), the numbers which are few hundred digits long, are considered as 'huge'.
2) I do not think if conventional programming languages would be able to do this stuff (or at least, it would be very difficult).
3) Have you given a thought on what kind of hardware would be required to do such calculation (I mean both - processor and memory). Such calculation becomes exponentially processor and memory hungry with each exceeding number. e.g. while calculating factorial of 10, memory and processing power required to calculate 7!*8*9*10 is much more than that required to calculate 7!.
4) Besides everything, is this really necessary? There can be some different approach for solution (I don't know what application/code we are talking here about).

Tim Moores
Saloon Keeper
Posts: 7618
177
• Number of slices to send:
Optional 'thank-you' note:

Anayonkar Shivalkar wrote:while calculating factorial of 10, memory and processing power required to calculate 7!*8*9*10 is much more than that required to calculate 7!.

No. 7! = 5040 whereas 8!= 40320 - calculating that does not use 8 times as much memory or CPU power.

Anayonkar Shivalkar
Bartender
Posts: 1558
5
• Number of slices to send:
Optional 'thank-you' note:

Tim Moores wrote:calculating that does not use 8 times as much memory or CPU power

I agree.

I was talking about processing power required to calculate 7! and 10!.

My point was - calculating 10! does not require 2 times more processing power and memory than calculating 15!. 10! requires much more than that.

Tim Moores
Saloon Keeper
Posts: 7618
177
• Number of slices to send:
Optional 'thank-you' note:
I merely used as 8! as an example. Calculating 10!, too, does not require much more RAM or CPU power than calculating 7!.

Not sure what your comparison of 10! and 15! is supposed to show, or why you think calculating 15! would use less resources than calculating 10! - of course it uses more.

Anayonkar Shivalkar
Bartender
Posts: 1558
5
• Number of slices to send:
Optional 'thank-you' note:
Never mind. Anyway, it is not adding anything helpful towards the solution, so let's focus on main issue

Sheriff
Posts: 22792
131
• Number of slices to send:
Optional 'thank-you' note:
I agree. And Tim asked the important question here:

Tim Moores wrote:Which Java data type can hold a number that large?

For the answer, I suggest looking through the API for classes that start with Big. There are only two, so the choice shouldn't be too hard.

Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

Prashant Mathur wrote:

Paul Clapham wrote:Here's a calculation for you to do before you start: How many digits will there be in the factorial of 10^6?.

It would be 8.2639316883 * 10^5,565,708 (approx)

Now tell what next ??

Assuming this is true (and I do think it is), I'd like to point out this number exceeds the number of atoms in the known universe by many, many orders of magnitude. So whatever type you'd use to compute this factorial, it cannot fit in memory of any existing computer. Even if we disregard this obstacle, it would probably take more time to compute the result than is the age of universe unless you'd employ some really sophisticated mathematical trick(s).

However, I might be able to exactly compute the last few thousands of digits of the resulting number, should you be interested

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Martin Vajsar wrote:

Prashant Mathur wrote:

Paul Clapham wrote:Here's a calculation for you to do before you start: How many digits will there be in the factorial of 10^6?.

It would be 8.2639316883 * 10^5,565,708 (approx)

Now tell what next ??

Assuming this is true (and I do think it is), I'd like to point out this number exceeds the number of atoms in the known universe by many, many orders of magnitude. So whatever type you'd use to compute this factorial, it cannot fit in memory of any existing computer.

We can very easily store this number in a modest amount of memory. It's a 5-million-digit number. Even at 1 byte per digit (rather wasteful) that's only 5 MB.

Actually calculating it, well, that I don't know about.

Martin Vashko
Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:
Aehm. I somehow happened to assume the 10^5,565,708 is the number of digits. I shouldn't have read that article about Ackermann function yesterday, I think.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Martin Vajsar wrote:Aehm. I somehow happened to assume the 10^5,565,708 is the number of digits. I shouldn't have read that article about Ackermann function yesterday, I think.

Questions like this always get me thinking of Graham's number. It's the 64th term in a sequence, where the terms can be expressed as "Knuth up-arrow towers" (a notation for expressing unimaginably large numbers) even the number of towers in the first term is "far greater than the number of Planck volumes (roughly 10185 of them) into which one can imagine subdividing the observable universe."

Which of course leads to the third panel here. One of my all-time favorite comics moments.
http://xkcd.com/207/

Marshal
Posts: 79549
380
• Number of slices to send:
Optional 'thank-you' note:

Dindy Oreeda wrote: . . . My suggestion is that you use java and the long data type. . . . I'm sure that accepts the huge huge numbers for your factorial. . . . Hope it helps.

No, it won’t. Java™ suffers an overflow error for i! where i is >12 for an int and >21 (I think) for a long.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Prashant Mathur wrote:Need to calculate factorial of huge huge numbers suppose 10,00,000 (10^6)

Jeff Verdegan wrote:We can very easily store this number in a modest amount of memory. It's a 5-million-digit number. Even at 1 byte per digit (rather wasteful) that's only 5 MB.

Actually calculating it, well, that I don't know about.

Here's a little mental exercise though, that we can use to see just how unrealistic it is to try to perform such a calculation.

Let's pretend we're just counting up to that 1,000,000 digit number. This is obviously much simpler and faster than computing the factorial, since computing the factorial is basically counting plus a multiplication step each time we count up to the next number.

Furthermore, let's assume that we have really awesome hardware and a new, special version of Java, with wide enough word and bus widths in the hardware and a corresponding Java primitive so that we can hold our million-digit number in a primitive, and let's also assume that incrementing it takes 1 clock cycle, and that this hardware runs at 10 GHz.

Now let's assume that this counting problem can be done in parallel, and we've given every person on earth one of these computers.

We now have 7e9 computers, each counting at a rate of 1e10 steps per second, for a net operational throughput of 7e19 steps per second. Let's round that up to 10e19, which is 1e20, just to simplify the calculations a bit.

So, at 1e20 steps per second, to count up to a 20-digit number will take 1 second; to count up to a 21-digit number will take 10 seconds; to count up to a 22-digit number will take 100-seconds, and so on. So, in general, to count up to an N-digit number will take 1e(N-20) seconds.

30 digits: 1e10 seconds. About 317 years.

100 digits: 1e80 seconds. About 3,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years. Or about 200,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 times the current age of the universe.

IN OTHER WORDS...
Using orders of magnitude more computing power than exists in the world today, even simply counting to a number that is many orders of magnitude smaller than our target number would take such a ridiculously long time that it's not even worth considering.

But you don't want to just count. You want to do something more complex.
And you have less than 1/1,000,000,000th the computing power available to you than in this scenario.
And you don't want to stop at a number that will take you an unimaginably large number of universe lifetimes to reach. You want to keep going unimaginably further than that.

So, no, you won't be calculating the factorial of a million-digit number.

Estimating it, on the other hand, may be feasible.

Campbell Ritchie
Marshal
Posts: 79549
380
• Number of slices to send:
Optional 'thank-you' note:
So, how did Prashant Mathur work out that figure?

Prashant Mathur wrote: . . . It would be 8.2639316883 * 10^5,565,708 (approx) . . .

At least I can work out the rightmost 100000 figures really quickly (assuming you are using decimal arithmetic). Probably using the same technique Martin Vajsar did.

Now, you are counting up to 1000000, and doing arithmetic on a 5000000 digit number. Multiplying such numbers is going to take 5000000 clock cycles, and you do that 1000000 times, so you are looking at quadratic complexity, something in the region of 2,500,000,000,000 clock cycles. Are you sure you are going to take several eternities, Jeff, rather than a few hours?

Martin Vashko
Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:At least I can work out the rightmost 100000 figures really quickly (assuming you are using decimal arithmetic). Probably using the same technique Martin Vajsar did.

I've already embarrassed myself in this thread, so why not try again?

I say that few thousand rightmost figures can be easily calculated in virtually any positional notation, using the exact same technique.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:So, how did Prashant Mathur work out that figure?

Prashant Mathur wrote: . . . It would be 8.2639316883 * 10^5,565,708 (approx) . . .

At least I can work out the rightmost 100000 figures really quickly (assuming you are using decimal arithmetic). Probably using the same technique Martin Vajsar did.

Now, you are counting up to 1000000, and doing arithmetic on a 5000000 digit number. Multiplying such numbers is going to take 5000000 clock cycles, and you do that 1000000 times, so you are looking at quadratic complexity, something in the region of 2,500,000,000,000 clock cycles. Are you sure you are going to take several eternities, Jeff, rather than a few hours?

Unless my one core assumption is wrong, yes, I'm sure. I think.

As far as I know, to actually compute the exact factorial of a number, the only way to do it is to actually do all the multiplications. If I'm wrong about this, then the rest of my calculations are bogus.

The OP wants the factorial value of a million-digit number. I took his term "compute" literally. Doing 1e1,000,000 multiplications will certainly take longer than counting to 1e1,000,000, so unless there's some other way to compute (not estimate) the factorial, then yeah, forever.

Or am I missing something?

[EDIT] Yes, yes I am. I missed the fact that the OP wants to calculate the factorial of 1,000,000, not that of 10^1,000,000.

Java Cowboy
Posts: 16084
88
• 1
• Number of slices to send:
Optional 'thank-you' note:
Going slightly off-topic...

Jeff Verdegan wrote:Questions like this always get me thinking of Graham's number.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:
Now, you are counting up to 1000000, and doing arithmetic on a 5000000 digit number.

I thought it was 1e1000000 and 1e5000000.

D'OH! Where did I get that the number of digits in the input was 1e6, rather than the input itself being 1e6.

:confused:

I'm an idiot.

Calculating the factorial of a 1,000,000 digit number is impossible.

Calculating the factorial of 1,000,000 takes under a minute on my laptop.

Campbell Ritchie
Marshal
Posts: 79549
380
• Number of slices to send:
Optional 'thank-you' note:
The number of rightmost digits which are the same depends on the number of factors in the factorial which have 5 as a prime factor, in decimal arithmetic. Up to 1000000, there are 200000 multiples of 5, 40000 multiples of 25, 8000 multiples of 125, 1600 multiples of 625, 320 multiples of 3125, 64 multiples of 15625, 12.8 multiples of 78125 and 2.56 multiples of 390625. Add those up and we find that 1000000! ends with 5, 249998 times.

Campbell Ritchie
Marshal
Posts: 79549
380
• Number of slices to send:
Optional 'thank-you' note:

Jeff Verdegan wrote: . . . Calculating the factorial of 1,000,000 takes under a minute on my laptop.

. . . and how long did it take to read the output?

Martin Vashko
Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:... Add those up and we find that 1000000! ends with 5, 249998 times.

A small typo here: it ends with a string of 0 (zeroes), not 5.

Campbell Ritchie
Marshal
Posts: 79549
380
• 1
• Number of slices to send:
Optional 'thank-you' note:

Jesper de Jong wrote: . . . "If you actually tried to picture Graham's Number in your head, then your head would collapse to form a black hole." . . .

No, that’s the Greek budget deficit. And Jurre Hermans will tell you, your head would collapse into a slice of pizza.

Campbell Ritchie
Marshal
Posts: 79549
380
• Number of slices to send:
Optional 'thank-you' note:

Martin Vajsar wrote: . . . A small typo here: . . . .

No, I am missing the April Fool thread we usually have here

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Jeff Verdegan wrote: . . . Calculating the factorial of 1,000,000 takes under a minute on my laptop.

. . . and how long did it take to read the output?

A few seconds, since I my output didn't include the result of the factorial.

 Create symphonies in seed and soil. For this tiny ad: We need your help - Coderanch server fundraiser https://coderanch.com/t/782867/Coderanch-server-fundraiser