# Help with an algorithm

18 messages
Open this post in threaded view
|

## Help with an algorithm

 Greetings,Sorry if this is more suited to a general programming forum—I hope the solution will be in Lua, and there are some pretty switched on people here... I’d like to iterate through all 40-bit binary numbers that have a Hamming weight of 25 (ie. 25 of the bits are set to 1). My naive solution of testing the Hamming weight of all 40-bit numbers looks like it will take half a year :-) , even with a fairly quick calculation of Hamming weight using 14-bit lookup tables... An alternative could use something like this:num = {}for i = 1, 15 do num[i] = "0" endfor i = 16, 40 do num[i] = "1" endn = tonumber(table.concat(num), 2)  -- test n Is there an efficient way of iterating through all combinations of "0" and "1" in num?Thank you,Vaughan
Open this post in threaded view
|

## Re: Help with an algorithm

 On 5/24/2013 1:29 PM, Vaughan McAlley wrote: > Sorry if this is more suited to a general programming forum—I hope > the solution will be in Lua, and there are some pretty switched on > people here... > > I’d like to iterate through all 40-bit binary numbers that have a > Hamming weight of 25 (ie. 25 of the bits are set to 1). My naive > solution of testing the Hamming weight of all 40-bit numbers looks > like it will take half a year :-) , even with a fairly quick > calculation of Hamming weight using 14-bit lookup tables... > > An alternative could use something like this: > > num = {} > > for i = 1, 15 do num[i] = "0" end > for i = 16, 40 do num[i] = "1" end > > n = tonumber(table.concat(num), 2)  -- test n > > Is there an efficient way of iterating through all combinations of > "0" and "1" in num? Maybe chop the number into two, giving two 20-bit segments. Each segment will have 5-20 set bits. Build tables for each number of set bits, then match two segments, e.g. 8 set bit in segment A will give 17 set bits in segment B. With tables precalculated, get the final number by putting A and B together. Not sure about the memory requirements, though... -- Cheers, Kein-Hong Man (esq.) Kuala Lumpur, Malaysia
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by Vaughan McAlley-2 On 24/05/2013 06:29, Vaughan McAlley wrote: > > I’d like to iterate through all 40-bit binary numbers that have a > Hamming weight of 25 (ie. 25 of the bits are set to 1). I think this may be what you want: http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
Open this post in threaded view
|

## Re: Help with an algorithm

 On Fri, May 24, 2013 at 1:09 AM, Finn Wilcox wrote: On 24/05/2013 06:29, Vaughan McAlley wrote: > > I’d like to iterate through all 40-bit binary numbers that have a > Hamming weight of 25 (ie. 25 of the bits are set to 1). I think this may be what you want: http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation See also http://www.hackersdelight.org/basics2.pdf (search for "snoob" around the end of 2-1) I don't know if the algorithm is any better, but the book explains some of the details.
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by Vaughan McAlley-2 Here is an iterator which will return the table each time it successfully generates a binary number with excepted number of ones: function generator(ones, total) return coroutine.wrap(function() local num = {} for i=1,total do num[i] = '0' end local function step(position, left) if left == 0 then coroutine.yield(num) elseif position > total then return else num[position] = '1' step(position + 1, left-1) num[position] = '0' step(position + 1, left) end end step(1, ones) end) endTo use it, just call it in a `for x in` loop: local count = 0 for n in generator(5, 10) do print(table.concat(n)) count = count + 1 end print('Total:', count) ​For this small test case, it generates 252 number. For your case, C(25,40) == 40225345056, which is over 40 billion numbers. Would you like to rethink your original problem?
Open this post in threaded view
|

