Factorial of any length

[Asif_NSU]

i have this assignment to compute the factorial of an integer of any length. I have done it using array of char and then overloading the * operator accordingly. It works fine but i wanted to know if there were other efficient algorithms for counting factorials of any length. Give me some links if u find some. My search in google did not return anything exciting. If urs does then plz give me the links.

[Asif_NSU]

This is a snippet i got from the one of the sites:

#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
	unsigned int d;//number of digits
	unsigned char *a;
	unsigned int j, n, q, z, t;
        int i;
        double p;
    
    cout << "\nEnter the No: ";
    cin >> n;
    
    p = 0.0; //calculate the number of digits required
    for(j = 2; j <= n; j++)
    	p += log10(j);
    	
    d = (int)p + 1;
    a = new unsigned char[d];
    
    if (!a)
    {
		cout << "Could not allocate memory!!!";
		exit(0);
    }
    
    for (i = 1; i < d; i++)
    	a[i] = 0; //initialize
    a[0] = 1;
    
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
		q = 0;//initialize remainder to be 0
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
	        t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }
    }
    
    cout << "\nThe Factorial is: ";
    // the fact is stored in reverse..
    for( i = d -1; i >= 0; i--)
    	cout << (int)a[i];
    	
    delete []a;
    	
    return 0;
    
}

But the problem is i dont understand what its doin and why, especially here:

for(j = 2; j <= n; j++)
    p += log10(j);

I guess its counting the number of digits required to hold the factorial, but where did this formula come from?

And MOST importantly whats goin on in here:

for (i = 1; i < d; i++)
    	a[i] = 0; //initialize
    a[0] = 1;
    
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
		q = 0;//initialize remainder to be 0
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
	        t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }
    }

Could anyone explain me whats goin on inside the loop?

[varunrathi]

