Home > other >  Memoisation - Bernoulli numbers
Memoisation - Bernoulli numbers

Time:01-06

I am trying to compute some Bernoulli numbers and am trying to use memoisation. In the example below, I can get the Bernoulli number for 8 when I run 1-7 before it, but not if the cache is clear. What changes would I need to make to run it when the cache is clear?

from fractions import Fraction
from scipy.special import comb
import numpy as np

# memoisation
bernoulli_cache = {}

def bernoulli(n: float):
    # check input, if it exists, return value
    if n in bernoulli_cache:
        return bernoulli_cache[n]
    
    # when input is 0 or 1
    if n == 0:
        value = Fraction(1)
    else:  
        value = Fraction(1)
        for k in range(n):
            value -= Fraction(comb(n, k)) * Fraction(bernoulli(k), (n - k   1))
            
    # write to cache
    bernoulli_cache[n] = value
    
    # fraction parts for output
    numerator = value.numerator
    denominator = value.denominator
    
    return numerator, denominator

# test this works- bits in cache aleady
bernoulli_cache = {}
bernoulli(0) # 1     
bernoulli(1) # 1/2    
bernoulli(2) # 1/6     
bernoulli(3) # 0
bernoulli(4) # −1/30
bernoulli(5) # 0
bernoulli(6) # 1/42
bernoulli(7) # 0
bernoulli(8) # -1/30

# this doesn't  - bits not in cache
bernoulli_cache = {}
bernoulli(8) # -1/30

CodePudding user response:

Your cache is storing a Fraction so when you have a cache hit you're returning a Fraction. When you have a cache miss you're returning a tuple. You can fix this by changing return numerator, denominator to return Fraction(numerator, denominator).

  • Related