Calcular el factorial de un número arbitrariamente grande, mostrando todos los dígitos

5 minutos de lectura

Recientemente me pidieron, en una entrevista, que describiera un método para calcular el factorial de cualquier número arbitrariamente grande; un método en el que obtenemos todos los dígitos de la respuesta.

Busqué en varios lugares y pregunté en algunos foros. Pero me gustaría saber si hay alguna forma de lograr esto sin usar bibliotecas como GMP.

Gracias.

Calcular el factorial de un numero arbitrariamente grande mostrando todos
ultrainstinto

¡La biblioteca GNU Multiprecision es buena! Pero como usted dice que no se permite el uso de bibliotecas externas, la única forma en que creo que es posible es tomando una matriz de int y luego multiplicando los números como lo hace con un lápiz sobre papel.

Aquí está el código que escribí hace algún tiempo ..

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}


void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :\n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

‘arr’ es solo una matriz de enteros, y factorial es una función simple que multiplica el número dado por el ‘número grande’.

Espero que esto resuelva tu consulta..

  • esa línea en main debiera ser factorial(arr,num) ¡o siempre obtendrás 10! producción. Déjame arreglar eso 🙂

    – schnaader

    27 de diciembre de 2009 a las 14:46


  • Muchas gracias por la respuesta inmediata..! ¡Esto era lo que estaba buscando! 🙂

    Anónimo

    27 de diciembre de 2009 a las 14:47

  • ¡¡UPS!! si, gracias por señalarlo! ¡Simplemente copié mi código y lo pegué aquí! :PAGS

    – UltraInstinto

    27 de diciembre de 2009 a las 14:49

  • @Prasoon, ¿qué significa “mejor”?

    – Drew Dorman

    27 de diciembre de 2009 a las 16:22

  • @Prasoon: esta solución no pretende ser eficiente, entonces, ¿por qué molestarse en convertir la recursividad en iteración?

    – rafak

    28 de diciembre de 2009 a las 9:28

La respuesta aceptada está bien, pero esto es C++; podemos hacerlo mejor. Hagamos el comienzo de los nuestros Bignum clase, con un número de dígitos totalmente ilimitado.

Para obtener la mayor eficiencia, trabajaríamos con números binarios puros, empaquetando cada elemento de la matriz con tantos bits como podamos manejar de manera eficiente. El enfoque más simple es almacenar un solo dígito decimal en cada elemento. Aquí he ido por un compromiso, almacenando 9 dígitos decimales en cada uint32_t elemento.

Los datos se almacenan little-endian, ya que es mucho más fácil extender un vector al final cuando necesitamos elementos de orden superior.

Una vez que tenemos esta clase, la función factorial es la simplicidad misma.

#include <assert.h>
#include <iomanip>
#include <iostream>
#include <stdint.h>
#include <vector>

class Bignum
{
public:
    Bignum(int value)
    {
        assert(value >= 0 && value <= 999999999);
        parts.push_back(value);
    }

    Bignum& operator*=(int rhs)
    {
        assert(rhs >= 0 && rhs <= 999999999);
        uint32_t carry = 0;
        for (size_t i = 0; i < parts.size(); i++)
        {
            uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry;
            parts[i] = (uint32_t)(product % 1000000000LL);
            carry = (uint32_t)(product / 1000000000LL);
        }
        if (carry != 0)
            parts.push_back(carry);
        return *this;
    }

    friend std::ostream & operator<<(std::ostream& stream, const Bignum& num);

private:
    std::vector<uint32_t> parts;
};

inline std::ostream& operator<<(std::ostream& stream, const Bignum& num)
{
    char oldfill = stream.fill('0');
    for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++)
        stream << *it << std::setw(9);
    stream.fill(oldfill);
    stream.width(0);
    return stream;
}

Bignum factorial(int n)
{
    Bignum fac = 1;
    for (int i = 2; i <= n; i++)
        fac *= i;
    return fac;
}

