Controllo della divisibilità per (sorta di) grandi numeri in python

Question

Ho scritto un semplice programma in python che codifica una stringa in un numero usando Gödel's encoding. Ecco una rapida panoramica: prendi la prima lettera della stringa, trova la sua posizione nell'alfabeto (a -> 1, b -> 2, ..., z -> 26) e solleva il primo numero primo (2) in questo potere. Prendi la seconda lettera nella stringa e il secondo primo (3) e così via. Ecco il codice: function

import string, math 
alphabet = list(string.ascii_lowercase) 

def primes(n): 
    "Returns a list of primes up to n." 

    primes = [2, 3] 
    i = 5 
    while i < n: 
     l = math.ceil(math.sqrt(i)) 
     k = math.ceil(math.sqrt(i+2)) 
     for p in primes[:l]: 
      if i % p == 0: 
       break 
     else: 
      primes.append(i) 
     for p in primes[:k]: 
      if (i+2) % p == 0: 
       break 
     else: 
      primes.append(i+2) 
     i += 6 
    return primes 

def Encode(string): 
    "Encodes a string using Godel's encoding." 

    enc = 1 
    p = primes(100) 
    for i in range(len(string)): 
     enc = enc*(p[i]**(alphabet.index(string[i])+1)) 
    return enc 

def Decode(code): 
    "Decodes a Godel's encoding into a string." 

    dec = "" 
    for i in primes(100): 
     count = 0 
     while code % i == 0: 
      code /= i 
      count += 1 
     if count == 0: #If we've found a prime that doesn't divide code, 
         #there are no more letters to be added. 
      break 
     else: 
      dec += alphabet[count-1] 
    return dec 

I numeri primi() lavora per la mia intenzione e scopi e così fa Encode(). Ora Decode() è la parte interessante. Funziona per codifiche lunghe fino a ~ 15 cifre, ma inizia a fare alcune cose mistiche a partire da ~ 20 cifre. Quindi, ad esempio, fornisce l'output giusto per la codifica di "aaaaaaaaaaaaaa" ma non per "python". Per grandi numeri sembra eseguire il ciclo while code % i == 0 troppe volte (176 per la prima lettera di "python" quando dovrebbe essere solo 16).

È solo un problema con la funzione mod in python? Sembra strano come 20 cifre non è poi così tanto tempo per un computer. C'è un errore nel mio codice? Grazie per tutto l'aiuto. Non sono un programmatore, ma sto cercando di imparare a fare cose del genere. Pertanto ogni critica costruttiva è ben accetta.

Answer 1

/= in Python 3 restituisce un valore in virgola mobile a precisione doppia. (Come fa math.ceil, btw.) I valori in virgola mobile non hanno precisione arbitraria. Potresti usare //= invece. Ciò risulta sempre in un numero intero. (Dà la parola al risultato.)

(Ho detto in precedenza che math.ceil era il tuo principale colpevole. Non penso che sia così, ma comunque non dovresti usare un valore in virgola mobile per indicizzare in un elenco.Se è necessario eseguire lo stesso codice in Python 2 che non riuscirà, è possibile ricondurlo a un numero intero utilizzando int(math.ceil(...)), anche se si potrebbe voler considerare di evitare del tutto i calcoli a virgola mobile, poiché le cose inizieranno a abbattere per valori sufficientemente grandi.)