Skip to content

Instantly share code, notes, and snippets.

@tkmharris
Last active May 26, 2021 20:38
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Short Haskell implementation of the Akiyama-Tanigawa algorithm for computing Bernoulli numbers.
{-- 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` --}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment