Saturday, February 14, 2009

Hamming numbers

The set of Hamming numbers H is defined recursively. 1 is in H. The numbers 2h, 3h, 5h are in H, if h is a number contained in H. The first few hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, ... Dijkstra put the problem of computing efficiently the hamming numbers. What is your proposal?
Pubblicato da a
Reazioni: 

1 comment:

  1. A first naive solution is to start with the set H_0 = {1, 2, 3, 5 } then build H_i = 3 * h_{i-1}, h_{i-1} \in H_{i-1}, i>0. Obviously, we generate multiple duplicates that we can t"eliminate" with a post-processing sort operation.

    What is wrong with that?

    ReplyDelete

Subscribe to: Post Comments (Atom)