how to get the thighest bit position in big integers?

This topic is closed.

mmgarvey@gmx.de
#1

how to get the thighest bit position in big integers?

Oct 5 '08, 03:35 PM

Hi,

I'm using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python's
native bignum capabilities.

In many cryptographic applications there is the need for a function
'get_highest_bi t_num' that returns the position number of the highest
set bit of a given integer. For example:

get_highest_bit _num( (1 << 159)) == 159
get_highest_bit _num( (1 << 160) - 1) == 159
get_highest_bit _num( (1 << 160)) == 160

I implemented this the following way:

def get_highest_bit _num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i

This works, but it is a very unsatisfying solution, because it is so
slow.

My second try was using the math.log function:

import math
r = (1 << 160) - 1
print highest_bit_num (r) # prints out 159
print math.floor(math .log(r, 2)) # prints out 160.0

We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn't any more.

My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn't that hackish?

cheers,
mmg
Tags: None
Gary Herron
#2

Oct 5 '08, 04:45 PM

Re: how to get the thighest bit position in big integers?

mmgarvey@gmx.de wrote:

Hi,
>
I'm using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python's
native bignum capabilities.
>
In many cryptographic applications there is the need for a function
'get_highest_bi t_num' that returns the position number of the highest
set bit of a given integer. For example:
>
get_highest_bit _num( (1 << 159)) == 159
get_highest_bit _num( (1 << 160) - 1) == 159
get_highest_bit _num( (1 << 160)) == 160
>

How about a binary search?

>>from bisect import bisect
>>BITS = [1<<n for n in range(1,1000)] # Use max number of bits here.
>>bisect(BITS , 1<<159)

159

>>bisect(BITS , 1<<160-1)

159

>>bisect(BITS , 1<<160)

160

>>>

I have no clue if this is faster or not. The comparison function used
in the search is (potentially) slow, but the search is O(log n) on the
number of bits rather than O(n), so its worth a test.

If you run timing test, let us know the results.

Gary Herron

I implemented this the following way:
>
def get_highest_bit _num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i
>
This works, but it is a very unsatisfying solution, because it is so
slow.
>
My second try was using the math.log function:
>
import math
r = (1 << 160) - 1
print highest_bit_num (r) # prints out 159
print math.floor(math .log(r, 2)) # prints out 160.0
>
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn't any more.
>
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn't that hackish?
>
cheers,
mmg
--

Mailman 3 Info | python-list@python.org - python.org

http://mail.python.org/mailman/listinfo/python-list

>
Comment
Duncan Booth
#3

Oct 5 '08, 04:55 PM

Re: how to get the thighest bit position in big integers?

mmgarvey@gmx.de wrote:

My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn't that hackish?
>

How about using the hex representation of the value?

OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433 222211111111"))
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]
Comment
Terry Reedy
#4

Oct 5 '08, 05:15 PM

Re: how to get the thighest bit position in big integers?

mmgarvey@gmx.de wrote:

Hi,
>
I'm using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python's
native bignum capabilities.
>
In many cryptographic applications there is the need for a function
'get_highest_bi t_num' that returns the position number of the highest
set bit of a given integer. For example:
>
get_highest_bit _num( (1 << 159)) == 159
get_highest_bit _num( (1 << 160) - 1) == 159
get_highest_bit _num( (1 << 160)) == 160
>
I implemented this the following way:
>
def get_highest_bit _num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i
>
This works, but it is a very unsatisfying solution, because it is so
slow.

One alternative is to compare r against successive larger powers of 2,
starting with 2**0 == 1. Given that you have p=2**(n-1), you could test
whether generating 2**n for large n is faster as 1<<n or p<<1. A
refinement would be to raise the test power k at a time instead of 1 at
a time, tuning k for the implementation. Then do binary search in the
interval n, n+k. I once read that longs store 15 bits in pairs of
bytes. If true today, k = 15 might be a good choice since <<15 would
mean tacking on a pair of 0 bytes.

My second try was using the math.log function:
>
import math
r = (1 << 160) - 1
print highest_bit_num (r) # prints out 159
print math.floor(math .log(r, 2)) # prints out 160.0
>
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn't any more.

I tested and floor(log(2**n, 2) == n for n in range(400), so your only
worry is that the answer is 1 too high. Easy to check and fix

res = int(math.floor( math.log(r, 2)))
if (1<<res) r: res -=1

This works for 2**n-1 over the same range (all tests with 3.0rc1).

My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python?

If you call the standard methods hackish, I have no idea what would
satisfy you ;-)

Terry Jan Reedy
Comment
$Aaron \Castironpi\ Brady$
Aaron \Castironpi\ Brady
#5

Oct 5 '08, 07:15 PM

Re: how to get the thighest bit position in big integers?

Duncan Booth wrote:

mmgarvey@gmx.de wrote:
>

>My question to the group: Does anyone know of a non-hackish way to
>determine the required bit position in python? I know that my two
>ideas
>can be combined to get something working. But is there a *better* way,
>that isn't that hackish?
>>

How about using the hex representation of the value?
>
OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433 222211111111"))
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]
--

Mailman 3 Info | python-list@python.org - python.org

http://mail.python.org/mailman/listinfo/python-list

>

You can replace the dict if it's faster.

OFFSET= tuple( int(x) for x in "54332222111111 11" )
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[int(s[0],16)]

P.S. Back home, this sort of 'nitpicking' would be judged
unconstructive. Worth pointing out, or not worth saying?

P.S.S. 'Thighest' bit? I thought the spam filters would catch that.
Comment
Duncan Booth
#6

Oct 5 '08, 08:35 PM

Re: how to get the thighest bit position in big integers?

"Aaron \"Castironpi \" Brady" <castironpi@gma il.comwrote:

>OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433 222211111111"))
>def get_highest_bit _num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[s[0]]

>
You can replace the dict if it's faster.
>
OFFSET= tuple( int(x) for x in "54332222111111 11" )
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[int(s[0],16)]
>
P.S. Back home, this sort of 'nitpicking' would be judged
unconstructive. Worth pointing out, or not worth saying?
>

You could have answered your own question fairly quickly using the 'timeit'
module. In this case you trade off the dict lookup for a global name lookup
and a function call so I'd expect you would have made it slower and indeed
it seems to be about 30-40% slower than mine.

The math.floor/math.log version isn't so good for small values, but both
string versions seem to slow down dramatically somewhere around 526 bits
(2.8uS suddenly jumps to about 4us while the math version stays roughly
steady around 3.2uS).
Comment
Scott David Daniels
#7

Oct 5 '08, 11:25 PM

Re: how to get the thighest bit position in big integers?

Terry Reedy wrote:

...
Your point, that taking floor(log2(x)) is redundant, is a good catch.
However, you should have added 'untested' ;-). When value has more
significant bits than the fp mantissa can hold, this expression can be 1
off (but no more, I assume). The following correction should be
sufficient:
>
res = math.frexp(valu e)[1] - EXP_OF_ONE
test = 1<<res
if test r: res -= 1
elif 2*test < r: res += 1

Well, I did test, but poorly.

>>high_bit(1<<5 87)

587

>>high_bit(1<<5 87-1)

586

And of course, I _should_ have tested

>>high_bit((1<< 587)-1)

587

By the way, I wrote my response before any replies had happened; it was
not a correction to your post.

--Scott David Daniels
Scott.Daniels@A cm.Org
Comment
Rich Healey
#8

Oct 6 '08, 12:05 AM

Re: how to get the thighest bit position in big integers?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron "Castironpi " Brady wrote:

Duncan Booth wrote:

>mmgarvey@gmx.de wrote:
>>

>>My question to the group: Does anyone know of a non-hackish way to
>>determine the required bit position in python? I know that my two
>>ideas
>>can be combined to get something working. But is there a *better* way,
>>that isn't that hackish?
>>>

>How about using the hex representation of the value?
>>
>OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433 222211111111"))
>def get_highest_bit _num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[s[0]]
>--
>http://mail.python.org/mailman/listinfo/python-list
>>

>
You can replace the dict if it's faster.
>
OFFSET= tuple( int(x) for x in "54332222111111 11" )
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[int(s[0],16)]
>
P.S. Back home, this sort of 'nitpicking' would be judged
unconstructive. Worth pointing out, or not worth saying?
>
P.S.S. 'Thighest' bit? I thought the spam filters would catch that.
>

That should be P.P.S.

PS: This is also unconstructive nitpicking.

Kind regards

Rich ;)

- --
Rich Healey - iTReign \ .''`. / healey.rich@gma il.com
Developer / Systems Admin \ : :' : / healey.rich@itr eign.com
AIM: richohealey33 \ `. `' / richo@psych0tik .net
MSN: bitchohealey@ho tmail.com \ `- / richohealey@hel lboundhackers.o rg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkj pVZUACgkQLeTfO4 yBSAcgeACgr45Hu 4XKyMjCf0jwq1LR 35tU
Lv8AnRn2RgHCxJ3 QwYpNO8/DjLncKv2t
=/WZa
-----END PGP SIGNATURE-----
Comment
$Aaron \Castironpi\ Brady$
Aaron \Castironpi\ Brady
#9

Oct 6 '08, 12:05 AM

Re: how to get the thighest bit position in big integers?

On Oct 5, 2:12 pm, "Aaron \"Castironpi \" Brady" <castiro...@gma il.com>
wrote:

Duncan Booth wrote:

mmgar...@gmx.de wrote:

>

OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433 222211111111"))
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]

>
OFFSET= tuple( int(x) for x in "54332222111111 11" )
def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[int(s[0],16)]

