Haskell Hamming Sequence Logic

Question

It was suggested I place this code here. I had posted it on StackOverflow for a kind of review.

I have tried to generate Hamming numbers using primes but the speed of the generation slows the higher the number generated and the prime list grew proportionately. I then started to find if a number could be factored down to 2,3 or 5. This was faster but still far away from linear.

Then I found in Excel that a candidate number when evenly divided by one of 2,3 or 5 can be found in previously generated hamming numbers if it is itself a Hamming number.

I thought this approach would result in faster Hammond number generation.

I have played with generating the last of a large set of Hamming numbers using my standard methods. Once the final set is generated all previous Hammings can selectively be extracted from it. The last set just takes to long to generate even though once it is, the speed becomes linear. I just need a faster way to generate any Hamming list.

I do not know if anyone has ever tried to exploit the fact that each successive candidate number can be tested for Hamming status by dividing it by one of 2,3 or 5 and testing if the quotient is a member of the Hamming list generated to that point.

The function takes two parameters, a seed list of (reversed) Hamming numbers less than 10 and a candidate list of any size. I prefer to us a list of [2,3,5] multiples I call base

base = scanl (\b a -> a+b) 2 $ cycle [1,1,1,1,2,1,1,2,2,1,1,2,2,1,1,2,1,1,1,1,2,2]

hamx ls (x:xs) 
   | even x        && elem (div x 2) ls = hamx (x:ls) xs
   | mod  x 3 == 0 && elem (div x 3) ls = hamx (x:ls) xs
   | mod  x 5 == 0 && elem (div x 5) ls = hamx (x:ls) xs
   | null xs = ls
   | otherwise = hamx ls xs

I tried filter and any and others in place of elem. The list generates in reverse. The elem finds Hamming matches faster from the bottom and new Hamming numbers appear also at the bottom. So, the bottom is the top.

I am now working on the 2,3,5 Hamming multiples used in other algorithms. I know how not to generate duplicates. I might be able to integrate these select multiples into the above code. For example, the select list will only use 15 multiples of 5 in 6,103,515,625. All of the 10s are already in the 2 multiples and many 5 multiples are found in 3 multiples. The only 3 multiples needed are from odd Hamming numbers. All 2 multiples are needed.

Answer 1

The main problem is that elem traverses list and that is slow. It is better to use Data.Set or HashMap as this data structures allow sub-linear membership checking.

import qualified Data.Set as Set

hamx :: [Integer] -> [Integer] -> [Integer]
hamx ls = reverse . Set.toList . loop (Set.fromList ls)
  where
    loop res [] = res
    loop res (x:xs)
     | even x        && Set.member (div x 2) res = loop (Set.insert x res) xs
     | mod  x 3 == 0 && Set.member (div x 3) res = loop (Set.insert x res) xs
     | mod  x 5 == 0 && Set.member (div x 5) res = loop (Set.insert x res) xs
     | otherwise = loop res xs

Or a bit shorter (but less readable) version:

import Data.List (foldl')
import qualified Data.Set as Set

hamx :: [Integer] -> [Integer] -> [Integer]
hamx ls = reverse . Set.toList . loop (Set.fromList ls)
  where
    loop = foldl' (\res x -> if predicate res x then Set.insert x res else res)
    predicate res x = any (\y -> mod x y == 0 && Set.member (div x y) res) [2, 3, 5]

---

Using IntSet instead of Set is several times faster, but Daniel Fischer's solution is still several orders of magnitude faster.

I put a project with criterion benchmark here.

Answer 2

A review of a computational code starts with reviewing the algorithm it uses.

Here's a kicker. Your algorithm in exponential, or worse, whereas the well-known "classic" algorithm is linear.

This means your code is spectacularly slower, incomparably slower.

Why are your algorithm exponential (at least)? It is because in order to produce n first Hamming numbers you are testing all the natural numbers below the nth Hamming number. But the nth Hamming number is on the order of ~ exp (n^1/3) in magnitude, according to Wikipedia.

The "classic" algorithm is linear in n. So is the improved algorithm (used in the two older answers on the SO entry where you've posted your code), which is faster than the "classic" one by about a constant factor of 2. I think anyone will agree that exponential algorithm is no improvement to the linear, quite the contrary.

Since the algorithm in your question is so abominably slow, any other considerations about your code will pale in comparison.