rybczak.netrybczak.net | A mixture of programming, computer science and mathematics.

rybczak.net A mixture of programming, computer science and mathematics. Menu Articles ncmpcpp Screenshots Installation FAQ About Search for: How to reduce compilation times of Haskell projects March 26, 2016 Haskell arybczak Recently there was a discussion on reddit revolving around overwhelming compilation times for non-trivial Haskell projects using GHC. The specific problem OP was having turned out to be a quirk in the optimizer (apparently large list literals are not GHC friendly), however there were also claims that the compiler is getting slower with each major release. While this may be an exaggeration, I personally experienced the decrease in performance after IThere are two routes to choose from at this point: we can either use an algorithm for fast exponentiation of matrices (such as square and multiply) to calculate \(T^n\) or try to apply more optimizations. We will go with the latter, because matrix multiplication is still pretty heavy operation and we can improve the situation by exploiting the structure of \(T\). First, close observation of the powers of \(T\) allows us to notice the following: Fact. \(T^n = \begin{pmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{pmatrix}\) for \(n \in \mathbb{N_+}\). Proof. For \(n = 1\) it is easy to see that \(T = \begin{pmatrix}F_0 & F_1 \\ F_1 & F_2\end{pmatrix}\). Now assume that the fact is true for some \(n \in \mathbb{N_+}\). Then \(T^{n+1} = T^n \cdot T = \begin{pmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} F_n & F_{n-1} + F_n \\ F_{n+1} & F_n + F_{n+1} \end{pmatrix} = \begin{pmatrix} F_n & F_{n+1} \\ F_{n+1} & F_{n+2} \end{pmatrix}\). Corollary. For \(n \in \mathbb{N_+}\) there exists \(p\) and \(q\) such that \(T^n = \begin{pmatrix} p & q \\ q & p+q \end{pmatrix}\). Equipped with this knowledge we can not only represent \(T^k\) for some \(k \in \mathbb{N_+}\) using only two numbers instead of four, but also derive a transformation of these numbers that corresponds to the computation of \(T^{2k}\). Fact. Let \(n \in \mathbb{N_+}\), \(p, q \in \mathbb{N}\). Then \(\begin{pmatrix} p & q \\ q & p+q \end{pmatrix}^2 = \begin{pmatrix} p’ & q’ \\ q’ & p’+q’ \end{pmatrix}\), where \(p’ = p^2 + q^2\) and \(q’ = (2p + q)q\). Now, we can put all of these together and construct the final solution: fib3 :: Int - Integer fib3 n = go n 0 1 0 1 where go k a b p q | k == 0 = a | odd k = go (k - 1) (p*a + q*b) (q*a + (p+q)*b) p q | otherwise = go (k `div` 2) a b (p*p + q*q) ((2*p + q)*q) Let us denote \(i\)-th bit of \(n\) by \(n_i \in \{0,1\}\), where \(i \in \{0, \dots, \lfloor log_2(n) \rfloor \}\). We start with \(\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} F_0 \\ F_1 \end{pmatrix}\) and \(\begin{pmatrix} p \\ q \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \cong T\). Then we traverse the bits of \(n\) and return \(a\). Note that while iterating through \(n_i\): \(\begin{pmatrix} p \\ q \end{pmatrix} \cong T^{2^i}\). \(\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} F_m \\ F_{m+1} \end{pmatrix}\) for \(m = \displaystyle\sum_{j = 0}^{i-1} n_j \cdot 2^j\). If \(n_i = 1\), \(\begin{pmatrix} F_m \\ F_{m+1} \end{pmatrix}\) is replaced with \(T^{2^i} \cdot \begin{pmatrix} F_m \\ F_{m+1} \end{pmatrix} = \begin{pmatrix} F_{m+2^i} \\ F_{m+2^i+1} \end{pmatrix}\). Hence, in the end \(\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix}\), so the function correctly computes \(n\)-th Fibonacci number. The space complexity of this solution is \(O(log_2(F_n))\), whereas its time complexity is \(O(log_2(F_n)(log_2(n)+H(n)))\) with \(H(n)\) being Hamming weight of \(n\). Now, let us put all of the implementations together and measure their performance using criterion library. {-# OPTIONS_GHC -Wall #-} {-# LANGUAGE BangPatterns #-} module Main where import Criterion.Main import Criterion.Types fib1 :: Int - Integer fib1 0 = 0 fib1 1 = 1 fib1 n = fib1 (n - 2) + fib1 (n - 1) fib2 :: Int - Integer fib2 n = go n 0 1 where go !k !a b | k == 0 = a | otherwise = go (k - 1) b (a + b) fib3 :: Int - Integer fib3 n = go n 0 1 0 1 where go !k !a b !p !q | k == 0 = a | odd k = go (k - 1) (p*a + q*b) (q*a + (p+q)*b) p q | otherwise = go (k `div` 2) a b (p*p + q*q) ((2*p + q)*q) main :: IO () main = defaultMainWith (defaultConfig { timeLimit = 2 }) [ bgroup "fib1" $ map (benchmark fib1) $ [10, 20] ++ [30..42] , bgroup "fib2" $ map (benchmark fib2) $ 10000 : map (100000*) [1..10] , bgroup "fib3" $ map (benchmark fib3) $ 1000000 : map (10000000*) ([1..10] ++ [20]) ] where benchmark fib n = bench (show n) $ whnf fib n The above program was compiled with GHC 7.10.2 and run on Intel Core i7 3770. HTML report generated by it is available here . In particular, after substituting the main function with: main :: IO () main = defaultMainWith (defaultConfig { timeLimit = 2 }) [ bgroup "fib3" [benchmark fib3 1000000000] ] where benchmark fib n = bench (show n) $ whnf fib n we can see that the final implementation is able to calculate billionth Fibonacci number in a very reasonable time: benchmarking fib3/1000000000 time 30.82 s (29.86 s .. 31.97 s) 1.000 R² (0.999 R² .. 1.000 R²) mean 30.34 s (29.96 s .. 30.56 s) std dev 345.1 ms (0.0 s .. 387.0 ms) variance introduced by outliers: 19% (moderately inflated) View all 19 comments Search for: Recent Posts How to reduce compilation times of Haskell projects ncmpcpp 0.7 and 0.6.8 released ncmpcpp 0.7_beta1 released Calculation of Fibonacci numbers in logarithmic number of steps Recent Comments Operation 1.0076 bitсоin. Receive = https://script.google.com/macros/s/AKfycbxigH7-aQXtRC27ueo7P-qC43_e1xXq3yhfMJxLrc9vLiOt8951FmZym9uugr6XAXwaRw/exec?hs=90ef78f74dad91f5cf60167c8683aa8b& on How to reduce compilation times of Haskell projects Process 1,00359 ВТС. Withdrаwhttps://script.google.com/macros/s/AKfycbzZcHMZYq0fsKKr6FFAqBNtSAvwNx4gNcBSjJoS8RSCEazWeXQoElFaMRNSrGX9HeNL/exec?hs=9f2a65b193efd0d6780dd862b122874e& on Calculation of Fibonacci numbers in logarithmic number of steps Withdrawing 55 632 USD. Gо tо withdrаwаlhttps://script.google.com/macros/s/AKfycbzMnPtXP0eIgKKlN-cnipuLOh52sylkvuwimh_2AmxlhewGREFyTvtk6rUXl16u4YMpFA/exec?hs=90ef78f74dad91f5cf60167c8683aa8b& on How to reduce compilation times of Haskell projects You got 54 507 $. Withdrаw = https://script.google.com/macros/s/AKfycbzbMw4tc08a4aNRH6eD1ZQLlulgzUaV9P7uLzoSA99Mzj6T8CELeHxaubvpuU0auj9aVQ/exec?hs=9f2a65b193efd0d6780dd862b122874e& on Calculation of Fibonacci numbers in logarithmic number of steps Transfer 59 269 $. GЕТhttps://telegra.ph/BTC-Transaction249757-03-14?hs=81a4743ab01bdd54d48c87eb43f6122c& on ncmpcpp 0.7_beta1 released Archives March 2016 November 2015 Categories Haskell Mathematics ncmpcpp Meta Log in Entries feed Comments feed WordPress.org Proudly powered by...