Hamming Numbers
August 30, 2011
The sequence of Hamming numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, … (A051037) consists of all numbers of the form 2i·3j·5k where i, j and k are non-negative integers. Edsger Dijkstra introduced this sequence to computer science in his book A Discipline of Programming, and it has been a staple of beginning programming courses ever since. Dijkstra wrote a program based on three axioms:
Axiom 1: The value 1 is in the sequence.
Axiom 2: If x is in the sequence, so are 2 * x, 3 * x, and 5 * x.
Axiom 3: The sequence contains no other values other than those that belong to it on account of Axioms 1 and 2.
.
Your task is to write a program to compute the first thousand terms of the Hamming sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
I wrote a Haskell version of Python’s test of using lazy evaluation to generate them; as it turns out, it’s the same as the SRFI-41 version.
Since I’m new to Haskell, I probably didn’t find the most elegant solution (and suggestions are welcome), but lazy evaluation is kind of amazing.
Looks like I had some redundant parentheses in my definition of merge, according to hlint. Apologies.
Re the imperative version, I think it is nicer to omit the 0 that does not belong to the sequence and simply produce a 0-based sequence of n elements:
(Cut-and-paste from my editor window to be safer against silly typos. I called my translation of Dijkstra’s code aq.)
Jussi: I tend to add a useless element to the beginning of arrays when porting code from languages that base arrays at 1 instead of 0. It’s mostly harmless, and saves a lot of x+1 and x-1 statements mapping between the two formats. I agree it’s ugly, but only a little bit. Where it actually matters, I do it right.
Here’s a shortish but quite efficient lazy Clojure version:
(defn hammings [initial-set]
(let [v (first initial-set)
others (rest initial-set)]
(lazy-seq
(cons
v
(hammings (into (sorted-set (* v 2) (* v 3) (* v 5)) others))))))
(take 1000 (hammings #{1}))
Runs in about 0.07 ms for the first 1000 hamming numbers on my machine.
Here’s my clojure solution. More details at my blog.
hemming = [1] ++ concatMap (\ x -> [x*2, x*3, x*5]) hemming
first1k = sort . take 1000 $ hemming
My Haskell variant
Dijkstra advocated 0-based indexing, so I think his algorithm in the chapter may actually be intended to be 0-based. It is hard to tell for sure. However, his initialization of aq to (1 1) is funny either way when only one 1 is meant to remain in the result, and the assignments to ik, xk seem to need to be either parallel or swapped when I implement it. Below is a 0-based version with parallel assignments. For example, (set*! (x y) y x) swaps x and y. (Originally I had tail-recursion instead of assignments, and I did not even notice that the second assignments in Dijkstra depend on the first ones.)
Cheers.
@Philipp: I like the brevity of your Haskell answer, but it seems to include a lot of repeats; as a Haskell newbie, I couldn’t figure out a way to remove them easily. Any ideas?
nub
Continuing to attempt to become more familiar with Haskell. Here is what I came up with.
In case you’re curious, my solution is in Lazy Racket :-)
Ended up playing with my answer some more while waiting for some other code to compile. I like how this one better.
HammingNumbers.java
hamm.go
@programmingpraxis: I’ve tried throwing
nub
into the solution, but it either (1) comes aftertake 1000
, in which case there are no longer 1000 entries, or (2) comes before it, and the program just hangs. I am not very adept in Haskell :-(Hamming number generator in Python 3.
Follows directly from the definition. Yield 1, then yield 2*, 3* and 5* a number in the list. It’s lazy too.
from heapq import merge
from itertools import tee
def hamming_numbers():
last = 1
yield last
a,b,c = tee(hamming_numbers(), 3)
for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)):
if n != last:
yield n
last = n
x = list(islice(hamming_numbers(),1000))
print(x[:10], x[-5:])
# output -> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] [50331648, 50388480, 50625000, 51018336, 51200000]
This time with proper formating:
Nothing magical here…
Inelegant but fast to write in Python:
my C++ solution. I’m disappointed that it takes so long for my implementation to calculate the sequence. (especially since someone got it in less thana tenth of a second.)Can someone tell me where I can improve the code?
http://codepad.org/WhHDxJAZ
The suggested solution makes n trips through a single loop, at each iteration calculating a minimum of three integers, performing three
if
tests comparing two integers at each iteration, and making a single addition and a single multiplication.Your code has 5
for
loops, two of them withif
tests inside them, and 1while
loop containing anif
which has a nestedif
inside it. And the inner loop of your code performs amodulo
operation (a very expensive operation) and a compare fordivisorSize
×sequenceIndex
iterations.And you forgot the 1 that starts the sequence.
By the way, the suggested solution runs in a thousandth of a second, not a tenth of a second:
> (define x #f)
> (time (set! x (hamming 1000)))
(time (set! x ...))
no collections
1 ms elapsed cpu time
1 ms elapsed real time
12048 bytes allocated
> (vector-ref x 1000)
51200000
To improve your code, you should follow the suggested solution.
I’m sorry if that’s a little bit harsh. I’ll be happy to look at your improved solution.
Phil
[…] compute the first thousand terms of the Hamming sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments […]
[…] This question is copyright of programmingpraxis.com. Click here to see the original […]
Here is my C implementation!
http://codepad.org/ilubfEfd
Thanks Phil for a review of my code. I now see how inefficient it is and was working on a revision but I don’t think I can make my algorithm as efficient as Supriya Koduri’s, to whom I want to ask “what train of thought allowed him to create such an elegant solution?”.
ruby solution : http://codepad.org/b87tK8qQ
Another solution based upon Dijkstra’s paper:
cosmin’s solution in Go: http://play.golang.org/p/qD1Tqntcy5
The results of the cosmin’s solution in Go posted by glnbrwn 12Dec2012 in Go do not match.
Python version posted October 30, 2012 by cosmin results are:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, …
Go when executed at the link given above results in:
[1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64
Go is missing 10, 15, 20, 25, 30 when executing it. Multiples of 5 are not getting added to the result.