Lo siento, me siento estúpido preguntando esto y estoy dispuesto a perder la mitad de mis puntos preguntando esto, pero ¿por qué este algoritmo no funciona? Funciona hasta cierto punto. Después del número 13, los factoriales están un poco apagados. Por ejemplo, los números no coinciden completamente en el lugar de los cientos de miles en adelante.

#include <stdio.h>

float factorial(unsigned int i) {

    if (i <= 1) {
        return 1;
    }
    return i * factorial(i - 1);
}

int  main() {
    int i = 13;
    printf("Factorial of %d is %f\n", i, factorial(i));
    return 0;
}

Aquí está la salida:

Factorial of 13 is 6227020800.000000

Aquí hay un ejemplo de salida imprecisa:

Factorial of 14 is 87178289152.000000

La salida para el número 14 debería ser realmente esta (de mathisfun.com)

14 87,178,291,200

Cambié el tipo de retorno a flotante para obtener una salida más precisa, pero obtuve este código en su mayor parte desde aquí: https://www.tutorialspoint.com/cprogramming/c_recursion.htm

EDITAR: si cambio al tipo de retorno para duplicar la salida es precisa hasta 21. Estoy usando el formateador de cadena % Lf para la salida en printf función.

4
user3870315 6 ene. 2017 a las 19:56

4 respuestas

La mejor respuesta

Alguien publicó una pregunta similar hace un tiempo. El consenso fue que si lo está escribiendo para el trabajo, use una biblioteca de números grandes (como GMP) y si es un ejercicio de programación, escriba una solución usando una matriz de caracteres.

Por ejemplo:

/* fact50.c

   calculate a table of factorials from 0! to 50! by keeping a running sum of character digits
*/

#include <stdio.h>
#include <string.h>

int main (void)
{
    printf ("\n                            Table of Factorials\n\n");

    // length of arrays = 65 character digits

    char str[] =
    "00000000000000000000000000000000000000000000000000000000000000000"; 
    char sum[] =
    "00000000000000000000000000000000000000000000000000000000000000001"; 

    const int len = strlen (str);
    int index;

    for ( int i = 0; i <= 50; ++i ) {

        memcpy (str, sum, len);

        for ( int j = 1; j <= i - 1; ++j ) {

            index = len - 1;        
            int carry = 0;

            do {
                int digit = (sum[index] - '0') + (str[index] - '0') + carry;            
                carry = 0;
                if ( digit > 9 ) {
                    carry = 1;
                    digit %= 10;
                }            
                sum[index] = digit + '0';
                --index;
            }
            while ( index >= 0 );

        }

        printf ("%2i! = ", i);
        for ( index = 0; sum[index] == '0'; ++index )
            printf ("%c", '.');
        for ( ; index < len; ++index )
            printf ("%c", sum[index]);
        printf ("\n");        

    }

    return 0;
}
2
Have Compiler -- Will Travel 7 ene. 2017 a las 02:54

Simple. float no puede almacenar con precisión enteros por encima de 16777216 sin pérdida de precisión.

int es mejor que flotar. Pero intente long long para que pueda almacenar correctamente 19 dígitos.

11
Paul Stelian 6 ene. 2017 a las 18:11

¿Por qué este algoritmo factorial no es exacto?

No hay nada malo en tu algorithm como tal. Es solo que los tipos de datos que usa tienen un límite para el número más alto que pueden almacenar. Esto será un problema sin importar qué algoritmo elijas. Puede cambiar los tipos de datos de float a algo como long double para contener algo más grande. Pero eventualmente comenzará a fallar una vez que el valor factorial exceda la capacidad de ese tipo de datos. En mi opinión, debe poner una condición en su función factorial para devolver sin calcular nada si el argumento pasado es mayor que un valor que su tipo de datos elegido puede admitir.

2
VHS 6 ene. 2017 a las 17:33

OP está encontrando los límites de precisión de float. Para típico float, valores de números enteros superiores a {{X2} } no todos son exactamente representables. Algunos resultados factoriales por encima de este punto son exactamente representables.

