Skip to content

Instantly share code, notes, and snippets.

# tkmharris/akiyama-tanigawa-bernoulli.hs

Last active May 26, 2021 20:38
Show Gist options
• Save tkmharris/00e10d6341d3f9ce4f343302a51bb129 to your computer and use it in GitHub Desktop.
Short Haskell implementation of the Akiyama-Tanigawa algorithm for computing Bernoulli numbers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 {-- Implementation of the Akiyama-Tanigawa algorithm for computing Bernoulli numbers. --} {-- Implement the algorithm by: 1. Begin with list of reciprocals of positive integers. 2. Write function to get next row and iteratie it to get list of lists. 3. Take the head of each list in the list to get Bernoulli nums. Everything evaluates lazily, so we can do this nicely with infinite lists. See tkmh.space/flotsam/haskell-akiyama-tanigawa for more.--} import Data.Ratio -- standard functions on rational numbers bernoulliNums :: [Rational] bernoulliNums = map head \$ iterate nextRow recips where recips = map (\n -> 1 % n) [1..] -- reciprocals of integers nextRow xs = zipWith (*) [1..] (zipWith (-) xs (drop 1 xs)) -- one-liner for next row; thanks owst {-- we can then get the first n Bernoulli numbers with `take n bernoulliNums` --}
to join this conversation on GitHub. Already have an account? Sign in to comment