Überprüfen der Teilbarkeit für (Art von) große Zahlen in Python

Question

Ich habe ein einfaches Programm in Python geschrieben, das eine Zeichenfolge in eine Nummer mit Gödel's encoding codiert. Hier ein kurzer Überblick: Du nimmst den ersten Buchstaben des Strings, suchst seine Position im Alphabet (a -> 1, b -> 2, ..., z -> 26) und ziehst die erste Primzahl (2) auf diese Kraft. Sie nehmen den zweiten Buchstaben in der Zeichenfolge und die zweite Primzahl (3) und so weiter. Hier ist der Code:

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 

Die Primzahlen() Funktion funktioniert für meine Absicht und Zweck und so auch Encode(). Jetzt ist Decode() der interessante Teil. Es funktioniert für Codierungen mit bis zu ~ 15 Ziffern, beginnt aber mit mystischen Dingen, die bei ~ 20 Ziffern beginnen. Zum Beispiel gibt es die richtige Ausgabe für die Kodierung von "aaaaaaaaaaaaaa", aber nicht für "python". Für große Zahlen scheint es, die while code % i == 0 Schleife zu oft auszuführen (176 für den ersten Buchstaben von "Python", wenn es nur 16 sein sollte).

Ist das nur ein Problem mit der Mod-Funktion in Python? Klingt komisch, da 20 Ziffern für einen Computer nicht allzu lang sind. Gibt es einen Fehler in meinem Code? Danke für die Hilfe. Ich bin selbst kein Programmierer, aber ich versuche so etwas zu lernen. Daher ist jede konstruktive Kritik willkommen.

Answer 1

/= in Python 3 gibt einen Gleitkommawert mit doppelter Genauigkeit zurück. (Wie auch math.ceil, btw.) Fließkommawerte haben keine willkürliche Genauigkeit. Sie könnten stattdessen //= verwenden. Das ergibt immer eine Ganzzahl. (Es gibt den Boden des Ergebnisses.)

(Ich sagte zuvor, dass math.ceil war der Hauptschuldige. Ich denke nicht, dass das der Fall ist, aber nichtsdestoweniger sollten Sie wahrscheinlich keinen Gleitkommawert verwenden Wenn Sie denselben Code in Python 2 ausführen müssen, der fehlschlägt, können Sie ihn mit int(math.ceil(...)) in eine Ganzzahl umwandeln, obwohl Sie vielleicht die Berechnung von Gleitkommazahlen überhaupt in Betracht ziehen möchten, da die Dinge beginnen werden break down für ausreichend große Werte.)