factorial de un numero grande

Factorial de un entero no negativo, es la multiplicación de todos los enteros menores o iguales a n. Por ejemplo, el factorial de 6 es 6*5*4*3*2*1, que es 720.

Hemos discutido el programa simple para factorial .

¿Cómo calcular factorial de 100 usando un programa C/C++?  
El factorial de 100 tiene 158 dígitos. No es posible almacenar tantos dígitos incluso si usamos long long int. 

Ejemplos: 

Input : 100
Output : 933262154439441526816992388562667004-
         907159682643816214685929638952175999-
         932299156089414639761565182862536979-
         208272237582511852109168640000000000-
         00000000000000

Input :50
Output : 3041409320171337804361260816606476884-
         4377641568960512000000000000

La siguiente es una solución simple en la que usamos una array para almacenar dígitos individuales del resultado. La idea es usar matemáticas básicas para la multiplicación.

El siguiente es un algoritmo detallado para encontrar factorial.
factorial (n) 
1) Cree una array ‘res []’ de tamaño MAX donde MAX es el número máximo de dígitos en la salida. 
2) Inicialice el valor almacenado en ‘res[]’ como 1 e inicialice ‘res_size’ (tamaño de ‘res[]’) como 1. 
3) Haga lo siguiente para todos los números desde x = 2 hasta n. 
……a) Multiplique x con res[] y actualice res[] y res_size para almacenar el resultado de la multiplicación.

¿Cómo multiplicar un número ‘x’ con el número almacenado en res[]?  
La idea es utilizar matemáticas escolares simples. Multiplicamos uno por uno x con cada dígito de res[]. El punto importante a tener en cuenta aquí es que los dígitos se multiplican desde el dígito más a la derecha hasta el dígito más a la izquierda. Si almacenamos dígitos en el mismo orden en res[], se vuelve difícil actualizar res[] sin espacio adicional. Es por eso que res[] se mantiene en forma inversa, es decir, se almacenan los dígitos de derecha a izquierda.

multiplicar (res[], x) 
1) Inicializar carry como 0. 
2) Hacer lo siguiente para i = 0 a res_size – 1 
….a) Encontrar el valor de res[i] * x + carry. Sea este valor prod. 
….b) Actualice res[i] almacenando el último dígito de prod en él. 
….c) Actualice el acarreo almacenando los dígitos restantes en el acarreo. 
3) Ponga todos los dígitos del acarreo en res[] y aumente res_size por el número de dígitos en el acarreo.

Example to show working of multiply(res[], x)
A number 5189 is stored in res[] as following.
res[] = {9, 8, 1, 5}
x = 10

Initialize carry = 0;

i = 0, prod = res[0]*x + carry = 9*10 + 0 = 90.
res[0] = 0, carry = 9

i = 1, prod = res[1]*x + carry = 8*10 + 9 = 89
res[1] = 9, carry = 8

i = 2, prod = res[2]*x + carry = 1*10 + 8 = 18
res[2] = 8, carry = 1

i = 3, prod = res[3]*x + carry = 5*10 + 1 = 51
res[3] = 1, carry = 5

res[4] = carry = 5

res[] = {0, 9, 8, 1, 5} 

A continuación se muestra la implementación del algoritmo anterior. 

NOTA: En la implementación a continuación, se supone que el máximo de dígitos en la salida es 500. Para encontrar un factorial de un número mucho mayor (> 254), aumente el tamaño de una array o aumente el valor de MAX.

// C++ program to compute factorial of big numbers
#include<iostream>
using namespace std;
 
// Maximum number of digits in output
#define MAX 500
 
int multiply(int x, int res[], int res_size);
 
// This function finds factorial of large numbers
// and prints them
void factorial(int n)
{
    int res[MAX];
 
    // Initialize result
    res[0] = 1;
    int res_size = 1;
 
    // Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n
    for (int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);
 
    cout << "Factorial of given number is \n";
    for (int i=res_size-1; i>=0; i--)
        cout << res[i];
}
 
// This function multiplies x with the number
// represented by res[].
// res_size is size of res[] or number of digits in the
// number represented by res[]. This function uses simple
// school mathematics for multiplication.
// This function may value of res_size and returns the
// new value of res_size
int multiply(int x, int res[], int res_size)
{
    int carry = 0;  // Initialize carry
 
    // One by one multiply n with individual digits of res[]
    for (int i=0; i<res_size; i++)
    {
        int prod = res[i] * x + carry;
 
        // Store last digit of 'prod' in res[] 
        res[i] = prod % 10; 
 
        // Put rest in carry
        carry  = prod/10;   
    }
 
    // Put carry in res and increase result size
    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}
 
// Driver program
int main()
{
    factorial(100);
    return 0;
}

// JAVA program to compute factorial
// of big numbers
class GFG {
     
    // This function finds factorial of
    // large numbers and prints them
    static void factorial(int n)
    {
        int res[] = new int[500];
 
        // Initialize result
        res[0] = 1;
        int res_size = 1;
 
        // Apply simple factorial formula
        // n! = 1 * 2 * 3 * 4...*n
        for (int x = 2; x <= n; x++)
            res_size = multiply(x, res, res_size);
 
        System.out.println("Factorial of given number is ");
        for (int i = res_size - 1; i >= 0; i--)
            System.out.print(res[i]);
    }
     
