Re: Help with an algorithm

[Vaughan McAlley <vaughan@...>]

On 25 May 2013 01:28, Steve Litt <slitt@troubleshooters.com> wrote:
> On Fri, 24 May 2013 17:20:40 +1000
> Vaughan McAlley <vaughan@mcalley.net.au> wrote:
>
>> On 24 May 2013 17:14, Michal Kottman <michal.kottman@gmail.com> 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