Recall that a Hamming Number is a positive integer which has no prime factor other than 2, 3 and 5, and we want to find the first so-many [say, 1000] Hamming numbers.
Exercise 1 was to write a straightforward computer program for this by direct testing of each number in turn:
[tidying this up to produce neater or more informative output is left as an exercise]. All we are doing here is extracting all possible factors of 2, 3 and 5 from [a copy of] the current number; if this reduces the copy to 1, then we have found another Hamming number. This clearly satisfies two of the criteria for an algorithm; it's deterministic and it is correct [the guts of the program being taken directly from the definition]. Does it terminate? The three inner loops must, because every time around, the positive integer i is reduced by a factor of at least two. The outer loop must, because it counts the number of Hamming numbers found, and the 1000th Hamming number is certainly less than 21000 [actually, much less -- luckily!].count = 0, current = 0 while count < 1000 do current = current + 1 i = current while i mod 2 = 0 do i = i/2 endwhile while i mod 3 = 0 do i = i/3 endwhile while i mod 5 = 0 do i = i/5 endwhile if i = 1 then count = count + 1, print current endif endwhile
Exercise 2 was to implement the much more efficient technique suggested in the problem class:
[tidying the printing, etc., and other minor optimisations, again left as an exercise]. The three inner loops could just as well be ifs rather than whiles, and could just as well test for equality with least; the rationale for the form given is discussed by Dijkstra, but it's really pretty feeble.dim H[1000] found = 1, H[1] = 1 # the first HN is 1 fing2 = 1, fing3 = 1, fing5 = 1 # H[1] is where we start our three fingers while found < 1000 do least = 2×H[fing2] if least > 3×H[fing3] then least = 3×H[fing3] endif if least > 5×H[fing5] then least = 5×H[fing5] endif # least is the smallest candidate, and so the next HN found = found + 1 H[found] = least while 2×H[fing2] <= least do fing2 = fing2 + 1 endwhile while 3×H[fing3] <= least do fing3 = fing3 + 1 endwhile while 5×H[fing5] <= least do fing5 = fing5 + 1 endwhile endwhile for i = 1 to 1000 do print H[i] endfor
Note that, quite typically, we have turned a simple program into an efficient program at the expense of clarity and transparency. But it is much easier to take a simple program that works, analyse its efficiency, and turn it into an efficient program that works than to take an `efficient' program that doesn't work and `debug' it until it does. [What does it mean for a buggy program to be efficient? Anyone can write a program that gives wrong answers quickly!]
G12FCO home page.
Next discussion.
Problem class.