[CentralOH] 2017-10-20 燕月 Lunch Placemat Scribbles: tcl braces versus python; fibonacci versus hamming

[Joe Knapp]

On Fri, Oct 20, 2017 at 10:24 PM, <jep200404 at columbus.rr.com> wrote:

>
> ############################################################
> ###################
>
> making hamming numbers
>
> wp:Smooth number
> wp:Hamming numbers
> wp:Richard Hamming
>

One to add is:

wp:Regular number

That deals with 5-smooth numbers specifically. I think the term was coined
by someone studying Babylonian (base 60) mathematics, which only allows
division by such "regular" numbers. They also come up in music theory
(intervals between notes in the 'just' tuning scheme).


> Second version tries to avoid duplication,
> so is much faster and uses much much less memory.
> Seems to be fast enough for the 1000000th hamming number.
> It even seems to be correct.
> ...
>     doj at sbc:~/20171026$ time ./ham2.py 1000000
>     1000000 519312780448388736089589843750000000000000000000000000000000
> 000000000000000000000000
>
>     real    8m31.437s
>     user    8m27.944s
>     sys     0m2.252s
>

Not sure of the state of the art, but check out this old Dr. Dobbs article
(2008):

http://www.drdobbs.com/architecture-and-design/hamming-problem/228700538

They report a Lisp version that took 900 seconds to generate 127 million
Hamming numbers.

A lot people skip trying to calculate the entire sequence up to the nth
Hamming number, instead just finding the nth number alone, using an
algorithm described in the Dr, Dobbs article .

This page:

https://rosettacode.org/wiki/Hamming_numbers

...has a lot of implementations in different languages, but most are of the
"just give the nth number" variety.

Joe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20171021/1fc30e7e/attachment.html>