## Re: Help with an algorithm

 On 24 May 2013 17:14, Michal Kottman <[hidden email]> wrote: > For this small test case, it generates 252 number. For your case, C(25,40) == 40225345056, which is over 40 billion numbers. > Would you like to rethink your original problem? I have a Raspberry Pi that can chug away for a couple of weeks, so it might be doable. Looks like I might need to put my C programmer’s hat on... thanks for all the suggestions!
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by Michal Kottman-2 On 5/24/2013 3:14 PM, Michal Kottman wrote: > [snip] > ​For this small test case, it generates 252 number. For your case, > C(25,40) == 40225345056, which is over 40 billion numbers. Would > you like to rethink your original problem? Oh yeah, I just wrote a complete implementation in Lua. Ran it on Lua 5.2 on an old Athlon 2.6GHz, one core at full tilt. The final number is calculated and a count is incremented, and it does nothing else. Setting to 10 hamming bits, it produces the expected count of 847660528 numbers in 125 seconds. For 25 hamming bits, the thingy should complete in a few hours at most. I split the number into segments of 8 bits, and using an auto-generated lookup table for 8 bit combinations, it loops several loops to join the bits together. -- Cheers, Kein-Hong Man (esq.) Kuala Lumpur, Malaysia
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by Vaughan McAlley-2 On Fri, 24 May 2013 17:20:40 +1000 Vaughan McAlley <[hidden email]> wrote: > On 24 May 2013 17:14, Michal Kottman <[hidden email]> wrote: > > For this small test case, it generates 252 number. For your case, > > C(25,40) == 40225345056, which is over 40 billion numbers. Would > > you like to rethink your original problem? > > > I have a Raspberry Pi that can chug away for a couple of weeks, so it > might be doable. Looks like I might need to put my C programmer’s hat > on... thanks for all the suggestions! IIRC, my prime number generator produced the first 2 billion primes in a few hours, so I agree this isn't undoable. http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htmYou'll need some way of accepting and storing the numbers that come out of this -- they might overrun your hard disk. One comment about all the algorithms delivering the next number with Y number of 1's: I'm pretty sure those work on the natural hardware size of numbers on a given computer, so unless your hardware has 40 bit integers, I don't think those will work, at least not without some modification. One more thing -- make sure your computer has plenty of cooling capacity. My prime number generator got my CPU up to 86 Celsius in maybe 5 minutes. SteveT Steve Litt                *  http://www.troubleshooters.com/Troubleshooting Training  *  Human Performance
Open this post in threaded view
|

## Re: Help with an algorithm

 On 25 May 2013 01:28, Steve Litt <[hidden email]> wrote: > On Fri, 24 May 2013 17:20:40 +1000 > Vaughan McAlley <[hidden email]> wrote: > >> On 24 May 2013 17:14, Michal Kottman <[hidden email]> wrote: >> > For this small test case, it generates 252 number. For your case, >> > C(25,40) == 40225345056, which is over 40 billion numbers. Would >> > you like to rethink your original problem? >> >> >> I have a Raspberry Pi that can chug away for a couple of weeks, so it >> might be doable. Looks like I might need to put my C programmer’s hat >> on... thanks for all the suggestions! > > IIRC, my prime number generator produced the first 2 billion primes in > a few hours, so I agree this isn't undoable. > > http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm> > You'll need some way of accepting and storing the numbers that come out > of this -- they might overrun your hard disk. > > One comment about all the algorithms delivering the next number with Y > number of 1's: I'm pretty sure those work on the natural hardware size > of numbers on a given computer, so unless your hardware has 40 bit > integers, I don't think those will work, at least not without some > modification. > > One more thing -- make sure your computer has plenty of cooling > capacity. My prime number generator got my CPU up to 86 Celsius in > maybe 5 minutes. > > SteveT > > Steve Litt                *  http://www.troubleshooters.com/> Troubleshooting Training  *  Human Performance > In the end I used the snoob function from http://www.hackersdelight.org/basics2.pdf adapted like this: unsigned long snoob(unsigned long x) {     unsigned long smallest, ripple, ones;     smallest = x & -x;     ripple = x + smallest;     ones = x ^ ripple;     ones = (ones >> 2)/smallest;     return ripple | ones; } I got over my fear of Xcode (the Raspberry Pi is only 32 bits so would have taken much longer), and my iMac chugged through the 40 billion numbers in a few hours. Luckily I wasn’t trying to store all the numbers, just find the most interesting. Working with 64-bit numbers is a bit trickier than 32-bit numbers... Vaughan
