posted 5 years ago

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.

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.

posted 5 years ago

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

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.Your constant enemy is yourself.

posted 5 years ago

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.

Dindy Oreeda wrote:

My suggestion is that you use java and thelongdata 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

posted 5 years ago

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

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

Regards,

Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)

Tim Moores

Saloon Keeper

Posts: 4036

94

posted 5 years ago

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 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.

Regards,

Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)

Tim Moores

Saloon Keeper

Posts: 4036

94

posted 5 years ago

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.

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.

posted 5 years ago

I agree. And Tim asked the important question here:

For the answer, I suggest looking through the API for classes that start with

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.SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 5 years ago

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

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

posted 5 years ago

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 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.

posted 5 years ago

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

Which of course leads to the third panel here. One of my all-time favorite comics moments.

http://xkcd.com/207/

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/

posted 5 years ago

No, it won’t. Java™ suffers an overflow error forDindy Oreeda wrote: . . . My suggestion is that you use java and thelongdata type. . . . I'm sure that accepts the huge huge numbers for your factorial. . . . Hope it helps.

*i*! where

*i*is >12 for an

`int`and >21 (I think) for a

`long`.

posted 5 years ago

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

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.

Using orders of magnitude

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.

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

posted 5 years ago

So, how did Prashant Mathur work out that figure?

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?

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.Prashant Mathur wrote: . . . It would be 8.2639316883 * 10^5,565,708 (approx) . . .

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?

posted 5 years ago

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.

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.

posted 5 years ago

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

As far as I know, to actually

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.

Campbell Ritchie wrote:So, how did Prashant Mathur work out that figure?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.Prashant Mathur wrote: . . . It would be 8.2639316883 * 10^5,565,708 (approx) . . .

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.

posted 5 years ago

- 1

Going slightly off-topic...

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

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."

posted 5 years ago

I thought it was 1e1000000 and 1e5000000.

D'OH! Where did I get that the number of

: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 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

posted 5 years ago

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

posted 5 years ago

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

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

Campbell Ritchie

Marshal

Posts: 56600

172