Help with an algorithm

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

Help with an algorithm

Vaughan McAlley-2
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" 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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

KHMan
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


Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Finn Wilcox-2
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


Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Steven Johnson
On Fri, May 24, 2013 at 1:09 AM, Finn Wilcox <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Michal Kottman-2
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)
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?
Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Vaughan McAlley-2
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!

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

KHMan
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


Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Steve Litt
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.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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Vaughan McAlley-2
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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Dirk Laurie-2
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.

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Steve Litt
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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Tim Hill
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
>


Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

petah
>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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Tim Hill
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
>


Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Steve Litt
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

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

petah
In reply to this post by Tim Hill
>typo .. i meant "unsigned long long", which *is* typically 64-bits 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 self-righteous; 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 butt-pain 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 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
>>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Vaughan McAlley-2
In reply to this post by Steve Litt
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 40-bit 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
Reply | Threaded
Open this post in threaded view
|

Re: Help with an algorithm

Dirk Laurie-2
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 40-bit 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.