    // This function multiplies x with the number
    // represented by res[]. res_size is size of res[] or
    // number of digits in the number represented by res[].
    // This function uses simple school mathematics for
    // multiplication. This function may value of res_size
    // and returns the new value of res_size
    static int multiply(int x, int res[], int res_size)
    {
        int carry = 0; // Initialize carry
 
        // One by one multiply n with individual
        // digits of res[]
        for (int i = 0; i < res_size; i++)
        {
            int prod = res[i] * x + carry;
            res[i] = prod % 10; // Store last digit of
                                // 'prod' in res[]
            carry = prod/10; // Put rest in carry
        }
 
        // Put carry in res and increase result size
        while (carry!=0)
        {
            res[res_size] = carry % 10;
            carry = carry / 10;
            res_size++;
        }
        return res_size;
    }
 
    // Driver program
    public static void main(String args[])
    {
        factorial(100);
    }
}
//This code is contributed by Nikita Tiwari

# Python program to compute factorial
# of big numbers
 
import sys
 
# This function finds factorial of large
# numbers and prints them
def factorial( n) :
    res = [None]*500
    # Initialize result
    res[0] = 1
    res_size = 1
 
    # Apply simple factorial formula
    # n! = 1 * 2 * 3 * 4...*n
    x = 2
    while x <= n :
        res_size = multiply(x, res, res_size)
        x = x + 1
     
    print ("Factorial of given number is")
    i = res_size-1
    while i >= 0 :
        sys.stdout.write(str(res[i]))
        sys.stdout.flush()
        i = i - 1
         
 
# This function multiplies x with the number
# represented by res[]. res_size is size of res[]
# or number of digits in the number represented
# by res[]. This function uses simple school
# mathematics for multiplication. This function
# may value of res_size and returns the new value
# of res_size
def multiply(x, res,res_size) :
     
    carry = 0 # Initialize carry
 
    # One by one multiply n with individual
    # digits of res[]
    i = 0
    while i < res_size :
        prod = res[i] *x + carry
        res[i] = prod % 10; # Store last digit of
                            # 'prod' in res[]
        # make sure floor division is used
        carry = prod//10; # Put rest in carry
        i = i + 1
 
    # Put carry in res and increase result size
    while (carry) :
        res[res_size] = carry % 10
        # make sure floor division is used
        # to avoid floating value
        carry = carry // 10
        res_size = res_size + 1
         
    return res_size
 
# Driver program
factorial(100)
 
#This code is contributed by Nikita Tiwari.

// C# program to compute
// factorial of big numbers
using System;
 
class GFG
{
     
    // This function finds factorial
    // of large numbers and prints them
    static void factorial(int n)
    {
        int []res = new int[500];
 
        // Initialize result
        res[0] = 1;
        int res_size = 1;
 
        // Apply simple factorial formula
        // n! = 1 * 2 * 3 * 4...*n
        for (int x = 2; x <= n; x++)
            res_size = multiply(x, res,
                                res_size);
 
        Console.WriteLine("Factorial of " +
                       "given number is ");
        for (int i = res_size - 1; i >= 0; i--)
            Console.Write(res[i]);
    }
     
    // This function multiplies x
    // with the number represented
    // by res[]. res_size is size
    // of res[] or number of digits
    // in the number represented by
    // res[]. This function uses
    // simple school mathematics for
    // multiplication. This function
    // may value of res_size and
    // returns the new value of res_size
    static int multiply(int x, int []res,
                        int res_size)
    {
        int carry = 0; // Initialize carry
 
        // One by one multiply n with
        // individual digits of res[]
        for (int i = 0; i < res_size; i++)
        {
            int prod = res[i] * x + carry;
            res[i] = prod % 10; // Store last digit of
                                // 'prod' in res[]
            carry = prod / 10; // Put rest in carry
        }
 
        // Put carry in res and
        // increase result size
        while (carry != 0)
        {
            res[res_size] = carry % 10;
            carry = carry / 10;
            res_size++;
        }
        return res_size;
    }
 
    // Driver Code
    static public void Main ()
    {
         
        factorial(100);
    }
}
 
// This code is contributed by ajit

<?php
// PHP program to compute factorial
// of big numbers
 
// Maximum number of digits in output
$MAX = 500;
 
// This function finds factorial of
// large numbers and prints them
function factorial($n)
{
    global $MAX;
    $res = array_fill(0, $MAX, 0);
 
    // Initialize result
    $res[0] = 1;
    $res_size = 1;
 
    // Apply simple factorial formula
    // n! = 1 * 2 * 3 * 4...*n
    for ($x = 2; $x <= $n; $x++)
        $res_size = multiply($x, $res, $res_size);
 
    echo "Factorial of given number is \n";
    for ($i = $res_size - 1; $i >= 0; $i--)
        echo $res[$i];
}
 
