Computing Factorials of a huge number in C/C++: A tutorial

tutorial
, , ,
21

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BigMultiplier
{
class Program
{

    static void Main(string[] args)
    {
        int[] s1 = new int[1];
        int[] s2 = new int[1];

        s1[0]=1;
        Program p = new Program();

        int[] s3 = p.doit(s1, s2);
        Console.WriteLine("Enter the Number for Which Factorial to be Found (below 1000)");
        int limit = Convert.ToInt32(Console.ReadLine());


        for (int i = 1; i <= limit; i++)
        {
            s3 = p.return_array(i);
            s1 = p.doit(s1, s3);
        }
        int sum = 0;
        for (int j = s1.Length-1; j >=0; j--)
        {
            Console.Write(s1[j]);
            sum = sum + s1[j];
        }
        Console.Write("sum = "+sum);
        Console.WriteLine();
        Console.ReadLine();          
    }

    int[] return_array(int num)
    {
        int[] num_arr = new int[1]; ;

        if (num <= 9)
        {
            num_arr = new int[1];
            num_arr[0] = num;
        }
        else if (num <= 99)
        {
            num_arr = new int[2];
            num_arr[1] = num % 10;
            num = num / 10;
            num_arr[0] = num;
        }
        else if (num <= 999)
        {
            num_arr = new int[3];
            num_arr[2] = num % 10;
            num = num / 10;
            num_arr[1] = num % 10;
            num = num / 10;
            num_arr[0] = num % 10;
        }
        else if (num <= 9999)
        {
            num_arr = new int[4];
            num_arr[3] = num % 10;
            num = num / 10;
            num_arr[2] = num % 10;
            num = num / 10;
            num_arr[1] = num % 10;
            num = num / 10;
            num_arr[0] = num % 10;
        }
        else if (num <= 99999)
        {
            num_arr = new int[5];
            num_arr[4] = num % 10;
            num = num / 10;
            num_arr[3] = num % 10;
            num = num / 10;
            num_arr[2] = num % 10;
            num = num / 10;
            num_arr[1] = num % 10;
            num = num / 10;
            num_arr[0] = num % 10;
        }
        return num_arr;
    }


    int[] doit(int[] num1_int, int[] num2_int)
    {

// String num1_string, num2_string;
// Console.WriteLine(“Enter the Number 1”);
// num1_string = Console.ReadLine();
// Console.WriteLine(“Enter the Number 2”);
// num2_string = Console.ReadLine();

// int[] num1_int = new int[num1_string.Length];
// int[] num2_int = new int[num2_string.Length];

// for (int j = 0; j < num1_string.Length; j++)
// {
// num1_int[j] = num1_string[j]-48;
// Console.Write(" " + num1_int[j]);
// }

// for(int j=0;j<num2_string.Length;j++)
// {
// num2_int[j] = num2_string[j]-48;
// Console.Write(" " + num2_int[j]);
// }

        int[,] num3_int = new int[num2_int.Length, (num1_int.Length + 1)];
        int i,k,temp=0;

        //Multiplication on Individual Digits Done and the Values are there in the Individual Cells of the Array
        for(i=0;i<num2_int.Length;i++)
        {
            for (k = 0; k < num1_int.Length; k++)
            {
                int mul = (num1_int[k] * num2_int[i])+temp;
                num3_int[i, k] = mul % 10;
                temp = mul / 10;
                if (k == (num1_int.Length - 1))
                {
                    num3_int[i, k+1] = temp;
                }

// Console.Write(" " + num3_int[i, k]);
}
// Console.Write(" " + num3_int[i, k]);
temp=0;
// Console.WriteLine();
}

// temp = 0;

// Console.ReadLine();
int[] result_int = new int[num1_int.Length + num2_int.Length];

// int[,] num3_int = new int[num2_string.Length, (num1_string.Length + 1)];

        double result=0;

        for(i=0;i<num2_int.Length;i++)
            for (k = 0; k < (num1_int.Length + 1); k++)
            {

// Console.Write(" i = " + i + " k=" + k+" “);
// Console.Write(num3_int[i, k]);
result=result+(num3_int[i,k]*Math.Pow(10,k)*Math.Pow(10,i));
// Console.WriteLine(” "+(num3_int[i,k]*Math.Pow(10,k)*Math.Pow(10,i)));
// Console.WriteLine("10^k " + Math.Pow(10,k));

            }

        int[,] num4_int= new int[num2_int.Length,num1_int.Length + num2_int.Length];
        for (i = 0; i < num2_int.Length; i++)
        {
            for (k = 0; k < (num1_int.Length + 1); k++)
            {
                //for (int l = 0; l < 0; l++)
                {
                    num4_int[i,k + i] = num3_int[i,k]; 
                }
            }               
        }

        for (i = 0; i < num2_int.Length; i++)
        {
            for (k = 0; k < (num1_int.Length + num2_int.Length); k++)
            {

// Console.Write(" " + num4_int[i, k]);
}
// Console.WriteLine();
}

        int[] re_int = new int[num1_int.Length + num2_int.Length];
        temp=0;
        for (i = 0; i < re_int.Length; i++)
        {
            re_int[i] = 0;
            for (k = 0; k < num2_int.Length; k++)
            {
                re_int[i] = num4_int[k, i] + re_int[i];
            }
            int t = re_int[i] + temp;
            re_int[i]=t%10;
            temp=t/10;
            if(i==(re_int.Length-1))
            {
                //Need to check
            }
        }

// Console.WriteLine("Final Result - Reversed Order “);
// for(i=0;i<re_int.Length;i++)
// Console.Write(” "+re_int[i]);

         //           re_int[i+k]=;

// Console.WriteLine("Final Result - Correct Order “);
// for(i=re_int.Length-1;i>=0;i–)
// Console.Write(” " + re_int[i]);

// Console.WriteLine(result);
// Console.ReadLine();
return re_int;
}
}
}

