0votos

Factorion en C

por josejuan hace 6 años

Mi versión de Haskell sólo revisa unos 6.300 números. Esta versión de C revisa los 2.500.000 pero es sensiblemente más rápida. Un buen ejemplo en que la constante multiplicativa es importante.

Sabiendo que no hay factoriones mayores que 2.500.000, encontrarlos a todos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* 
en un AMD Phenom X6 2,7Ghz:  9 milisegundos 
en un Atom D510 1,6Ghz: 41 milisegundos 
*/ 
#include <stdio.h> 
 
int main(int argc, char **argv) { 
    int f[10], i; 
    char d[7]; 
    f[0] = 1; 
    for(i = 1; i < 10; i++) 
        f[i] = f[i - 1] * i; 
    for(i = 0; i < 7; i++) 
        d[i] = 0; 
    int s = 1, maxid = 0; 
    for(i = 1; i < 2500000; i++) { 
 
        // hacer ésto, es MUCHO más rápido que dividir hasta 0 
        // lo que se hace aquí es contar en base 10 (como en el cole XD) 
        int id = 0; 
        for(;;) { 
            char q = d[id]; 
            if(id <= maxid) s -= f[q]; 
            if(maxid < id) maxid = id; 
            if(++q == 10) { 
                s++; 
                d[id] = 0; 
                id++; 
            } else { 
                d[id] = q; 
                s += f[q]; 
                break; 
        if(s == i) 
            printf("%i\n", i); 
    return 0; 
2 comentarios
0votos

Escrito por josejuan hace 6 años

No me había fijado, ¡pero son 9,72 ciclos de reloj para revisar cada número! XD XD XD
0votos

Escrito por josejuan hace 6 años

Por supuesto, la constante multiplicativa sólo saca ventaja "en las distancias cortas", como era de esperar, si el lugar de 2.500.000 hacemos que deban buscarse factoriones hasta 25.000.000, ahora (en el Atom) los tiempos quedan:

algoritmo "tonto" en "C" hasta 25.000.000: 383 milisegundos
algoritmo "listo" en "Haskell" hasta 25.000.000: 118 milisegundos

concretamente, los costes son:

millones; tiempo C; tiempo Haskell
1; 18; 50
10; 155; 108
100; 1521; 234
1000; 15171; 479

el primero tiene un coste lineal respecto N y el segundo logarítmico, es decir

algoritmo C O(n)
algoritmo Haskell O(log n)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.