Probemos esto con diferentes tipos.
En 11!, los resultados float exceden 16777216.0f y son exactamente correctos.
En 14!, el resultado float es impreciso debido a la precisión limitada.
En 23!, el resultado double es impreciso debido a la precisión limitada.

En 21!, la respuesta supera mi uintmax_t rango .
En 35!, la respuesta supera mi float rango .
En 171!, la respuesta supera mi double rango .

Una representación de cadena es precisa sin fin hasta que alcanza las limitaciones del búfer.

#include <stdint.h>
#include <string.h>
#include <stdio.h>

uintmax_t factorial_uintmax(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_uintmax(i - 1);
}

float factorial_float(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_float(i - 1);
}

double factorial_double(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_double(i - 1);
}

char * string_mult(char *y, unsigned base, unsigned x) {
  size_t len = strlen(y);
  unsigned acc = 0;
  size_t i = len;
  while (i > 0) {
    i--;
    acc += (y[i] - '0') * x;
    y[i] = acc % base + '0';
    acc /= base;
  }
  while (acc) {
    memmove(&y[1], &y[0], ++len);
    y[0] = acc % base + '0';
    acc /= base;
  }
  return y;
}

char *factorial_string(char *dest, unsigned int i) {
  strcpy(dest, "1");
  for (unsigned m = 2; m <= i; m++) {
    string_mult(dest, 10, m);
  }
  return dest;
}

void factorial_test(unsigned int i) {
  uintmax_t u = factorial_uintmax(i);
  float f = factorial_float(i);
  double d = factorial_double(i);
  char s[2000];
  factorial_string(s, i);
  printf("factorial of %3d is uintmax_t: %ju\n", i, u);
  printf("                    float:     %.0f %s\n", f, "*" + (1.0 * f == u));
  printf("                    double:    %.0f %s\n", d, "*" + (d == u));
  printf("                    string:    %s\n", s);
}

int main(void) {
  for (unsigned i = 11; i < 172; i++)
    factorial_test(i);
  return 0;
}

Salida

factorial of  11 is uintmax_t: 39916800
                    float:     39916800 
                    double:    39916800 
                    string:    39916800
factorial of  12 is uintmax_t: 479001600
                    float:     479001600 
                    double:    479001600 
                    string:    479001600
factorial of  13 is uintmax_t: 6227020800
                    float:     6227020800 
                    double:    6227020800 
                    string:    6227020800
factorial of  14 is uintmax_t: 87178291200
                    float:     87178289152 *
                    double:    87178291200 
                    string:    87178291200
factorial of  20 is uintmax_t: 2432902008176640000
                    float:     2432902023163674624 *
                    double:    2432902008176640000 
                    string:    2432902008176640000
factorial of  21 is uintmax_t: 14197454024290336768
                    float:     51090940837169725440 *
                    double:    51090942171709440000 *
                    string:    51090942171709440000
factorial of  22 is uintmax_t: 17196083355034583040
                    float:     1124000724806013026304 *
                    double:    1124000727777607680000 *
                    string:    1124000727777607680000
factorial of  23 is uintmax_t: 8128291617894825984
                    float:     25852017444594485559296 *
                    double:    25852016738884978212864 *
                    string:    25852016738884976640000
factorial of  34 is uintmax_t: 4926277576697053184
                    float:     295232822996533287161359432338880069632 *
                    double:    295232799039604119555149671006000381952 *
                    string:    295232799039604140847618609643520000000
factorial of  35 is uintmax_t: 6399018521010896896
                    float:     inf *
                    double:    10333147966386144222209170348167175077888 *
                    string:    10333147966386144929666651337523200000000
factorial of 170 is uintmax_t: 0
                    float:     inf *
                    double:    72574156153079940453996357155895914678961840000000... *
                    string:    72574156153079989673967282111292631147169916812964...
factorial of 171 is uintmax_t: 0
                    float:     inf *
                    double:    inf *
                    string:    12410180702176678234248405241031039926166055775016...
3
chux - Reinstate Monica 6 ene. 2017 a las 19:28