dating advice for women

22

ok thats a good idea

23

@s1h33p
What would happen if m = 2??

24

Thanks a lot :slight_smile:

25

I was always confused to do this task. And finally your post removed my confusion.

Thank you for your effective article. :slight_smile:

26

The efficient way to calculate factorial is by calculating k-th last element on k-th iteration. If you can output to a file all you need is O(n) space lesser multiplications. infact, we can do that without multiplications.
Checkout for full article:

27

Yes, using a char array instead of an int array, since we are only storing digits and not numbers, would make more sense when talking about a memory efficient code.

On this case, I chose clarity over efficiency, as I believe that for a newbie that reads this tutorial, introducing the idea that a char is actually a very small int could be unnecessary complicated :slight_smile:

9 Likes
28

When digits are stored in the form of ascii code then digits 0-9 can’t be treated as 0-9. Digits will be treated as 48-57. To use digit 1 as number 1 if it is stored as char then 48 should be subtracted from ascii value of 1 i.e 49.
49-48=1

29

that return_array method is really ugly!!!

1 Like
30

@pavanishiny

t represents number of test cases.

And about (t–), after each loop value of t is decremented by 1, and till condition is TRUE i.e. till value of t is greater than 0 loop runs and as value of t becomes 0 loop terminates.

Hope you have understood the concept. . . :slight_smile:

31

Thanks a lot

32

source - anudeep’s blog.

1 Like
33

#include<stdio.h>
#include<stdlib.h>
#define m double
m fact(m n)
{
m i,ans=1;
for(i=2;i<=n;i++)
ans=ans*i;
return ans;
}
int main()
{
m t,n;
int i;
scanf("%lf",&t);
n=(m)malloc(sizeof(m)*t);
for(i=0;i<t;i++)
scanf("%lf",&n[i]);
for(i=0;i<t;i++)
printf("\n%0.0lf",fact(n[i]));
return 0;
}
getting correct on compiler but gives wrong answer on codechef

34

codechef reply
codechef reply1366×767 40.5 KB

35

#define m double

Omg. You deserve this Compilation error :smirk:.