Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import Data.List
import Text.Printf
import Numeric
tolerance :: Double
tolerance = 1e-2
e :: Double
e = 2.718281828
times :: [Double]
times = [100, 100*60, 100*60*60, 100*60*60*24,
100*60*60*24*30, 100*60*60*24*30*12,
100*60*60*24*30*12*100]
inverseNLgN :: Double -> Double
inverseNLgN x = x / lambertW(x)
factorials = scanl (*) 1 [1..]
factorial = (factorials !!)
inverseNFactorial :: Double -> Double
inverseNFactorial x = fromIntegral $ f 1 x
where f i x | (factorial i) > x = i - 1
| otherwise = f (i + 1) x
lambertW :: Double -> Double
lambertW x =
recursiveLambertW ((log x) - (log (log x))) x
where recursiveLambertW previous x =
case abs (previous - new) < tol of
True -> new
False -> recursiveLambertW new x
where new = previous -
(previous * ew - x) /
(ew + previous * ew)
ew = e ** previous
inverse_funcs :: [(String, Double -> Double)]
inverse_funcs = [("lg(n)", \x -> e ** x),
("sqrt(n)", (** 2)),
("n", id),
("n lg(n)", inverseNLgN),
("n^2", (** 0.5)),
("n^3", (** 0.33)),
("2^n", \x -> log x/log 2),
("n!", inverseNFactorial)]
main :: IO ()
main = do
putStrLn $ "<table><thead><tr>" ++
"<th>complexity</th>" ++
"<th>1 second</th>" ++
"<th>1 minute</th>" ++
"<th>1 hour</th>" ++
"<th>1 day</th>" ++
"<th>1 month</th>" ++
"<th>1 year</th>" ++
"<th>1 century</th>" ++
"</tr></thead><tbody>"
mapM_ printRow inverse_funcs
putStrLn "</tbody></table>"
where printRow (name, f) = do
putStr "<tr>"
mapM_ printCell $
[name] ++ map format [f t|t<-times]
putStrLn "</tr>"
format x =
showEFloat (Just 2)
(fromIntegral $ floor x)
[]
printCell s =
putStr $ "<td>" ++ s ++ "</td>"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.