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

[Joe Knapp]

Re: Hamming numbers

I tried a somewhat different approach to generating the Hamming sequence,
based on classifying the intervals from one number to the next, i.e., the
interval from 1 to 2 is 2/1 (2.0), from 2 to 3 is 3/2 (1.5)... from 1536
(the 100th Hamming number) to 1600 is 5^2/2^3 (1.08). It turns out that
there is only a very limited number of discrete intervals from one Hamming
number to the next in quite a large range. E.g., for the first 1.59
trillion Hamming numbers there are only 119 different intervals, each
identified by an i,j,k triple where i,j,k are positive or negative
integers. The example above for the 100th-101st interval is {-3,0,2}.

As the Hamming number goes up the interval to the next one tends to go
down, which makes sense because there are more possibilities that some
combination of i,j,k will result in a fraction close to 1.0.

Anyway, here's a C header file with the table in the struct hamtab[]:

https://github.com/jmknapp/hammingnumbers/blob/master/hamseq.h

So given a Hamming number with exponents {i,j,k}, to find the next number
just look through the table for the first entry having {p2,p3,p5} such that
i+p2 > 0 && j+p3 > 0 && i+p5 > 0 (since multiplication would just be adding
the exponents). Voila! At most 119 entries have to be checked and only
short int additions and comparisons are involved.

That goes pretty fast, but a significant speedup (about a factor of 4 or 5)
can come from not necessarily searching the table from the 0th index. The
second struct in the header file shows a successor table (succtab[]) that
has lists of all possible successors of each entry (just found empirically
by running through the sequence once).

This C code along with the header file implements the algorithm:

https://github.com/jmknapp/hammingnumbers/blob/master/hamseq.c

compiled with: gcc -std=c99 -O3 hamseq.c -o hamseq

The attached plot shows the execution time on an i7-2600 3.4GHz machine--it
takes about 2 seconds to generate the first 100 million Hamming numbers and
several hours for the first trillion.

I was thinking of porting this to python to see how it would go, but have a
learning curve there. Would be a lot slower except maybe with pypy?

Joe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20171023/fc121b44/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ohamm.png
Type: image/png
Size: 16961 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/centraloh/attachments/20171023/fc121b44/attachment-0001.png>