[ruby-talk:12443] Re: ...and the challenge

>===== Original Message From Mathieu Bouchard <[e-mail]> =====
>On Mon, 12 Mar 2001, Benjamin J. Tilly wrote:
>> >(oh, btw. Ben's version takes over 3 times longer. i'm now testing with
>> >n=10**30 and using >/dev/null)
>> We have a winner.  If you want all of the Hamming numbers less
>> than a fixed bound, this appears fastest.
>
>I believe there are faster ways than that, but I don't want to go that
>far...

Well fastest of the submitted solutions. :-)

>> Theoretically the sort is k*log(k) where k is the number of
>> elements.  Practically if you raise n large enough for that to
>> matter, you will run out of memory on the machine. :-)
>
>the hamming function, where h(1)=1, is very close to
>
>proc{|k| 0.185*6.9893**(k**(1/3.0)) }
>
>which can be used as a reliable approximation for large values of k
>(add 2% for safety)

Ah, I didn't know that.  Well with that fact you should be
able to indeed do well.

>The size of the returned numbers is approximately s = 1.943*(k**(1/3.0)).
>Average comparison is in O(s) time. k*log(k) for the sort assumes O(1)
>comparisons. This sort is in O(k**(4/3.0) * log(k)). (well I think so)
>
>The amount of RAM used is in O(k**(4/3.0)). I haven't calculated how much
>yours take but it's much less...

Is there anything you don't know about the Hamming function? :-)

>> Of course if you just want to know what the thousandth element
>> in the Hamming sequence is, I believe that my approach will be
>> faster than an approach based on the above.
>
>I believe that too.

At last!  A point I can disagree on! :-)

>> Ditto if you are asked for the first thousand elements.
>
>Given the above approximation of the hamming function, the problem of
>computing the sequence up to element number k is equivalent to the one of
>computing the sequence up to value h(k). Therefore my solution will be
>faster.

I believe this, and I note that my solution, in order to give
you the thousandth element, has to calculate the first thousand
elements as well.  Therefore in both approaches calculating the
thousandth element is essentially the same problem as calculating
the first thousand, and since you are faster at that, you are
simply faster. :-)

Cheers,
Ben

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------