fork(16) download
  1. {-# OPTIONS_GHC -O2 #-}
  2. {-# LANGUAGE BangPatterns #-}
  3.  
  4. -- rosettacode.org/wiki/Hamming_numbers#Haskell cf. ideone.com/k8PU3
  5.  
  6. module Main where
  7. import Data.List
  8. import Data.Function
  9.  
  10. hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming
  11. where
  12. union a@(x:xs) b@(y:ys) = case compare x y of
  13. LT -> x : union xs b
  14. EQ -> x : union xs ys
  15. GT -> y : union a ys
  16.  
  17. main =
  18. do
  19. s <- getLine
  20. case s of
  21. "a" -> do print $ take 20 hamming
  22. print (hamming !! 1690, hamming !! 1691)
  23. print $ hamming !! (1000000-1) -- 9 MB: releases the prefix of the list
  24. "b" -> do
  25. print $ hamming !! (1000000-1)
  26. print $ hamming !! 1000000 -- 77 MB: does NOT release the prefix (is needed twice)
  27. "c" -> do
  28. mapM_ print $ take 2 $ drop 999999 hamming -- 9 MB: used once, prefix gc-d
  29. "d" -> do
  30. let (r,t) = nthHam (1000000) -- 4 MB: stores upper band only
  31. (r2,t2) = nthHam (1000001)
  32. print (t,trival t)
  33. print (t2,trival t2)
  34. _ -> do -- 10^8: 4 MB 0.27 sec
  35. let (r,t) = nthHam (read s) -- 10^9: 6 MB (-4=2) 1.42 sec ~n^0.7
  36. print (t, showLogVal 2 r) -- 10^10: 14 MB (-4=10) 7.20 sec ~n^0.7
  37. -- print (case t of (i,j,k)-> 2^i*3^j*5^k)
  38.  
  39. showLogVal base logval = show (10**y) ++ "E+" ++ show x
  40. where (x,y) = properFraction (logBase 10 base * logval)
  41.  
  42. -- directly find n-th Hamming number (base 1, from 2), in ~ O(n^{2/3}) time
  43. -- by Will Ness, based on "top band" idea by Louis Klauder from DDJ discussion
  44. -- drdobbs.com/blogs/architecture-and-design/228700538
  45.  
  46. ln2 = log 2; ln3 = log 3; ln5 = log 5
  47. logval (i,j,k) = fromIntegral i*ln2 + fromIntegral j*ln3 + fromIntegral k*ln5
  48. trival (i,j,k) = 2^i * 3^j * 5^k
  49. estval n = (6*ln2*ln3*ln5* fromIntegral n)**(1/3) -- estimated logval
  50. rngval n
  51. | n > 500000 = (1.698 , 0.0050) -- empirical
  52. | n > 50000 = (1.693 , 0.0100) -- estimation
  53. | n > 500 = (1.66 , 0.0500) -- correction
  54. | n > 1 = (1.56 , 0.2000) -- (dist,width)
  55. | otherwise = (1.56 , 0.4000)
  56.  
  57. -- estval(n) = log (M[n]) = ln2 * logBase 2 (M[n])
  58.  
  59. lb3 = logBase 2 3; lb5 = logBase 2 5 -- lb3 == log 3/log 2, lb5 == log 5/log 2
  60. logval2 (i,j,k) = fromIntegral i + fromIntegral j*lb3 + fromIntegral k*lb5
  61. estval2 n = (6*lb3*lb5* fromIntegral n)**(1/3) -- estimated logval **Base 2**
  62. rngval2 n
  63. | n > 500000 = (2.4496 , 0.0076 ) -- empirical
  64. | n > 50000 = (2.4424 , 0.0146 ) -- estimation
  65. | n > 500 = (2.3948 , 0.0723 ) -- correction - base 2
  66. | n > 1 = (2.2506 , 0.2887 ) -- (dist,width)
  67. | otherwise = (2.2506 , 0.5771 )
  68.  
  69. nthHam n -- n: 1-based 1,2,3...
  70. | w >= 1 = error $ "Breach of contract: (w < 1): " ++ show (w)
  71. | m < 0 = error $ "Not enough triples generated: " ++ show (c,n)
  72. | m >= nb = error $ "Generated band is too narrow: " ++ show (m,nb)
  73. | True = res
  74. where
  75. (d,w) = rngval2 n -- correction dist, width
  76. hi = estval2 n - d -- hi > logval2 > hi-w
  77. (c,b) = foldl_ -- total count, the band
  78. (\(!c,!b) (i,t) -> case t of [] -> (i+c,b)
  79. [x] -> (i+c,x:b))
  80. (0,[]) -- (sum *** concat) . unzip $
  81. [ ( i+1, -- total triples w/ this (j,k)
  82. [ (r,(i,j,k)) | frac < w ] ) -- store it, if inside band
  83. | k <- [ 0 .. floor ( hi /lb5) ], let p = fromIntegral k*lb5,
  84. j <- [ 0 .. floor ((hi-p)/lb3) ], let q = fromIntegral j*lb3 + p,
  85. let (i,frac) = pr (hi-q) ; r = hi - frac -- r = i + q
  86. ] where pr = properFraction -- pr 1.24 => (1,0.24)
  87. (m,nb) = ( fromIntegral $ c - n, length b ) -- m 0-based from top, |band|
  88. (s,res) = ( sortBy (flip compare `on` fst) b, s!!m ) -- sorted decreasing, result
  89. foldl_ = foldl'
Success #stdin #stdout 0.02s 4896KB
stdin
1000000

1000000        0.01s-5.0MB     ((55,47,64),"5.193127804483973E+83")
1000000000     1.08s-5.9MB     ((1334,335,404),"6.21607575556559E+843")

c  0.85s-8.0MB
a  0.87s-8.0MB 
stdout
((55,47,64),"5.193127804483973E+83")