4

This algorithm finds a given value n by iterating between a lower bound and upper bound, similar to binary search. How can I improve this algorithm? A few details. The value n is almost always less than 1.0, but this isn't a boundary condition. It is, however, never less than 0. 

def approx_value(n, lower_bound, upper_bound, precision = 0.001):
    approx = (lower_bound + upper_bound) / 2.0
    while (abs(approx - n) > precision):
        if n > approx:
            lower_bound = approx
        else:
            upper_bound = approx
        approx = (lower_bound + upper_bound) / 2.0
    return approx

def approx_value_no_bounds(n, precision = 0.0001):
    approx = 1.0
    while (abs(approx - n) > precision):
        if approx > n: #decrease volatility
            return approx_value(n, 0.0, approx)
        else:
            approx *= 2
    return approx

I know this seems odd because the value of n is already supplied, but the algorithm is not complete. Basically, n is the solution of a complex equation that cannot be solved for approx in closed form, so I'm doing it iteratively. Eventually, this algorithm will compare the value of the function when using approx with the value n and return approx is it approximates the input variable well enough.

I'm hoping to keep the running time in O(log(n)), which is why I modelled it somewhat after binary search, albeit only somewhat because the upper bound is not necessarily known immediately.

Ricardo Altamirano
  • 14,650
  • 21
  • 72
  • 105
  • 1
    Try it out. The code seems like it should work. – Blender Mar 17 '12 at 03:03
  • The code works perfectly, but I wanted to make sure I hadn't missed any basic optimisations. I know premature optimisation is dangerous, but I just want to know that I'm not missing anything glaringly obvious to more experienced programmers. – Ricardo Altamirano Mar 17 '12 at 03:05
  • 1
    If you're worried about speed, try `PyPy` (it's a drop-in replacement for Python, but optimized with a JIT compiler). If you want to go even faster, try using `numpy` and optimize your code using `numpy`s functions. Better yet, try coding this in C or C++. – Blender Mar 17 '12 at 03:09
  • 1
    What is `guess` in this line: `if guess > n:`? (Just a typo? :) ) – huon Mar 17 '12 at 03:25
  • It seems like what you are trying to do is find the inverse of a function. Are you able to compute derivatives? If so, you can greatly improve performance. – Vaughn Cato Mar 17 '12 at 03:43
  • @Blender - I'm planning to code this in C++ eventually , but I'm using Python to get the logic down since my C++ isn't too practiced, to say the least. @dbaupp - My apologies. I renamed `guess` to `approx` when I uploaded it to fit more with the actual problem and I missed one. @VaughnCato - The algorithm is finding the inverse of a function, but the function is the Black-Scholes model, which is extremely difficult to solve in reverse. – Ricardo Altamirano Mar 17 '12 at 04:44

2 Answers2

3

This sounds like a classic optimization problem. These are well studied, and there are several well-known algorithms. Some simple but reasonably efficient ones are Newton's method or gradient descent.

You could also try the nonlinear-simplex algorithm if the above don't work very well for your function.

The running time vs accuracy tradeoff here depends on the nature of the function you are trying to solve for.

jnnnnn
  • 3,889
  • 32
  • 37
  • I've heard of several of these methods, and I may try to implement the ones that fit when I have a chance. In technical terms, the algorithm is solving the black-scholes model for implied volatility, which isn't solvable in closed form. (I know the problem has been solved many times before, but for the sake of learning I'm reinventing the wheel a tad) – Ricardo Altamirano Mar 17 '12 at 04:46
1

Functions from Optimization and root finding (scipy.optimize) might be helpful here.

Here's an example that reverses sun_altitude(time) function using scipy.optimize.brentq().

Community
  • 1
  • 1
jfs
  • 399,953
  • 195
  • 994
  • 1,670