Encoding a 128 bit integer in Python?
Inspired by the "coding scheme" of the answer to this question , I implemented my own coding algorithm in Python.
This is how it looks:
import random from math import pow from string import ascii_letters, digits # RFC 2396 unreserved URI characters unreserved = '-_.!~*\'()' characters = ascii_letters + digits + unreserved size = len(characters) seq = range(0,size) # Seed random generator with same randomly generated number random.seed(914576904) random.shuffle(seq) dictionary = dict(zip(seq, characters)) reverse_dictionary = dict((v,k) for k,v in dictionary.iteritems()) def encode(n): d =  n = n while n > 0: qr = divmod(n, size) n = qr d.append(qr) chars = '' for i in d: chars += dictionary[i] return chars def decode(str): d =  for c in str: d.append(reverse_dictionary[c]) value = 0 for i in range(0, len(d)): value += d[i] * pow(size, i) return value
The problem I'm running into is encoding and decoding very large integers. For example, this is how large numbers are currently being encoded and decoded:
s = encode(88291326719355847026813766449910520462) print s -> "3_r(AUqqMvPRkf~JXaWj8" i = decode(s) print i -> "8.82913267194e+37" print long(i) -> "88291326719355843047833376688611262464"
The highest 16 places match up perfectly, but after them the number deviates from the original.
I guess this is a precision issue with very large integers when dividing in Python. Is there a way to get around this problem? Or is there another problem that I am not aware of?
source to share
The problem is this line:
value += d[i] * pow(size, i)
You seem to be using
the inline method here instead
. It returns a floating point number, so you lose precision for your large numbers. You must use the built-in operator,
, better yet, store the current cardinality of the base in an integer variable:
def decode(s): d = [reverse_dictionary[c] for c in s] result, power = 0, 1 for x in d: result += x * power power *= size return result
Now it gives me the following output:
print decode(encode(88291326719355847026813766449910520462)) # => 88291326719355847026813766449910520462
source to share