

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 40bit 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 40bit numbers looks like it will take half a year :) , even with a fairly quick calculation of Hamming weight using 14bit 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? Thank you, Vaughan


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 40bit 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 40bit numbers looks
> like it will take half a year :) , even with a fairly quick
> calculation of Hamming weight using 14bit 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 20bit segments. Each
segment will have 520 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,
KeinHong Man (esq.)
Kuala Lumpur, Malaysia


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, left1) num[position] = '0'
step(position + 1, left) end end step(1, ones)
end) end
To 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?


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!


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
autogenerated lookup table for 8 bit combinations, it loops
several loops to join the bits together.

Cheers,
KeinHong Man (esq.)
Kuala Lumpur, Malaysia


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


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 64bit numbers is a bit trickier than 32bit numbers...
Vaughan


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.


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 64bit numbers is a bit trickier than 32bit 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


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 64bit numbers is a bit trickier than 32bit 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
>


>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 32bit (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 year2000 type shortsightedness and does a real disservice to portable code... or those who'll have to debug it down the road :)
 p


typo .. i meant "unsigned long long", which *is* typically 64bits 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 32bit (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 year2000 type shortsightedness and does a real disservice to portable code... or those who'll have to debug it down the road :)
>
>  p
>


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


>typo .. i meant "unsigned long long", which *is* typically 64bits on any C99 compliant compiler.
>
>I didn't suggest that anyone "eyeball" anything, and don't feel that my comment deserved such an ad hominem reply.
Hey make such a typo in actual code and all hell breaks loose :)
Sorry I didn't mean to be pompous or selfrighteous; I read your earlier comments about Java having less flimsy standards than C which isn't exactly fair, C was initially meant to be "portable assembler" decades before Java was born. Your "most" adds insult to C standards' "at least N bits" injury.
I was also recently bitten in the ass by a bug due to shifting sizeof(long) across compilers, platforms AND OS versions so couldn't let this one pass... I'd rather have learned this from someone else's buttpain rather than experience it myself.
("nurse! I need another pillow!")
 p
>
>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 32bit (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 year2000 type shortsightedness and does a real disservice to portable code... or those who'll have to debug it down the road :)
>>
>>  p
>>
>
>
>


On 26 May 2013 01:33, Steve Litt < [hidden email]> wrote: >> On 25 May 2013 01:28, Steve Litt < [hidden email]> wrote:
> Vaughan, > > Where in the program did you tell it you're using 40 bit numbers? Or > did you just quit when you reached > > 0000000000000000000000000000000000000001111111111111110000000000000000000000000
> > ? > Yes, I just checked that the number was over 2^40. > Did you find any evidence of your computer CPU overheating? No, my 2008 iMac coped fine. It got a bit warm, but not as warm as an equivalent time playing Starcraft would (not that I have that kind of time to spare these days). It’s nearly winter here in Australia.
> > What properties made some of these numbers more interesting than > others? Did you use pipes like: > > ./find_fifteens  ./show_interesting.sh > interesting_numbers.txt >
I’m laying an area of pavers 8 wide by 5 down, with dark and light pavers available. I wanted to do an ‘interesting’ pattern... being fond of the golden ratio and noticing 8 & 5 are Fibbonaccci numbers, I thought I could encode a 40bit number that when read from the (right) side, is the golden ratio away from when it is read from the bottom.
So what I have found is: + < back fence
 01110111  01000100  00101000
 10100000  10100010
is 0x774428a0a2... when read looking from the right you get:
11000 00011 11101 00001 00100 00011 10001 00001
or 0xc0fa120e21
print(0xc0fa120e21 / 0x774428a0a2) gives you the golden ratio to 11 decimal places, which is the most interesting to me :)
You’ll notice I’m using a Hamming weight of 15 instead of 25. Either way was fine if the ones and zeros relate by roughly the golden mean.
> ./find_fifteens  ./show_interesting.sh > interesting_numbers.txt
> These are the times I love computers. I might do this myself. >
No, I just printed out the best result as it appeared. But you are correct... computers can be a lot of fun :)
> Thanks,
> > SteveT >
Cheers,
Vaughan


2013/5/26 Vaughan McAlley < [hidden email]>:
> I’m laying an area of pavers 8 wide by 5 down, with dark and light pavers
> available. I wanted to do an ‘interesting’ pattern... being fond of the
> golden ratio and noticing 8 & 5 are Fibbonaccci numbers, I thought I could
> encode a 40bit number that when read from the (right) side, is the golden
> ratio away from when it is read from the bottom.
Aha! We have a definition of "interesting". This task can be done with
much less computation.
Try all possible first rows. For each, fill the remaining elements
with all zeros and all ones. Multiply the number by phi. If the smallest
result is greater than 2^40, throw away that row. Otherwise, convert
those smallest and largest values to 40 bits. They'll agree to 7 bits,
so that gives you the first column. If it disagrees with the first row
where they cross, throw away that first row. Otherwise, you have 7 bits
of the second row to try. Etc.

