Càlcul intensiu
Fa unes setmanes em va apretar per intentar esbrinar quin és el número primer més petit les xifres del qual sumin un primer més gran que 100. No té cap interès científic, però m’ha servit per a recordar una mica el C i veure les diferències de temps d’execució amb el Python, que és el llenguatge de programació que darrerament faig servir per a scripts i proves de concepte.
El número que busco ha de tenir, com a mínim, 12 xifres per raons òbvies, i ha de ser més gran que 299.999.999.999 (que és divisible per 7). Per trobar-lo he fet servir una aproximació de “força bruta”, comprovant tots els senars des del 299.999.999.999 fins al 999.999.999.999.
Se’m planteja el problema de calcular de forma eficient la suma de les xifres d’un número. Faig una primera aproximació en Python, amb diverses variants:
def suma1(numeroASumar): suma = 0 s = str(numeroASumar) for n in range(len(s)): suma = suma + int(s[n]) return suma def suma2(numeroASumar): suma = 0 s = str(numeroASumar) for n in range(len(s)): suma = suma + ord(s[n]) - 48 return suma def suma3(numeroASumar): suma = 0 s = str(numeroASumar) longitud = len(s) for n in range(longitud): suma = suma + ord(s[n]) - 48 return suma def suma4(numeroASumar): suma = 0 s = str(numeroASumar) for n in s: suma = suma + ord(n) - 48 return suma def suma5(numeroASumar): suma = 0 s = str(numeroASumar) for n in s: suma += ord(n) - 48 return suma def suma6(numeroASumar): suma = 0 while (numeroASumar > 0): suma += numeroASumar % 10 numeroASumar /= 10 return suma
Els resultats que obtinc són (temps mesurats amb la funció time.clock() per les sumes del primer milió d’enters):
| algorisme | temps |
|---|---|
| suma1 | 8,86 |
| suma2 | 6,26 |
| suma3 | 6,24 |
| suma4 | 4,93 |
| suma5 | 4,87 |
| suma6 | 3,62 |
Vistos els resultats és obvi pensar que la conversió a string consumeix força temps, i que l’aritmètica entera de suma6 és molt més ràpida.
Implemento en C l’algorisme complet, amb la precaució que guardi els resultats parcials a disc i sàpiga reprendre l’execució on ha estat aturada. Deixo el procés uns quants dies amb prioritat baixa. No tinc anotades les diferències de temps d’execució entre C i Python, però són molt grans (ho tornaré a mesurar).
El número buscat és el 399.999.998.999 I només hi ha 3 números primers més petits que 1.000.000.000.000 les xifres del qual sumin 107. Són els 999.998.999.999, 999.999.999.899, 999.999.999.989.
