5
$\begingroup$

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.

$\endgroup$
18
  • $\begingroup$ What language do you have in mind for the implementation? $\endgroup$ Apr 27, 2012 at 4:30
  • $\begingroup$ Compute it inexactly using floating-point arithmetic, and use that as an initial guess to start the search? $\endgroup$
    – user856
    Apr 27, 2012 at 4:33
  • $\begingroup$ @Rahul Narain: I want everything I'm doing to be provably correct, so I'd rather avoid floating-point. But using it as a guideline for searches may well work. Of course, there is the problem that in general the numbers may get larger than native floating point can handle. $\endgroup$ Apr 27, 2012 at 4:52
  • $\begingroup$ @deoxygerbe: The program is written in Haskell. I suppose I could rewrite it in Mathematica or something but I'd rather not. And so far none of the exact arithmetic libraries I've found for Haskell have been quite satisfactory, which is why I'm asking this -- but perhaps you know one? $\endgroup$ Apr 27, 2012 at 4:53
  • $\begingroup$ @HarryAltman: can you take natural logarithms and evaluate real^real easily in those libraries? $\endgroup$ Apr 27, 2012 at 5:03

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What bugs me here is the "convert to integer" step. I mean, if there's not enough precision, it doesn't really represent a particular integer... but I guess that's why you double the precision and try again; whatever arbitrary-precision library I'd be using has some way of guessing one, and I don't really care what it is so long as it's eventually correct. $\endgroup$ Apr 28, 2012 at 0:02
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .