Re: Fastest way to convert a byte of integer into a list
On Jul 13, 3:46 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 13, 5:17 am, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 12, 5:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? Standing on the shoulders of previous posters, I put this together. -- Paul But aren't we moving backwards? The OP did ask for the fastest way. I put this together (from other posters and my own): import gmpy import time y = 2**177149 - 1 # init list of tuples by byte bytebits = lambda num : [num i 1 for i in range(8)] bytes = [ tuple(bytebits(i)) for i in range(256) ] # use bytes lookup to get bits in a 32-bit integer bits = lambda num : sum((bytes[num i 255] for i in range(0,32,8)), ()) # use base-2 log to find how many bits in an integer of arbitrary length from math import log,ceil log_of_2 = log(2) numBits = lambda num : int(ceil(log(num)/log_of_2)) # expand bits to integers of arbitrary length arbBits = lambda num : sum((bytes[num i 255] for i in range(0,numBits(num),8)),()) t0 = time.time() L = arbBits(y) t1 = time.time() print 'Paul McGuire algorithm:',t1-t0 t0 = time.time() L = [y i 1 for i in range(177149)] t1 = time.time() print ' Matimus algorithm:',t1-t0 x = gmpy.mpz(2**177149 - 1) t0 = time.time() L = [gmpy.getbit(x,i) for i in range(177149)] t1 = time.time() print ' Mensanator algorithm:',t1-t0 ##Paul McGuire algorithm: 17.483676 ## Matimus algorithm: 3.28100013733 ## Mensanator algorithm: 0.125- Hide quoted text - - Show quoted text - Oof! Pre-calculating those byte bitmasks doesn't help at all! It would seem it is faster to use a single list comp than to try to sum together the precalcuated sublists. I *would* say though that it is somewhat cheating to call the other two algorithms with the hardcoded range length of 177149, when you know this is the right range because this is tailored to fit the input value 2**177149-1. This would be a horrible value to use if the input number were something small, like 5. I think numBits still helps here to handle integers of arbitrary length (and only adds a slight performance penalty since it is called only once). -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 14, 5:49?pm, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 13, 3:46 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 13, 5:17 am, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 12, 5:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? Standing on the shoulders of previous posters, I put this together. -- Paul But aren't we moving backwards? The OP did ask for the fastest way. I put this together (from other posters and my own): import gmpy import time y = 2**177149 - 1 # init list of tuples by byte bytebits = lambda num : [num i 1 for i in range(8)] bytes = [ tuple(bytebits(i)) for i in range(256) ] # use bytes lookup to get bits in a 32-bit integer bits = lambda num : sum((bytes[num i 255] for i in range(0,32,8)), ()) # use base-2 log to find how many bits in an integer of arbitrary length from math import log,ceil log_of_2 = log(2) numBits = lambda num : int(ceil(log(num)/log_of_2)) # expand bits to integers of arbitrary length arbBits = lambda num : sum((bytes[num i 255] for i in range(0,numBits(num),8)),()) t0 = time.time() L = arbBits(y) t1 = time.time() print 'Paul McGuire algorithm:',t1-t0 t0 = time.time() L = [y i 1 for i in range(177149)] t1 = time.time() print ' Matimus algorithm:',t1-t0 x = gmpy.mpz(2**177149 - 1) t0 = time.time() L = [gmpy.getbit(x,i) for i in range(177149)] t1 = time.time() print ' Mensanator algorithm:',t1-t0 ##Paul McGuire algorithm: 17.483676 ## Matimus algorithm: 3.28100013733 ## Mensanator algorithm: 0.125 Oof! Pre-calculating those byte bitmasks doesn't help at all! It would seem it is faster to use a single list comp than to try to sum together the precalcuated sublists. I *would* say though that it is somewhat cheating to call the other two algorithms with the hardcoded range length of 177149, when you know this is the right range because this is tailored to fit the input value 2**177149-1. This would be a horrible value to use if the input number were something small, like 5. I think numBits still helps here to handle integers of arbitrary length (and only adds a slight performance penalty since it is called only once). I agree. But I didn't want to compare your numBits against gmpy's numdigits() which I would normally use. But since the one algorithm required a hardcoded number, I thought it best to hardcode all three. I originally coded this stupidly by converting the number to a string and then converting to a list of integers. But Matimus had already posted his which looked a lot better than mine, so I didn't. But then I got to wondering if Matimus' solution requires (B**2+B)/2 shift operations for B bits. My attempt to re-code his solution to only use B shifts didn't work out and by then you had posted yours. So I did the 3-way comparison using gmpy's direct bit comparison. I was actually surprised at the difference. I find gmpy's suite of bit manipulation routines extremely valuable and use them all the time. That's another reason for my post, to promote gmpy. It is also extremely important to keep coercion out of loops. In other words, never use literals, only pre-coerced constants. For example: import gmpy def collatz(n): ONE = gmpy.mpz(1) TWO = gmpy.mpz(2) TWE = gmpy.mpz(3) while n != ONE: if n % TWO == ONE: n = TWE*n + ONE else: n = n/TWO collatz(gmpy.mpz(2**177149-1)) -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 15, 11:12 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 14, 5:49?pm, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 13, 3:46 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 13, 5:17 am, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 12, 5:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? Standing on the shoulders of previous posters, I put this together. -- Paul But aren't we moving backwards? The OP did ask for the fastest way. I put this together (from other posters and my own): import gmpy import time y = 2**177149 - 1 # init list of tuples by byte bytebits = lambda num : [num i 1 for i in range(8)] bytes = [ tuple(bytebits(i)) for i in range(256) ] # use bytes lookup to get bits in a 32-bit integer bits = lambda num : sum((bytes[num i 255] for i in range(0,32,8)), ()) # use base-2 log to find how many bits in an integer of arbitrary length from math import log,ceil log_of_2 = log(2) numBits = lambda num : int(ceil(log(num)/log_of_2)) # expand bits to integers of arbitrary length arbBits = lambda num : sum((bytes[num i 255] for i in range(0,numBits(num),8)),()) t0 = time.time() L = arbBits(y) t1 = time.time() print 'Paul McGuire algorithm:',t1-t0 t0 = time.time() L = [y i 1 for i in range(177149)] t1 = time.time() print ' Matimus algorithm:',t1-t0 x = gmpy.mpz(2**177149 - 1) t0 = time.time() L = [gmpy.getbit(x,i) for i in range(177149)] t1 = time.time() print ' Mensanator algorithm:',t1-t0 ##Paul McGuire algorithm: 17.483676 ## Matimus algorithm: 3.28100013733 ## Mensanator algorithm: 0.125 Oof! Pre-calculating those byte bitmasks doesn't help at all! It would seem it is faster to use a single list comp than to try to sum together the precalcuated sublists. I *would* say though that it is somewhat cheating to call the other two algorithms with the hardcoded range length of 177149, when you know this is the right range because this is tailored to fit the input value 2**177149-1. This would be a horrible value to use if the input number were something small, like 5. I think numBits still helps here to handle integers of arbitrary length (and only adds a slight performance penalty since it is called only once). I agree. But I didn't want to compare your numBits against gmpy's numdigits() which I would normally use. But since the one algorithm required a hardcoded number, I thought it best to hardcode all three. I originally coded this stupidly by converting the number to a string and then converting to a list of integers. But Matimus had already posted his which looked a lot better than mine, so I didn't. But then I got to wondering if Matimus' solution requires (B**2+B)/2 shift operations for B bits. My attempt to re-code his solution to only use B shifts didn't work out and by then you had posted yours. So I did the 3-way comparison using gmpy's direct bit comparison. I was actually surprised at the difference. I find gmpy's suite of bit manipulation routines extremely valuable and use them all the time. That's another reason for my post, to promote gmpy. It is also extremely important to keep coercion out of loops. In other words, never use literals, only pre-coerced constants. For example: import gmpy def collatz(n): ONE = gmpy.mpz(1) TWO = gmpy.mpz(2) TWE = gmpy.mpz(3) while n != ONE: if n % TWO == ONE: n = TWE*n + ONE else: n = n/TWO collatz(gmpy.mpz(2**177149-1)) -- Paul Try the following function; it works for arbitrary positive integers, doesn't need a 3rd party module, doesn't need to worry whether all that ceil/log/log floating-point stuffing about could result in an off- by-one error in calculating the number of bits, works with Python 1.5.2, and is competitive with Matimus's method. def listbits(n): result = [] app = result.append while n: app(n 1) n = n 1 return result Cheers, John -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On 7 13 , 6 34 , Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? my clone *bin* function from python3000 def _bin(n, count=32): returns the binary of integer n, using count number of digits return ''.join([str((n i) 1) for i in range(count-1, -1, -1)]) -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 12, 5:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? Standing on the shoulders of previous posters, I put this together. -- Paul # init list of tuples by byte bytebits = lambda num : [num i 1 for i in range(8)] bytes = [ tuple(bytebits(i)) for i in range(256) ] # use bytes lookup to get bits in a 32-bit integer bits = lambda num : sum((bytes[num i 255] for i in range(0,32,8)), ()) # use base-2 log to find how many bits in an integer of arbitrary length from math import log,ceil log_of_2 = log(2) numBits = lambda num : int(ceil(log(num)/log_of_2)) # expand bits to integers of arbitrary length arbBits = lambda num : sum((bytes[num i 255] for i in range(0,numBits(num),8)),()) print arbBits((134)-1) print arbBits(37) # prints #(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0) #(1, 0, 1, 0, 0, 1, 0, 0) -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 13, 5:17 am, Paul McGuire [EMAIL PROTECTED] wrote: On Jul 12, 5:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? Standing on the shoulders of previous posters, I put this together. -- Paul But aren't we moving backwards? The OP did ask for the fastest way. I put this together (from other posters and my own): import gmpy import time y = 2**177149 - 1 # init list of tuples by byte bytebits = lambda num : [num i 1 for i in range(8)] bytes = [ tuple(bytebits(i)) for i in range(256) ] # use bytes lookup to get bits in a 32-bit integer bits = lambda num : sum((bytes[num i 255] for i in range(0,32,8)), ()) # use base-2 log to find how many bits in an integer of arbitrary length from math import log,ceil log_of_2 = log(2) numBits = lambda num : int(ceil(log(num)/log_of_2)) # expand bits to integers of arbitrary length arbBits = lambda num : sum((bytes[num i 255] for i in range(0,numBits(num),8)),()) t0 = time.time() L = arbBits(y) t1 = time.time() print 'Paul McGuire algorithm:',t1-t0 t0 = time.time() L = [y i 1 for i in range(177149)] t1 = time.time() print ' Matimus algorithm:',t1-t0 x = gmpy.mpz(2**177149 - 1) t0 = time.time() L = [gmpy.getbit(x,i) for i in range(177149)] t1 = time.time() print ' Mensanator algorithm:',t1-t0 ##Paul McGuire algorithm: 17.483676 ## Matimus algorithm: 3.28100013733 ## Mensanator algorithm: 0.125 -- http://mail.python.org/mailman/listinfo/python-list
Fastest way to convert a byte of integer into a list
Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 12, 3:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? num = 255 numlist = [num i 1 for i in range(8)] -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 13, 9:54 am, Matimus [EMAIL PROTECTED] wrote: On Jul 12, 3:34 pm, Godzilla [EMAIL PROTECTED] wrote: Hello, I'm trying to find a way to convert an integer (8-bits long for starters) and converting them to a list, e.g.: num = 255 numList = [1,1,1,1,1,1,1,1] with the first element of the list being the least significant, so that i can keep appending to that list without having to worry about the size of the integer. I need to do this because some of the function call can return a 2 lots of 32-bit numbers. I have to find a way to transport this in a list... or is there a better way? num = 255 numlist = [num i 1 for i in range(8)] Thanks matimus! I will look into it... -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 13, 9:54 am, Matimus [EMAIL PROTECTED] wrote: num = 255 numlist = [num i 1 for i in range(8)] Godzilla wrote: Thanks matimus! I will look into it... Watch out for the order, which might or might not match your intent. Cheers, Alan Isaac -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 12, 8:49 pm, John Machin [EMAIL PROTECTED] wrote: On Jul 13, 10:28 am, Paul Rubin http://[EMAIL PROTECTED] wrote: Godzilla [EMAIL PROTECTED] writes: num = 255 numlist = [num i 1 for i in range(8)] Thanks matimus! I will look into it... numlist = lookup_table[num] where lookup_table is a precomputed list of lists. Ummm ... didn't the OP say he had 32-bit numbers??? List comprehension would be faster, lookup would be even faster but would have to generate list or dictionary ahead of time but this will work on any length int up 2 limit of int does not pad with zeros on most significant end to word length. n=input() l=[] while(n0): l.append(str(n1)); n=n1 I posted this here http://www.uselesspython.com/download.php?script_id=222 a while back. -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
John Machin [EMAIL PROTECTED] writes: numlist = lookup_table[num] where lookup_table is a precomputed list of lists. Ummm ... didn't the OP say he had 32-bit numbers??? He asked about 8 bit numbers. I saw something about 32-bit numbers but figured those would be split into bytes or something: (untested and I don't remember if this is the byte order wanted): from itertools import chain numlist = list(chain(lookup_table[(numi)0xff] for i in xrange(0,32,8))) -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
Godzilla [EMAIL PROTECTED] writes: num = 255 numlist = [num i 1 for i in range(8)] Thanks matimus! I will look into it... numlist = lookup_table[num] where lookup_table is a precomputed list of lists. -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 13, 10:28 am, Paul Rubin http://[EMAIL PROTECTED] wrote: Godzilla [EMAIL PROTECTED] writes: num = 255 numlist = [num i 1 for i in range(8)] Thanks matimus! I will look into it... numlist = lookup_table[num] where lookup_table is a precomputed list of lists. Ummm ... didn't the OP say he had 32-bit numbers??? -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
On Jul 13, 11:13 am, bsneddon [EMAIL PROTECTED] wrote: On Jul 12, 8:49 pm, John Machin [EMAIL PROTECTED] wrote: On Jul 13, 10:28 am, Paul Rubin http://[EMAIL PROTECTED] wrote: Godzilla [EMAIL PROTECTED] writes: num = 255 numlist = [num i 1 for i in range(8)] Thanks matimus! I will look into it... numlist = lookup_table[num] where lookup_table is a precomputed list of lists. Ummm ... didn't the OP say he had 32-bit numbers??? List comprehension would be faster, lookup would be even faster but would have to generate list or dictionary ahead of time but this will work on any length int up 2 limit of int does not pad with zeros on most significant end to word length. n=input() l=[] while(n0): l.append(str(n1)); n=n1 I posted this herehttp://www.uselesspython.com/download.php?script_id=222 a while back. Thanks all... I will have a look at it soon. Regarding to the 32-bit number, the lenght is variable but it is usually defined at design time... -- http://mail.python.org/mailman/listinfo/python-list
Re: Fastest way to convert a byte of integer into a list
Godzilla [EMAIL PROTECTED] writes: Regarding to the 32-bit number, the lenght is variable but it is usually defined at design time... That you're trying to represent it as a list of bits at all is weird, and probably likely to slow the program down. You do know that python has arbitrary sized ints, right? -- http://mail.python.org/mailman/listinfo/python-list
