Hamming numbers: Difference between revisions
edit related tasks; some small c/e in Haskell
(→Explicit multiples reinserting: explicitly show the empirical orders of growth for the leftover queue) |
(edit related tasks; some small c/e in Haskell) |
||
Line 17:
;Related tasks:
* [[Humble numbers]]
* [[N-smooth numbers]]
Line 5,232 ⟶ 5,233:
===Avoiding generation of duplicates===
The classic version can be sped up quite a bit (about twice, with roughly the same [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical orders of growth]) by avoiding generation of duplicate values in the first place:
<lang haskell>hammings :: () -> [Integer]
hammings() = 1 : foldr u [] [2,3,5] where
Line 5,250 ⟶ 5,251:
===Explicit multiples reinserting===
This is a common approach which explicitly maintains an internal buffer of <math>O(n^{2/3})</math> elements, removing the numbers from its front and reinserting their 2- 3- and 5-multiples in order. It overproduces the sequence, stopping when the ''n''-th number is no longer needed instead of when it's first found. Also overworks by maintaining this buffer in total order where just heap would be sufficient. Worse, this particular version uses a sequential list for its buffer. That means <math>O(n^{2/3})</math> operations for each number, instead of <math>O(1)</math> of the above version (and thus <math>O(n^{5/3})</math> overall). Translation of [[#Java|Java]] (which does use priority queue though, so should have ''O''‍ ‍(''n''‍ ‍log''n'') operations overall). Uses <code>union</code> from the "classic" version above:
<lang Haskell>
iterate (\(_ , (a:t)) -> (a, union t [2*a,3*a,5*a])) (0, [1])</lang>
{{out}}
<lang Haskell>> take 20 $ map fst $
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
> take 2 $ map fst $
[2125764000,2147483648]
> mapM_ print $ take 10 $
(1,[2,3,5])
(2,[3,4,5,6,10])
Line 5,270 ⟶ 5,272:
(12,[15,16,18,20,24,25,27,30,36,40,45,50,60])
> map (length . snd . head .
[402,638,1007,1596]
| |||