• Post Reply Bookmark Topic Watch Topic
  • New Topic

factorial of huge huge numbers  RSS feed

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Please tell.
 
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4036
94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Which Java data type can hold a number that large?
 
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).

In the end, even I'm really curious about this - how it can be achieved
 
Tim Moores
Saloon Keeper
Posts: 4036
94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4036
94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Never mind. Anyway, it is not adding anything helpful towards the solution, so let's focus on main issue
 
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Going slightly off-topic...

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

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


 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!