That's really counterintuitiv e. (That's the word, yes.) They're both
function calls and both global variables. Maybe you could use 'len(s)
* 4' to mask out the rest and lookup that index, rather than
converting -back- to integer. Or, better yet, take 'ord' of s[0].
(Ha ha, -you- time it.)
Comment
$Aaron \Castironpi\ Brady$
Aaron \Castironpi\ Brady
#10

Oct 6 '08, 12:15 AM

Re: how to get the thighest bit position in big integers?

On Oct 5, 7:02 pm, Rich Healey <healey.r...@gm ail.comwrote:

P.S. Back home, this sort of 'nitpicking' would be judged
unconstructive. Worth pointing out, or not worth saying?

>

P.S.S. 'Thighest' bit? I thought the spam filters would catch that.

>
That should be P.P.S.
>
PS: This is also unconstructive nitpicking.
>
Kind regards
>
Rich ;)

Hey, whatever gets the bills paid, friend.
Comment
Duncan Booth
#11

Oct 6 '08, 08:25 AM

Re: how to get the thighest bit position in big integers?

"Aaron \"Castironpi \" Brady" <castironpi@gma il.comwrote:

On Oct 5, 2:12 pm, "Aaron \"Castironpi \" Brady" <castiro...@gma il.com>
wrote:

>Duncan Booth wrote:

mmgar...@gmx.de wrote:

>>

OFFSET = dict(("%x"%i, int(c)) for i,c in
enumerate("5433 222211111111")) def get_highest_bit _num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]

>>
>OFFSET= tuple( int(x) for x in "54332222111111 11" )
>def get_highest_bit _num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[int(s[0],16)]

>
That's really counterintuitiv e. (That's the word, yes.) They're both
function calls and both global variables. Maybe you could use 'len(s)
* 4' to mask out the rest and lookup that index, rather than
converting -back- to integer. Or, better yet, take 'ord' of s[0].
(Ha ha, -you- time it.)

No, the difference between the two is still an extra call to a global
function.

'ord' may be slightly faster than calling 'int' (function calls with two
arguments are slower than similar functions with only one), but you have
still added one extra variable lookup and function call over the original.

--
Duncan Booth http://kupuguy.blogspot.com
Comment
Mark Dickinson
#12

Oct 6 '08, 08:45 AM

Re: how to get the thighest bit position in big integers?

On Oct 5, 11:40 pm, Terry Reedy <tjre...@udel.e duwrote:

Your point, that taking floor(log2(x)) is redundant, is a good catch.
However, you should have added 'untested' ;-). When value has more
significant bits than the fp mantissa can hold, this expression can be 1
off (but no more, I assume). The following correction should be
sufficient:
>
res = math.frexp(valu e)[1] - EXP_OF_ONE
test = 1<<res
if test r: res -= 1
elif 2*test < r: res += 1
>
For value = 2**n -1, n 53, it is always 1 too high on my Intel
machine, so the first correction is sometimes needed. I do not know if
the second is or not.

See also http://bugs.python.org/issue3439
where there's a proposal to expose the _PyLong_NumBits method. This
would give an O(1) solution.

Mark
Comment
bearophileHUGS@lycos.com
#13

Oct 6 '08, 10:25 AM

Re: how to get the thighest bit position in big integers?

Mark Dickinson:

See alsohttp://bugs.python.org/issue3439
where there's a proposal to expose the _PyLong_NumBits method. This
would give an O(1) solution.

Sounds useful, I've used the gmpy.numdigits( x [,base]) few times.

Bye,
bearophile
Comment
Holger
#14

Oct 6 '08, 10:45 AM

Re: how to get the thighest bit position in big integers?

On 6 Okt., 10:37, Mark Dickinson <dicki...@gmail .comwrote:

See alsohttp://bugs.python.org/issue3439
where there's a proposal to expose the _PyLong_NumBits method. This
would give an O(1) solution.

Doesn't that depend on the underlying implementation?

Anyway, here's a pretty one (I think):
def highest_bit(n, maxbits = 256):
bit = 0
while maxbits 1:
maxbits = maxbits >1
mask_b = ((1<<maxbits)-1)
mask_a = mask_b<<maxbits
a = n & mask_a
b = n & mask_b
if a:
bit = bit + maxbits
n = a >maxbits
else:
n = b
return bit

I suspect you would call that a O(logn)) solution

Holger
Comment
Holger
#15

Oct 6 '08, 11:45 AM

Re: how to get the thighest bit position in big integers?

def highest_bit(n, maxbits = 256):
bit = 0
while maxbits 1:
maxbits >>= 1
a = n >maxbits
if a:
bit += maxbits
n = a
return bit

is sligtly better
Comment

Previous 1 2 3 template Next

how to get the thighest bit position in big integers?

how to get the thighest bit position in big integers?

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment