Omnifarious - 3 months ago 7
Python Question

# Is there a faster way to convert an arbitrary large integer to a big endian sequence of bytes?

I have this Python code to do this:

``````from struct import pack as _pack

if lnum < 0:
raise RangeError("Cannot use packl to convert a negative integer "
"to a string.")
count = 0
l = []
while lnum > 0:
l.append(lnum & 0xffffffffffffffffL)
count += 1
lnum >>= 64
if count <= 0:
lens = 8 * count % pad
l.append('>' + 'x' * pad + 'Q' * count)
l.reverse()
return _pack(*l)
else:
l.append('>' + 'Q' * count)
l.reverse()
s = _pack(*l).lstrip('\0')
lens = len(s)
if (lens % pad) != 0:
else:
return s
``````

This takes approximately 174 usec to convert
`2**9700 - 1`
to a string of bytes on my machine. If I'm willing to use the Python 2.7 and Python 3.x specific
`bit_length`
method, I can shorten that to 159 usecs by pre-allocating the
`l`
array to be the exact right size at the very beginning and using
`l[something] =`
`l.append`
.

Is there anything I can do that will make this faster? This will be used to convert large prime numbers used in cryptography as well as some (but not many) smaller numbers.

Edit

This is currently the fastest option in Python < 3.2, it takes about half the time either direction as the accepted answer:

``````def packl(lnum, padmultiple=1):
"""Packs the lnum (which must be convertable to a long) into a
byte string 0 padded to a multiple of padmultiple bytes in size. 0
means no padding whatsoever, so that packing 0 result in an empty
string.  The resulting byte string is the big-endian two's
complement representation of the passed in long."""

if lnum == 0:
elif lnum < 0:
raise ValueError("Can only convert non-negative numbers.")
s = hex(lnum)[2:]
s = s.rstrip('L')
if len(s) & 1:
s = '0' + s
s = binascii.unhexlify(s)
if filled_so_far != 0:
s = b'\0' * (padmultiple - filled_so_far) + s
return s

def unpackl(bytestr):
"""Treats a byte string as a sequence of base 256 digits
representing an unsigned integer in big-endian format and converts
that representation into a Python integer."""

return int(binascii.hexlify(bytestr), 16) if len(bytestr) > 0 else 0
``````

In Python 3.2 the
`int`
class has
`to_bytes`
and
`from_bytes`
functions that can accomplish this much more quickly that the method given above.

Starting in Python 3.2, there are functions `int.from_bytes()` and `int.to_bytes()` that perform the conversion between `bytes` and `int` objects in a choice of byte orders.