Dumb python questions

[Paul Rubin]

bokr at accessone.com (Bengt Richter) writes:
> >Here's one: say I have a long int, like x = 7**77777L.  How can I tell
> >how many bits it takes to express that number in binary?  How can I
> >convert it into a packed character string (i.e. represent it in string
> >form with 8 bits/char so I can write it to a file)?  The answers I can
> >think of involve weird kludges and/or are unacceptably slow.
> >
> >Thanks.
> Brute force, but easy to understand:
>  >>> x = 7**77777L
>  >>> cl = []
>  >>> while x:
>  ...     cl += chr(x&0xff)
>  ...     x = x>>8
>  ...
>  >>> s = ''.join(cl)
> 
> Which gives you a little-endian result.

This is too slow to be reasonable.

> To get the string length required quickly, we can use
> the builtin hex conversion which is very fast.
> Note the '0x' in front and 'L' at the end (3 extra)
>  >>> hex(x)[:5]
>  '0xC7F'

Thanks, I didn't know about the hex function.  I tried ('%x' % x) and
it gave me an overflow error message (Python 1.5.2).  It works in 2.1.1.

To convert to binary, I think using hex(x) on the long int and then
using  the binascii package to convert hex to binary is likely
to be faster than the division loop above.

> I grant you, the while loop takes a few seconds, and so does the
> 7**77777L.  How fast do you need? We could write faster algorithms
> for the exponentiations, and also the conversion to string, both in
> Python. We could also obviously write a fast extension to do it in
> C/C++ and return a string of 8-bit chars as fast as the hex()
> function.  How fast do you need?

I just think something is terribly wrong if converting the number
to a binary representation (which it's already in, after all) is
much slower than computing the number in the first place.  How
would you do either the exponentiation or the conversion faster
in Python?

The numbers I actually want to use are closer in magnitude to 7**777
rather than 7**77777, if that matters.  I'd prefer to avoid using
a C library.  If I use one, gmpy should do the job.  I've timed
Python's arithmetic as around 10x slower than gmpy, which is
quite respectable since gmpy's inner loops are carefully tuned
assembly code, and this kind of arithmetic is hard to do efficiently
in portable C.  Python's arithmetic is around 100x faster than
perl's Math::BigInt.