Open this post in threaded view
|

## Re: Help with an algorithm

 2013/5/25 Vaughan McAlley <[hidden email]>: > I got over my fear of Xcode (the Raspberry Pi is only 32 bits so would > have taken much longer), and my iMac chugged through the 40 billion > numbers in a few hours. Luckily I wasn’t trying to store all the > numbers, just find the most interesting. If you can define "interesting", it might be possible to devise a faster algorithm that generates only the interesting ones.
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by Vaughan McAlley-2 On Sat, 25 May 2013 14:33:18 +1000 Vaughan McAlley <[hidden email]> wrote: > On 25 May 2013 01:28, Steve Litt <[hidden email]> wrote: > > On Fri, 24 May 2013 17:20:40 +1000 [clip] > > One comment about all the algorithms delivering the next number > > with Y number of 1's: I'm pretty sure those work on the natural > > hardware size of numbers on a given computer, so unless your > > hardware has 40 bit integers, I don't think those will work, at > > least not without some modification. > > > > One more thing -- make sure your computer has plenty of cooling > > capacity. My prime number generator got my CPU up to 86 Celsius in > > maybe 5 minutes. > > > > SteveT > > > > Steve Litt                *  http://www.troubleshooters.com/> > Troubleshooting Training  *  Human Performance > > > > In the end I used the snoob function from > http://www.hackersdelight.org/basics2.pdf adapted like this: > > unsigned long snoob(unsigned long x) > { >     unsigned long smallest, ripple, ones; > >     smallest = x & -x; >     ripple = x + smallest; >     ones = x ^ ripple; >     ones = (ones >> 2)/smallest; >     return ripple | ones; > } > > I got over my fear of Xcode (the Raspberry Pi is only 32 bits so would > have taken much longer), and my iMac chugged through the 40 billion > numbers in a few hours. Luckily I wasn’t trying to store all the > numbers, just find the most interesting. > > Working with 64-bit numbers is a bit trickier than 32-bit numbers... > > Vaughan Vaughan, Where in the program did you tell it you're using 40 bit numbers? Or did you just quit when you reached 0000000000000000000000000000000000000001111111111111110000000000000000000000000 ? Did you find any evidence of your computer CPU overheating? What properties made some of these numbers more interesting than others? Did you use pipes like: ./find_fifteens | ./show_interesting.sh > interesting_numbers.txt These are the times I love computers. I might do this myself. Thanks, SteveT Steve Litt                *  http://www.troubleshooters.com/Troubleshooting Training  *  Human Performance
Open this post in threaded view
|

## Re: Help with an algorithm

 On most platforms these days unsigned long is 64 bits (however, note the "most"). On May 25, 2013, at 8:33 AM, Steve Litt <[hidden email]> wrote: > On Sat, 25 May 2013 14:33:18 +1000 > Vaughan McAlley <[hidden email]> wrote: > >> On 25 May 2013 01:28, Steve Litt <[hidden email]> wrote: >>> On Fri, 24 May 2013 17:20:40 +1000 > > [clip] > >>> One comment about all the algorithms delivering the next number >>> with Y number of 1's: I'm pretty sure those work on the natural >>> hardware size of numbers on a given computer, so unless your >>> hardware has 40 bit integers, I don't think those will work, at >>> least not without some modification. >>> >>> One more thing -- make sure your computer has plenty of cooling >>> capacity. My prime number generator got my CPU up to 86 Celsius in >>> maybe 5 minutes. >>> >>> SteveT >>> >>> Steve Litt                *  http://www.troubleshooters.com/>>> Troubleshooting Training  *  Human Performance >>> >> >> In the end I used the snoob function from >> http://www.hackersdelight.org/basics2.pdf adapted like this: >> >> unsigned long snoob(unsigned long x) >> { >>    unsigned long smallest, ripple, ones; >> >>    smallest = x & -x; >>    ripple = x + smallest; >>    ones = x ^ ripple; >>    ones = (ones >> 2)/smallest; >>    return ripple | ones; >> } >> >> I got over my fear of Xcode (the Raspberry Pi is only 32 bits so would >> have taken much longer), and my iMac chugged through the 40 billion >> numbers in a few hours. Luckily I wasn’t trying to store all the >> numbers, just find the most interesting. >> >> Working with 64-bit numbers is a bit trickier than 32-bit numbers... >> >> Vaughan > > Vaughan, > > Where in the program did you tell it you're using 40 bit numbers? Or > did you just quit when you reached > > 0000000000000000000000000000000000000001111111111111110000000000000000000000000 > > ? > > Did you find any evidence of your computer CPU overheating? > > What properties made some of these numbers more interesting than > others? Did you use pipes like: > > ./find_fifteens | ./show_interesting.sh > interesting_numbers.txt > > These are the times I love computers. I might do this myself. > > Thanks, > > SteveT > > Steve Litt                *  http://www.troubleshooters.com/> Troubleshooting Training  *  Human Performance >
