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 = 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
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.