Càlcul intensiu

Fa unes setmanes em va apretar per 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.

Deixa un comentari

Aquest lloc utilitza Akismet per reduir el correu brossa. Aprendre com la informació del vostre comentari és processada