5

I'm reading an article about Bloom filters, https://en.wikipedia.org/wiki/Bloom_filter, in which an expression is derived for the optimal number of hash functions. I'd like to reproduce the computation for the simplified case that m = n, that is, I'd like to determine the minimum of the function

(1-exp(-x))**x

which, from the article, should occur at x = ln(2). I tried doing this with sympy as follows:

In [1]: from sympy import *

In [2]: x, y, z = symbols('x y z')

In [3]: init_printing(use_unicode=True)

In [8]: from sympy.solvers import solve

In [9]: solve(diff((1-exp(-x))**x,x), x)

However, I get a

NotImplementedError: multiple generators [x, exp(x), log(1 - exp(-x))]
No algorithms are implemented to solve equation x*exp(-x)/(1 - exp(-x)) + log(1 - exp(-x))

I would just like to double-check whether Sympy really cannot solve this problem? Perhaps I need to add additional constraints/assumptions on x?

Kurt Peek
  • 52,165
  • 91
  • 301
  • 526
  • 2
    Looks like it can't. [WolframAlpha](https://www.wolframalpha.com/input/?i=solve+((1-exp(-x))%5Ex)%27+%3D0) only finds the solution _numerically_, and generally Mathematica knows more symbolic tricks than SymPy, considering the resources poured into it. (The solution does match the value of `ln(2)`, by the way) –  Aug 26 '17 at 12:02

1 Answers1

2

When you run into this issue where an equation can't be solved by manipulation of symbols (solving analytically), it's possible that it can still be solved by trying different numbers and getting to (or very close to) the correct answer (solving numerically).

You can convert your sympy solution to a numpy-based function, and use scipy to solve numerically.

from sympy import lambdify
from scipy.optimize import fsolve

func_np = sp.lambdify(x, diff((1-exp(-x))**x,x), modules=['numpy'])
solution = fsolve(func_np, 0.5)

This solves the equation as 0.69314718, which is what you expect.

Tristan Reid
  • 5,844
  • 2
  • 26
  • 31