Click here to Skip to main content
15,035,685 members
Please Sign up or sign in to vote.
2.50/5 (2 votes)
See more:
1.) I develop a C# program to compute N! using integer type, but i need to convert it to unsigned integer type of array to store a N from 1 to 99,999,999. The function will compute N! and store into array with a maximum 4 digits per element.

2.) As you print the value in each element of array you will need to fill in leading zeros by printing character zeros if the digits in an element of the array (except for the beginning of the number) contains leading zeros.

3.) I need to find out what is biggest factorial number that your program can compute and how long to finished (time)? Size of array could change.

What I have tried:

C#
using System;

namespace BigFactorial
{
class Program
{
static int MAX = 5000;
//This is telling the program what to multiply.
private static void mult(int[] x, int n)
{
int y = 0, i, m;

for (i = 0; i < MAX; i++)
{
m = y + x[i] * n;
x[i] = m % 1000000;
y = m / 1000000;
}
}
//This is telling the program how to calculate factorial of n.
public static void Factorial(int[] a, int n)
{
a[0] = 1;
for (int i = n; i > 1; i--)
{
mult(a, i);
}
}
//This is displaing the factorial after the calculation.
public static void Display(int[] a)
{
int i;
for (i = MAX - 1; a[i] == 0; i--) ;

Console.Write(a[i]);
for (int j = i - 1, c = 1; j >= 0; j--, c++)
{
string s = "" + a[j];
Console.Write(s.PadLeft(6, '0'));
if (c % 10 == 0)
Console.WriteLine();
}
Console.WriteLine();
}
public static void Main(string[] args)
{
while (true)
{
//Telling user to enter a number.
Console.Write("Enter a number to factor or a negative number to quit: ");
int n = int.Parse(Console.ReadLine());
//Quit function
if (n < 0) break;
int[] arr = new int[MAX];
Factorial(arr, n);
Display(arr);
}

}
}
}
Posted
Updated 2-Feb-21 14:54pm
v2
Comments
PIEBALDconsult 2-Feb-21 14:19pm
   
Definitely homework and it sounds like your teacher has no understanding of the situation.
Why would there be an array?
The very mention of "maximum 4 digits per element" and "if the digits in an element of the array ... contains leading zeros" is nonsense -- unless you are storing the results as strings?

Quote:
I develop a C# program to compute N! using integer type, but i need to convert it to unsigned integer type of array to store a N from 1 to 99,999,999. The function will compute N! and store into array with a maximum 4 digits per element.

No, you can't.
Even as an unsigned integer occupying the full 32 bits (4 bytes) you cannot fit 9,999,999! into it. The maximum value you can fit into 32 bit (even unsigned) is 4,294,967,295, and 13! exceeds that: 6,227,020,800.
Even if you move to a 64 bit integer, you cannot fit even close to 99,999,999!: the larges an unsigned 64 bit integer can hold is 9,223,372,036,854,775,807 so 20! is the largest you can fit: 2,432,902,008,176,640,000

Bear in mind that factorial values grow an an exponential rate: it is unlikely that all the memory in all the computers on Earth would have enough memory to hold 99,999,999! at all.
   
Comments
Member 15062853 2-Feb-21 14:33pm
   
Besides the fact that the instructor has no idea what he is doing, is there a way to convert this over to uint??
OriginalGriff 2-Feb-21 14:42pm
   
What part of "it won't fit" do you have trouble with?
Luc Pattyn 2-Feb-21 21:00pm
   
Some kind of BigInteger scheme is being used, built as an array of ints where 4 (actually 6) digits of the big number are stored in each element. So it works like a base 10,000 (actually base 1,000,000) representation of integers with arbitrary range, assuming MAX is chosen appropriately.

:)
OriginalGriff 3-Feb-21 1:58am
   
I'm still not sure it's going to work: my calculator just laughs at me when I try to work out the number of digits involved:

logn(99999999!)

:D
CPallini 3-Feb-21 2:19am
   
I am quite confident it woudn't work, because you need (about) 10^800000000 to store 99999999!
Luc Pattyn 3-Feb-21 9:59am
   
Indeed 99,999,999! has some 756570548 decimal digits.
You could store it as a string, consuming 756MB (C) or 1512MB (C#) of memory; or as an int32 array with 6 digits per int, requiring some 500MB of memory.
I don't see a problem.

:)
Luc Pattyn 3-Feb-21 10:01am
   
I'm glad your calculator is happy.
BTW the logarithm of a product equals the sum of the logarithms of its factors.

:)
Hi,

there are a couple of things you could improve:

0. The intro said "maximum 4 digits per element" but your code stores and displays 6 digits per element (which is valid but inconsistent with the task description). You could make it a const in your code and expedriment with some values...

1. Rather than allocating the array in advance, I would do that inside the Factorial() method and return the array as the result.

2. I don't expect any int/uint conversion problems. When a numeric value can be represented in both of these types, an explicit cast suffices; without a cast, the compiler may issue some warnings. Also, you could try and do it all using uints only.

3. About MAX: for large values of N the value of N! gets approximated quite well by Stirlings formula; so you could use that formula inside Factorial() to dynamically calculate your array dimension. It would be wise to add say 3 for safety.

Beware, the Stirling formula as is obviously would yield a huge number, exceeding the range of a double or decimal. But then you don't need the value, you need the number of array elements, so a smart use of logarithms could avoid any issues. That requires you to rework the formula a bit!


:)
   
Comments
Richard Deeming 3-Feb-21 5:37am
   
Even using Stirling's formula to approximate 99999999! exceeds the limits of the double type. :)

In fact, using the double type, the highest non-infinite result from the Gamma function is for 171, giving:
170! ~= 7.25741561530811E+306
Luc Pattyn 3-Feb-21 10:05am
   
You don't need the value of 99999999! to determine how many digits it would have; all you need is its logarithm, say in base 10. And taking the logarithm of a product boils down to summing the logarithms of its factors, whether you apply it to the definition of factorial, or to the Stirling formula...

Something like this
public int calcNumDigits(int max) {
double numDigits = 0;
for (int i = 0; i < max; i++) {
numDigits += Math.Log10(i+1);
}
log("" + max + "! has " + numDigits + " digits");
return (int)Math.Ceiling(numDigits);
}
suffices to get to the result: 756570548 decimal digits.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900