Divisibility check for (kind of) large numbers in python

Question

I am writing a simple python program that encodes a string into a number using Gödel coding . Here is a brief overview: you take the first letter of the line, find its position in the alphabet (a → 1, b → 2, ..., z → 26) and raise the first prime number (2) by this force. You take the second letter in the string and the second simple (3) and so on. Here is the 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 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 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 

The primes () function works for my purposes and goals, as well as Encode (). Now Decode () is the interesting part. It works for encodings up to 15 digits long, but starts to do some mystical things, starting with ~ 20 digits. So, for example, it gives the correct output for the encoding "aaaaaaaaaaaaaaa", but not for "python". For large numbers, it seems to execute the while code % i == 0 too many times (176 for the first letter of "python", when there should be only 16).

Is this just a problem with the mod function in python? It sounds strange, since 20 digits are not so long for a computer. Is there an error in my code? Thanks for the help. I'm not a programmer myself, but I'm trying to learn how to do such things. Therefore, any constructive criticism is welcome.

Answer 1

/= in Python 3 returns a double-precision floating-point value. (Like math.ceil , btw.) Floating-point values ​​do not have arbitrary precision. You can use //= instead. This always leads to an integer. (This gives half the result.)

(I previously said that your main culprit was math.ceil. I do not think this is the case, but, nevertheless, you probably should not use a floating point value to index the list. If you need to run the same the code in Python 2 will fail. You can return it to an integer using int(math.ceil(...)) , although you may need to avoid floating point calculations at all, as things will start to break down for large enough values .)