int main(int argc, char* argv[])
{
    for (int n = 0; n <= 52; n++)
        std::cout << factorial(n) << std::endl;
    return 0;
}

1646746817 661 Calcular el factorial de un numero arbitrariamente grande mostrando todos
Cenizo

Buena solución de Srivatsan Iyer y mi sugerencia es:

  1. Todavía se puede hacer que la memoria sea más eficiente mediante el uso de una matriz de caracteres sin firmar en lugar de usar una matriz int para almacenar dígitos. Tomará solo el 25% de la memoria necesaria para la matriz int.

  2. Para la mejor optimización de la memoria, también podemos usar un solo byte para representar 2 dígitos. Dado que solo 4 bits son suficientes para representar cualquier dígito del 0 al 9, podemos empaquetar dos dígitos en un solo byte usando operaciones bit a bit. Tomará el 12.5% ​​de la memoria necesaria para la matriz int.

  • O podemos usar 32 bits para almacenar nueve dígitos. O 64 bits para almacenar 19 dígitos.

    – gnasher729

    21 de agosto de 2015 a las 19:15

Una clase BigInteger resolvería su problema, y ​​la implementación de C anterior le da una idea de cómo se implementaría un BigInt, excepto que el código está optimizado para la velocidad y adaptado para calcular el factorial únicamente.

1646746818 556 Calcular el factorial de un numero arbitrariamente grande mostrando todos
schnaader

Bueno, tendrías que escribir tus propias rutinas matemáticas usando matrices. Eso es muy fácil para la suma, la multiplicación es un poco más difícil, pero aún es posible.

EDITAR: Quería publicar un ejemplo, pero el ejemplo de Srivatsan Iyer está bien.

Tengo una solución para calcular el factorial, que funciona bien para al menos n<=15000. El factorial de 10000 se puede calcular en 1 segundo y el cálculo del factorial lleva menos de 2 segundos. (Por supuesto, su pregunta no dice nada sobre las limitaciones de tiempo y estos tiempos dependen totalmente de la máquina). De todos modos, el concepto es bastante simple. Yo uso una matriz de caracteres. El primer carácter de la matriz es '1'. Los LSB se almacenan desde el índice que comienza con 0. Una variable (m según mi programa) realiza un seguimiento de la longitud factorial. El valor final de m es el número de dígitos en el factorial y el (m-1)-ésimo elemento de la matriz de caracteres es el MSB del factorial. A medida que el ciclo itera, los caracteres se agregan en el lado derecho de la matriz. Una variable 'c' realiza un seguimiento del acarreo.

Los inconvenientes de usar la matriz son fragmentos de bytes no utilizados. Y más allá de cierto punto, no puede reservar espacio para una matriz. Además, las matrices tienden a volverse lentas.

Puedes consultar mi programa en ideone: http://ideone.com/K410n7

Creo que mi solución aún se puede optimizar. Por favor sugiera cómo.

include<stdio.h> 

char res[200000];

inline int fact(int n)
{

    int i,j;

    register int m,c;

    m=1;

    res[0]='1';

    for(i=2;i<=n;i++)
    {

        c=0;

        for(j=0; j< m; j++){

            c =((res[j]-48)*i)+c;

            res[j]=(c%10)+48;

            c=c/10;

        }
        while(c>0){
            res[m]=(c%10)+48;

            c=c/10;

            m++;

        }

    }

    return m;

}

int main() {


    int n,i,d;

    scanf("%d",&n);


    d=fact(n);

    for(i=d-1;i>=0;i--)

        printf("%c",res[i]);


    return 0;
}

1646746818 126 Calcular el factorial de un numero arbitrariamente grande mostrando todos
HSA

#include <iostream>
using namespace std;
int main ()
{
    int i,n,p=1;
    cout<<"Enter a number: ";
    cin>>n;
    cout<<endl;

    for (i=1;i<=n; i++)
    {
        cout<<i<<" X "; 
        p=p*i;
    }
    cout<<endl<<endl<<p<<" factorial of "<<n;

    return 0;
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad