diff options
| author | Justin Bedo <cu@cua0.org> | 2023-01-24 16:04:51 +1100 |
|---|---|---|
| committer | Justin Bedo <cu@cua0.org> | 2023-01-24 18:27:23 +1100 |
| commit | 72c43d718504c71d641844167dee51b1e501f307 (patch) | |
| tree | 68cc1aad384c33237026250cebc52779a8f100cb | |
| parent | d748c1e34958e4da3d0045df3e0f852c14707820 (diff) | |
faster choose
| -rw-r--r-- | bin/cluster.hs | 10 | ||||
| -rw-r--r-- | cabal.project | 4 |
2 files changed, 8 insertions, 6 deletions
diff --git a/bin/cluster.hs b/bin/cluster.hs index 42e25dc..67b6e02 100644 --- a/bin/cluster.hs +++ b/bin/cluster.hs @@ -25,11 +25,13 @@ logFromInt = logFrom . fromIntegral logFrom = Exp . log binom :: Int -> Int -> Double -> Log Double -binom 0 _ _ = 1 -binom n 0 p = logFrom (1 - p) ** logFromInt n -binom n@(logFromInt -> n') k@(logFromInt -> k') p@(logFrom -> p') = choose * p' ** k' * logFrom (1 - p) ** (n' - k') +binom n@(logFromInt -> n') k@(logFromInt -> k') p + | n == 0 = 1 + | k == 0 = logFrom (1 - p) ** logFromInt n + | k == n = logFrom p ** logFromInt n + | otherwise = n `choose` k * logFrom p ** k' * logFrom (1 - p) ** (n' - k') where - choose = product [(n' + 1 - logFromInt i) / logFromInt i | i <- [1 .. k]] + choose (fromIntegral -> n) (fromIntegral -> k) = stirling n / stirling k / stirling (n - k) -- (infinite) binary trees data Tree a = Tree a (Tree a) (Tree a) diff --git a/cabal.project b/cabal.project index b4bd1ad..1869ff4 100644 --- a/cabal.project +++ b/cabal.project @@ -3,5 +3,5 @@ packages: *.cabal source-repository-package type: git location: https://vk3.wtf/cgit/ppl.git - tag: 190a4dc5f5398e6646823aa41637f54cc8cb54aa - --sha256: 0rm96sslc08hvxjfzqqm8ix4ndq2qhp6f1ycpnbs5347c7gl8xn5 + tag: 275ed22d5050488e6d40bb5800f1ade9c30d8a76 + --sha256: 0s3knn77s4pc277j3z0n80qh90kzlayl712b4i7sq43ib3p340ii |