deal with big numbers..

[cse.avinash]

Can any one help me to know how to deal with big numbers, like to count the number of digits in factorial of 5*10^9.
or how to make number 20,000 decimal.
array can store only to 10^6, if heap is taken the size could extend up to 10^9.How to deal with numbers having more than that size.
eagerly waiting for reply.

[Adak]

There are two ways:

1) Use a big number library. GNU's is well known.

2) Use an int or char array. Make each element hold just one digit of the number. Write a function for each operation you want done. Yes, you might want a matching array, just to hold the carry value.

You need to remember how arithmetic was done, before calculators! ;)

[cse.avinash]

1)How to use big number library..can you help me with some examples..

2)How to count the number of digits in factorial of 5*(10^9). using int array.

[Adak]

1) No, when I was working with big numbers, I had to "roll my own" handler for very large digits. GNU wasn't well known then (no www, and no internet for me).

2) Since 10 ^ 9 has 10 digits, and since 10 has only 1 one in it, 5 * (10^9) will also have 10 digits in it:

eg.
10 ^3 = 1,000 has 4 digits, and 5*(10^3) = 5,000
10 ^6 = 1,000,000 has 7 digits, and 5*(10^6) = 5,000,000

See the pattern?

A word about GNU:
They helped create Linux, which is more properly called GNU/Linux as a matter of fact. They have a religious conviction of the highest order, that anything worth saying, is worth saying in 10,000 words, while elucidating the complete specification of all 8.7 Billion species on planet Earth, and any other planets they're thinking of, atm.

I'd love to kick them one time in the arse, and ask them "Why can't you get to the effing point? But it would do no good - they'd just explain it in a 10,000 word speech, while elucidating the complete specifications of all 8.7 Billion species on ...

;)

[cse.avinash]

1)Okay I am understanding, but I am new to C and searching in google results in GMP library which is a library, they dont include functions or pdfs from which I can learn.

2)100 consists of 3 digits but factorial(100)is of 158 digits.
lly 1000 is of 4 digits but factorial(1000) is of 2568 digits.
in the same way what is the number of digits in factorial(5*(10^9)).

[Adak]

Yes, I missed the factorial mention. Ooops!

I'm not a mathematician. If there is a trick to answering this, I don't know it. I would have to calculate it out.

You might want to look at this website:
http://www.edepot.com/win95.html

It's a shareware big number program. I don't know if it can possibly calculate your range of integers though. That's a HUGE number. This quote on Wikipedia, was interesting - perhaps the factorial number could be estimated?

The calculation of factorials can easily produce very large numbers. This is not a problem for their usage in many formulae (such as Taylor series) because they appear along with other terms, so that—given careful attention to the order of evaluation—intermediate calculation values are not troublesome. If approximate values of factorial numbers are desired, Stirling's approximation gives good results using floating-point arithmetic. The largest representable value for a fixed-size integer variable may be exceeded even for relatively small arguments (see the table below). Even floating-point approximations can exceed the maximum representable floating-point value.

It may help to recast the calculations in terms of the logarithm of the number. But if exact values for large factorials are desired, then special software is required, as in the pseudocode that follows, which implements the classic algorithm to calculate 1, 1×2, 1×2×3, 1×2×3×4, etc. the successive factorial numbers.

I can't help you with GMP, because I've never used it. Go to their website, and follow the instructions for your OS and compiler. Be prepared for the 10,000 word essay on every species on the planet, as well.

I'm a bit unclear what the problem is here. Are you supposed to code up an answer to this, use a big number library like GMP, or just get the answer, any way at all?

[cse.avinash]

I just want to know to how to count the numbers in such a big factorial,My code is counting digits upto fatorial(10^5),but digits in factorial(10^9)is huge.

Here is my code:--

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
	int a[100000000] = {0};
int m,temp, x;
void fact(int n)
{
	m = 1;
	a[0] = 1;
	temp = 0;
	x = 0 ;
	int i = 0;
	while( n > 1 )
	{
		temp = 0;
		x = 0;
		for ( i = 0 ; i < m ; i++)
		{
			x = ( a[i] * n ) + temp;
			a[i] = x % 10;
			temp = x / 10;
		}
    	while( temp > 0)
		{
			a[m++] = temp % 10;
			temp /= 10;
		}
		n--;
	}
	printf("%d",m);	
	printf("\n");
}
int main(){
	int num =0 ;
		scanf("%d",&num);
		fact(num);
getch();
	return 0;
}

[Adak]

What's your plan of attack here?

You can calculate this by adding all the exponents that are part of the numbers you want to multiply (10^9) * (10^9) = 10^18. That is one of the laws of exponents.

Carry out those additions, and that will tell you how many zeroes the final value would have.

As far as calculating it yourself:

Your array size is way too small, to me. Also, you'll probably need to change the data type of char, to save memory**. Char's can be printed out like "little numbers", if you use %d or %i format, and can be added, subtracted, multiplied, etc. Just remember their small range (127 signed char or 255 for unsigned char).

** static arrays are limited in size in C, because the stack that provides the memory, is a small subset of total memory. Use dynamic memory allocation to get memory from the much larger heap for huge arrays. (malloc or calloc). I suggest calloc() because it can set the value of all the array elements, to zero for you.

[N1GHTS]

You need to create a program to perform this:

The number of digits in the positive integer x is exactly

log(x) + 1,

rounded down, where the log is base 10, or you could write

ln(x)/ln(10) + 1,

rounded down. (Of course, if x is not a perfect power of 10, then this is the same as log(x) rounded up.)

Next all you need is a good enough approximation that rounding off gives you the right answer. For that, you can use Stirling's Theorem,

Stirling's Approximation
http://mathforum.org/library/drmath/view/55996.html

Take the log of both the upper and the lower bounds, add 1, and round both down to the nearest integer. If you get the same number on both sides (which you will almost every time), then that's your answer.

Source: http://mathforum.org/library/drmath/view/68245.html

You must use the power of mathematics to get the right answer without doing all the work, because it would take a computer years to calculate massive factorials in a recursive loop. Armed with a good algorithm, you need to imitate that formula in large binary arrays, preferably dynamic using realloc() or write to a file.

If you do this work without using 3rd party libraries, it would probably be more efficient to write this code straight into Assembly language as you can save a few precious clock cycles in some of the complex recursive loops.

[TrustyTony]

Sum of logarithms looks more attractive, but to 10**9 takes still time. I did timed loop in my favorite language and it took 7.198 s to calculate value 65657060 for 10**7 and that is still two decades down. Result was accurate at least for 10**5 (456574), which is OK to calculate as normal big integer number and see string length directly.

Better way though is to use sterlings formula for logarithm of factorial:
http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-factorial/

I get 8565705523.0 (in 0.013 s) for 10**9 so the correct number could be one more or that exactly that.