How can I write an algorithm to perform the following calculation exactly? (references accepted)

Question

Given natural numbers $N, K, m, C$, with $3^{m/3}K>C$, I want to be able to write an algorithm to exactly compute the number

$$ \left\lceil \log_3 \left(\frac{N}{3^{m/3}K-C}\right) \right\rceil $$

Since I think I see how to exactly compare an integer against this number, there is the trivial method of "try larger numbers until one works" (maybe this could be sped up by doubling the number every time, and doing a binary search once an upper bound is found?).

However, I expect there are better methods. Can anyone point me to a reference on doing this sort of exact numeric computation, or at least tell me how to solve this particular problem in a non-terrible way?

EDIT: Since it seems a number of people have missed the point -- I want to compute this number exactly, and I want the output to be provably correct. Yes, in practice, doing it with doubles will get the right answer; I already have a version of the program that does that. But I want to write a version that is provably correct, and will, given sufficient memory, work even if the numbers input far exceed the range of a double (though I hope nobody ever does this). In short, any potential failure other than my computer running out of memory is unacceptable.

Since the program is written in Haskell, pointing me to an exact arithmetic library in Haskell that actually works and is provably correct, will suffice for an answer. But please do some sort of check that this is actually or at least likely to be true of the library you are proposing I use; for instance, the last one I tried, ERA, told me that $\lfloor 3-3^{-128}\rfloor=3$.

EDIT again: Some experimentation with what I thought would be a better method suggests maybe brute-force/binary search is the way to go after all. Oops? Well, I'm not certain yet, but my point is, if the answer really is "Yes, binary search really is the a good way to do this, no fancier way is needed," I will accept that as an answer, not demand some better one.

Answer 1

I have absolutely no experience using Haskell, but given a library supporting arbitrary precision floating point numbers and arbitrary size integers I'd do the following:

• Define a function $\tt{check}$ that takes an integer as input and a bool as output with $$ {\tt check}(r) = {\tt true} ~~~ \Leftrightarrow ~~~ 3^{3r+m} K^3 \ge (N + 3^r)^3, $$ i.e. a function that, as you put it, exactly compares the integer to the desired output.
• Compute the expression in floating point arithmetic with some starting precision, store the result as an arbitrarily large integer $r$.
• Check whether ${\tt check}(r) = {\tt true}$ and ${\tt check}(r-1) = {\tt false}$. If that is the case, $r$ is proven to be the correct output. If not, double the precision and repeat.

I'm not sure if that counts as a non-terrible solution, but I think it should terminate relatively fast. Indeed, in most cases it should terminate on its first try, given a sensible starting precision. (I also assume that $3^{m/3}K-C > 0$, otherwise $\text{log}$ isn't well-defined anyway.)

If you want to avoid floating point arithmetic altogether, your idea of doubling integers and then using binary search should be fast enough. You only need something like $4 \text{log}( <result> )$ checks to do this. I expect a floating-point-guess, integer-check method to be slightly faster, though.

Answer 2

Well, it turns out binary search was faster than high precision floating-point computations. Not a very interesting answer or mathematical answer, but that's what happened, so I'm going to mark this closed.