// This function multiplies x with the number
// represented by res[].
// res_size is size of res[] or number of
// digits in the number represented by res[].
// This function uses simple school mathematics
// for multiplication. This function may value 
// of res_size and returns the new value of res_size
function multiply($x, &$res, $res_size)
{
    $carry = 0; // Initialize carry
 
    // One by one multiply n with individual
    // digits of res[]
    for ($i = 0; $i < $res_size; $i++)
    {
        $prod = $res[$i] * $x + $carry;
 
        // Store last digit of 'prod' in res[]
        $res[$i] = $prod % 10;
 
        // Put rest in carry
        $carry = (int)($prod / 10);
    }
 
    // Put carry in res and increase
    // result size
    while ($carry)
    {
        $res[$res_size] = $carry % 10;
        $carry = (int)($carry / 10);
        $res_size++;
    }
    return $res_size;
}
 
// Driver Code
factorial(100);
     
// This code is contributed by chandan_jnu
?>

<script>
 
// Javascript program to compute factorial of big numbers
 
// This function finds factorial of large numbers
// and prints them
function factorial(n)
{
    let res = new Array(500);
 
    // Initialize result
    res[0] = 1;
    let res_size = 1;
 
    // Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n
    for (let x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);
 
    document.write("Factorial of given number is " + "<br>");
    for (let i=res_size-1; i>=0; i--)
        document.write(res[i]);
}
 
// This function multiplies x with the number
// represented by res[].
// res_size is size of res[] or number of digits in the
// number represented by res[]. This function uses simple
// school mathematics for multiplication.
// This function may value of res_size and returns the
// new value of res_size
function multiply(x, res, res_size)
{
    let carry = 0; // Initialize carry
 
    // One by one multiply n with individual digits of res[]
    for (let i=0; i<res_size; i++)
    {
        let prod = res[i] * x + carry;
 
        // Store last digit of 'prod' in res[]
        res[i] = prod % 10;
 
        // Put rest in carry
        carry = Math.floor(prod/10);
    }
 
    // Put carry in res and increase result size
    while (carry)
    {
        res[res_size] = carry%10;
        carry = Math.floor(carry/10);
        res_size++;
    }
    return res_size;
}
 
// Driver program
    factorial(100);
 
// This  code is contributed by Mayank Tyagi
 
</script>

Factorial of given number is 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Complejidad de tiempo : O(nlogn!) n for loop y logn! para bucle while

Espacio Auxiliar: O(MAX)

El enfoque anterior se puede optimizar de muchas maneras. Pronto discutiremos una solución optimizada para el mismo.
Este artículo es una contribución de Harshit Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Programa 2: (método BigInteger)

Big Integer también se puede usar para calcular el factorial de números grandes.

// Java program to find large
// factorials using BigInteger
import java.math.BigInteger;
import java.util.Scanner;
 
public class Example {
     
    // Returns Factorial of N
    static BigInteger factorial(int N)
    {
        // Initialize result
        BigInteger f
            = new BigInteger("1"); // Or BigInteger.ONE
 
        // Multiply f with 2, 3, ...N
        for (int i = 2; i <= N; i++)
            f = f.multiply(BigInteger.valueOf(i));
 
        return f;
    }
 
    // Driver method
    public static void main(String args[]) throws Exception
    {
        int N = 20;
        System.out.println(factorial(N));
    }
}

2432902008176640000

Programa 3: (usando LinkedList)

También se puede utilizar la lista enlazada, este enfoque no desperdiciará ningún espacio adicional.

#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, a, b) for (int i = a; i <= b; i++)
 
using namespace std;
// Made a class node containing data and previous pointer as
// we are using tail pointer
class Node {
public:
    int data;
    Node* prev;
    Node(int n)
    {
        data = n;
        prev = NULL;
    }
};
 
void Multiply(Node* tail, int n)
{
    Node *temp = tail,
         *prevNode = tail; // Temp variable for keeping tail
    int carry = 0;
    while (temp != NULL) {
        int data = temp->data * n + carry;
        temp->data = data % 10; // stores the last digit
        carry = data / 10;
        prevNode = temp;
        temp = temp->prev; // Moving temp by 1 prevNode will
                           // now denote temp
    }
    // If carry is greater than 0 then we create another
    // node for it.
    while (carry != 0) {
        prevNode->prev = new Node((int)(carry % 10));
        carry /= 10;
        prevNode = prevNode->prev;
    }
}
 
void print(Node* tail)
{
    if (tail == NULL) // Using tail recursion
        return;
    print(tail->prev);
    cout
        << tail->data; // Print linked list in reverse order
}
 
// Driver code
int main()
{
    int n = 20;
    Node tail(1); // Create a node and initialise it by 1
    rep(i, 2, n)
        Multiply(&tail, i); // Run a loop from 2 to n and
                            // multiply with tail's i
    print(&tail); // Print the linked list
    cout << endl;
    return 0;
}
 
// This code is contributed by Kingshuk Deb

2432902008176640000

Complejidad de tiempo: O (¡nlogn!)

Espacio Auxiliar: O(1)