Let's say I have a software that calculates integrals, formally if possible and if not, then it computes an approximation by taking a small $dt$. Of course if the integral is an unknown number, I wouldn't be interested in giving it a name. But if I calculate $\int_0^e\left(\frac{\pi}e+1\right)dt$, I'd like to get $\pi+e$ instead of $5.85987\dots$. Now of course any decent program would be able to calculate that integral that way. But if I made it a bit trickier, I'm quite sure most wouldn't. For example $\int_0^e\ln\left|\exp\left(\left(\frac{\pi}e+1\right)+\sqrt{2}i\right)\right|dt$. Maybe some programs would. But at some point, they would all fail. And when I reach that point where I can't compute it formally, I want to be able to say "Hey, it's not far from $\pi+e$".

How do I find an expression using (a small set of well-known) constants (for example $\{1,e,\pi\}$), $+$, ,$-$,$\times$ $/$ using as few characters* as possible which value is at a distance of at most $\varepsilon >0$ of my approximate value?

Obviously I could compute all the trees until I hit it or got more than $M$ elements (the maximum length of a formula that I could find interesting). M wouldn't be that big so it would be feasible. But isn't there a bright way of doing this?

Because my current vision of how this could be done, I think all algorithm better than the naive brute-force one are

Things I've though of:

  • Use inequalities. For example, if there is a sum at the root, order all the operands in the order: unknown sign, negative, positive so that once you're done with negatives and start the positive, if you get over the value you want, you know you're not getting anywhere. And things like that.

  • Keep a "do not try" subset of the variables. And pass it as an argument to the recursive function trying the trees. For example in $\pi + e - \cdot$, both $\pi$ and $e$ would be in the "do not try" subset since if they helped find a formula, then there would be a shorted one with the same value. But for that thing to be efficient, I'd probably need to remove $1$ from the constants and add an operation $n\times \cdot$ for all $n \in \Bbb Z$ but that brings a new problem: You have infinitely many operators and therefore infinitely many trees of a fixed size... And I'm pretty sure that unless I implement everything from structures to the actual algorithm with that specific goal in mind, it'll actually slow things down...

I'd be fine with any kind of deterministic algorithm even though I couldn't think of anything aside from the naive one plus removing some trees that could work.

* It's the only way I found to measure the relevance of a formula. But if you've got another one, I'd like to hear it :)

  • 1
    $\begingroup$ You may find literature on "inverse symbolic calculators" an informative starting point. $\endgroup$ – Kaya Jul 9 '13 at 20:06
  • $\begingroup$ I couldn't find an article or the source code a an ICS though... I'll keep searching. $\endgroup$ – xavierm02 Jul 9 '13 at 20:20
  • 1
    $\begingroup$ I am familiar with algorithms that deal with this problem restricted to $+$ and $-$ and where the coefficients of the constants are integral: see integer relation algorithms. $\endgroup$ – Kaya Jul 9 '13 at 21:39
  • $\begingroup$ And so for products I could use that after applying the logarithm but then I have to combine both :/ $\endgroup$ – xavierm02 Jul 9 '13 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.