Hamming numbers: Difference between revisions
→Explicit multiples reinserting: explicitly show the empirical orders of growth for the leftover queue
GordonBGood (talk | contribs) (→{{header|Pascal}}: correct "slow" reference and add enough BigInt to print the millionth value...) |
(→Explicit multiples reinserting: explicitly show the empirical orders of growth for the leftover queue) |
||
Line 5,252:
<lang Haskell>hamm n = drop n $ iterate (\(_,(a:t))-> (a,union t [2*a,3*a,5*a])) (0,[1])</lang>
{{out}}
<lang Haskell>
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
[2125764000,2147483648]
(1,[2,3,5])
(2,[3,4,5,6,10])
Line 5,270:
(12,[15,16,18,20,24,25,27,30,36,40,45,50,60])
[402,638,1007,1596]
Runs too slowly to reach 1,000,000, with empirical orders of growth above ''~''‍ ‍(''n''‍ ‍<sup>1.7</sup>‍ ‍) and worsening. Last two lines show the internal buffer's length for several sample ''n''‍ ‍s.▼
> map (logBase 2) $ zipWith (/) =<< tail $ [402,638,1007,1596]
[0.67,0.66,0.66]</lang>
▲Runs too slowly to reach 1,000,000, with empirical orders of growth above ''~''‍ ‍(''n''‍ ‍<sup>1.7</sup>‍ ‍) and worsening. Last two lines show the internal buffer's length for several sample ''n''‍ ‍s, and its [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth ''empirical'' orders of growth] which strongly support the <math>O(n^{2/3})</math> claim.
===Enumeration by a chain of folded merges===
| |||