1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. Unfortunately, this question is incomplete. To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. Questions should include a description of what the code does. A short description of the Hamming sequence will ease the life of reviewers and make it more likely that your code gets properly reviewed. \$\endgroup\$ – Zeta Dec 17 '18 at 16:24
  • \$\begingroup\$ see this for a related discussion, of the code based on the idea not unlike the one in your question. \$\endgroup\$ – Will Ness Dec 23 '18 at 13:30
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ha, I had my logic in a foldl', too but with elem also but also with a function to divide the candidate numbers by a select factor of one of [2,3,5]. \$\endgroup\$ – fp_mora Dec 17 '18 at 22:30
  • \$\begingroup\$ The top rendition is faster. Neither require reverse because res is not constructed in reverse. My result ls was constructed in reverse for speed of ':' vs. ++ and for search from the end of the list which was closer to a match. \$\endgroup\$ – fp_mora Dec 18 '18 at 3:00
  • \$\begingroup\$ I copy-pasted your code from Github to my GHCi and ran hamx n with n in [200,300,400,500] and each time the run time increased three-fold. This means the algorithm is exponential in n. The other, classic, algo is of course linear, so there is no one speedup factor to give between the two (re "several orders of magnitude"). It simply does not exist. Saying that one code is X times faster than the other implies that both are in the same Theta complexity class. --- (a side note: I'd use a descriptive name for predicate, like keep.) \$\endgroup\$ – Will Ness Dec 19 '18 at 7:50
0
\$\begingroup\$

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 (n1/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.

\$\endgroup\$
  • \$\begingroup\$ Math is a tautology. That in no way detracts from it as the highest endeavor. The converse of “exponential algorithm is no improvement” is a tautology but benefits likewise. My motivation for writing code is at odds with yours and CR. Subsets of Hamming numbers can be calculated. There is a relationship to primes and algebras. All numbers in the 10^n set are contained in 10^n+1 set by taking the 0 (mod 10)s and dividing by 10. This is part of my interest. \$\endgroup\$ – fp_mora Dec 21 '18 at 16:06
  • \$\begingroup\$ To late editing, *all numbers in 10^(0-n) are contained in 10^n+1 \$\endgroup\$ – fp_mora Dec 21 '18 at 16:18
  • 1
    \$\begingroup\$ yes, you're right, math doesn't care for speed, only correctness. Fibonaccis are Fibonaccis whether defined with a linear, logarithmic, or exponential code. but in programming we also have speed and memory space considerations, and we generally prefer the faster solution, and search for it diligently. :) \$\endgroup\$ – Will Ness Dec 26 '18 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.