Can u please, post ur solution
If u can`t post the soln. then can u please explain how to find the factorial of a number of any length.

[jwenting]

That's the problem when you pull code from some website or book and submit it as your own... You learn nothing from it.
Learn to make your own code, learn to understand the code of others.

[Asif_NSU]

okay in my own solutions i defined a class named BigInt. The class could hold an integer of any length, and the operator + was overloaded for that class so that two BigInt could be added. I did this assignment a semester ago. So when i was asked to find factorials of any length i just new that the basic problem is to do multiplication like this:
72172817218122121 x 7812

But i could do additions of numbers like this 7128712821812+1282817281718 with my BigInt. And because multiplication is just repeated addition i overloaded the * operator and defined multiplication for my BigInt class. That's how i solved the factorial of any length problem.

But implementing multiplication with repeated addintion is an exponential process and it gets slower for larger values exponentially. THATS WHY I was trying to know if there were other efficient methods and the code i posted here was a result of my first attempt to find a solution made by others.

And i really did not stop there. I did some further studies on the topic and came to know that the problem of finding factorials of arbitrary length is just a instance of not having an arbitrary-precision-arithmetic. So if i could implement a arbitrary-precision-arithmetic i could find factorials of any length and could do more.

First thing i learned when trying to implement APA is that i should convert the input(say the integer) into a number of higher base. The base should be the square root of the largest integer that can be handled by the machine. So then i will need less memory and most importantly number of digits to add or multiply would be significantly fewer.

The next thing i learned about implementing multiplication is that "i should avoid doing multiplication by repeated addition" since its an O(n^2). Then i could do multiplication like the way we multiply in our real life. Well that was sufficient for me. But i also came to know that this multiplication can be implemented with even faster algorithms namely

1. Karatsuba's divide-and-conquer algorithm
2. Fourier transforms
3. Chinese remainder theorem and modular arithmetic.

I possess little or no knowledge on this three process. So i guess thats as far as i could go.

And one more thing... i tried to convert the input into a number of higher base. I can do this by simple division and remainder process that we all know. But that works for normal integers. But while working wit big sized integers i have to convert the input and put that digit by digit into an array of characters. But then i cannot divide the whole number --bcos there is no number and only discrete digits. Can anyone suggest how can i convert an integer of any length into a higher base.

Thank u.

[Asif_NSU]

learn to understand the code of others.

I did try and now i know that

for(j = 2; j <= n; j++)
      p += log10(j);

this piece of code calculates the number of digits required to hold the factorial of that number. Suppose i have a decimal number 100, then the number of digits required to hold 100 in decimal system is log10(100) + 1.
Same is true for number of any base.

for (i = 1; i < d; i++)
      a[i] = 0; //initialize 
a[0] = 1;
p = 0.0;
for (j = 2; j <= n; j++)
 {
  q = 0;//initialize remainder to be 0
  p += log10(j); 
  z = (int)p + 1; 
  for (i = 0; i <= z/*NUMDIGITS*/; i++)
   {
          t = (a[i] * j) + q; 
             q = (t / 10);
              a[i] = (char)(t % 10);  
   }      
}

And this part multiplies the contents in the array first with 2 and then puts the result into the array. Then goes to the next number 3 and multiplies content of the array with 3 and then to the next number and so on. Thus if we have 5 as input it calculates 1*2->2*3 ->6*4->24*5->120 and thus we get the factorial.

The assignment was given just two days before the submission date and i had no time to study further and learn more. Even though i now understand what the code does , i did not know what it was doin at the time i posted it and asked for help. I m new to prgramming and have only learned the syntax of C and C++ and that is also not exhaustive. I did not have the oppurtunity to play with different algorihtmic tricks involved in programming. Therefore, i face a hard time devising my own algorithms to mathematical problems and also to learn from others code, simply bcos i am not familiar with different mathematical tricks involved in the code. I hoped i could overcome it by asking help from people who already know about them and that would shorten my learning curve.

[vegaseat]

Here is the way I figured it out:

Let's say 5! = 1 * 2 * 3 * 4 * 5
the 1 drops out then 5! = 2 * 3 * 4 * 5
apply the log operator log(5!) = log(2) + log(3) + log(4) + log(5)

for(j = 2; j <= n; j++)
p += log10(j);

p is just log10(n!), by the way you could use exp10(p) to get an approximation of n!

then build up a numeric string using an array of characters with 2 nested for loops, the size of the array is p + 1

the way the nested for loops work the numeric string is in reverse, so spell it from the back

[varunrathi]

how to define a class which can "hold an integer of any length". my problem is that i am unable to define an integer of any length".

[1o0oBhP]

NO-ONE has used the simple loop method! im not sure how it compares but the posted snippet a while back certainly seems overkill for a simple factorial function.

Heres my code:

long Factorial (int base) // Factorial(4) = 4!
{
long result = (long)base;
for(int i = base - 1; i > 1; i--) // i > 1 avoids x 0 error if i = 0
{
result *= (long)i;
}
return result;
}

someone please tell me how to display my code properly as my posts arent looking as they should! :S

if you want a string then log10 the result, add 2 (string has '0' char at end) and divide by 1 then 10 then 100 ect, in powers of 10 to get digits and add to string.... im not sure where (or if) the log10 function is or exactly how to build the string, but im sure someone else could do it on this forum...

[BountyX]

That's the problem when you pull code from some website or book and submit it as your own... You learn nothing from it.
Learn to make your own code, learn to understand the code of others.

Copy Paste Find Replace! Hahah stay away from that philosphy and you will do alright.

[vegaseat]

NO-ONE has used the simple loop method! im not sure how it compares but the posted snippet a while back certainly seems overkill for a simple factorial function.

Heres my code:

long Factorial (int base) // Factorial(4) = 4!
{
    long result = (long)base;
    for(int i = base - 1; i > 1; i--) // i > 1 avoids x 0 error if i = 0
    {
        result *= (long)i;
    }
    return result;
}

someone please tell me how to display my code properly as my posts arent looking as they should! :S

if you want a string then log10 the result, add 2 (string has '0' char at end) and divide by 1 then 10 then 100 ect, in powers of 10 to get digits and add to string.... im not sure where (or if) the log10 function is or exactly how to build the string, but im sure someone else could do it on this forum...

There is a problem using simple multiplication of long integers, they don't even cover 1% of GWs annual deficit. You would run out of meaningful digits after the factorial of 12. The factorial of 13 is already past 6 billion.

[1o0oBhP]

point taken, im not sure exactly what is being asked of here? i just coded a factorial function and thats what i have used before... for larger numbers there is nothing stopping anyone making a scientific number data structure. i have found that particularly useful for physics simulation programs :)

[vegaseat]

point taken, im not sure exactly what is being asked of here? i just coded a factorial function and thats what i have used before... for larger numbers there is nothing stopping anyone making a scientific number data structure. i have found that particularly useful for physics simulation programs :)

by the way, to pretty up your code, enclose it with
code
/code
you have to use [] around code and /code.
I can't use them now or they won't show up.

just like this!!!!!!!

Read the article "Please use BB Code tags"
If you use the
php
/php
pair you get some color highlighting in your code. Same deal with the [] though!

[alc6379]

by the way, to pretty up your code, enclose it with at least 4 space indention.

More specifically, the block look like this:

code goes here

[Asif_NSU]

how to define a class which can "hold an integer of any length". my problem is that i am unable to define an integer of any length".

u can hold an integer of any length the way u can hold a string of any size.

[1o0oBhP]

thanks for the tag info !

[varunrathi]

i was able to write the code for a factorial of upto 8000, but after that it`s not working b`cos the array i`m using to store the factorial can`t have more than 30000 elments. is there any other way to store more number of digits.

[Dave Sinkula]

i was able to write the code for a factorial of upto 8000, but after that it`s not working b`cos the array i`m using to store the factorial can`t have more than 30000 elments. is there any other way to store more number of digits.

It the array currently statically allocated? If so, you might want to try dynamic allocation.

[roxanne_gem07]

Whoop.. I think i need to study a little bit harder.. This site really helps me a lot.. Thanks guys..