Open this post in threaded view
|

## Re: Help with an algorithm

 >On most platforms these days unsigned long is 64 bits (however, note the "most"). That's a very unhelpful comment even if it were true, but it isn't. First, the sign hardly matters. Second, a C type's size is set in stone by a /compiler/, not a platform or CPU, as is struct alignment. Apple actually changed type sizes from one OSX version to the next. Whether by "most" you mean PCs and/or cellphones, then "most" define long as 32-bit (VisualC @ x64 or Clang/iOS @ x32). The C standards defines ranges, not fixed sizes. In retrospect is seems a bad idea but at the time there were all sorts of funky CPUs... we're lucky they were all binary. A long does currently occupy 8 bytes on *nix64, "mostly", but one can hardly use that probability as a basis for design. If you want fixed type sizes include "stdint.h" and use uint32_t, say, but watch those truncation warnings. Making assumptions about C type sizes or suggesting that eyeballing today's landscape is good enough to draw conclusions is year-2000 type shortsightedness and does a real disservice to portable code... or those who'll have to debug it down the road :) -- p
Open this post in threaded view
|

## Re: Help with an algorithm

 typo .. i meant "unsigned long long", which *is* typically 64-bits on any C99 compliant compiler. You are of course correct of the chaos in the meanings of the various integer widths, outside of those defined by stdint.h. I didn't suggest that anyone "eyeball" anything, and don't feel that my comment deserved such an ad hominem reply. On May 25, 2013, at 2:03 PM, petah <[hidden email]> wrote: >> On most platforms these days unsigned long is 64 bits (however, note the "most"). > > That's a very unhelpful comment even if it were true, but it isn't. > > First, the sign hardly matters. Second, a C type's size is set in stone by a /compiler/, not a platform or CPU, as is struct alignment. Apple actually changed type sizes from one OSX version to the next. Whether by "most" you mean PCs and/or cellphones, then "most" define long as 32-bit (VisualC @ x64 or Clang/iOS @ x32). The C standards defines ranges, not fixed sizes. In retrospect is seems a bad idea but at the time there were all sorts of funky CPUs... we're lucky they were all binary. A long does currently occupy 8 bytes on *nix64, "mostly", but one can hardly use that probability as a basis for design. > > If you want fixed type sizes include "stdint.h" and use uint32_t, say, but watch those truncation warnings. > > Making assumptions about C type sizes or suggesting that eyeballing today's landscape is good enough to draw conclusions is year-2000 type shortsightedness and does a real disservice to portable code... or those who'll have to debug it down the road :) > > -- p >
Open this post in threaded view
|

## Re: Help with an algorithm

 In reply to this post by petah On Sat, 25 May 2013 23:03:34 +0200 petah <[hidden email]> wrote: > >On most platforms these days unsigned long is 64 bits (however, note > >the "most"). > > That's a very unhelpful comment even if it were true, but it isn't. Come on, be nice, petah. SteveT Steve Litt                *  http://www.troubleshooters.com/Troubleshooting Training  *  Human Performance
Open this post in threaded view
|