0
$\begingroup$

I am dealing with points on a 2d space $(x, y)$ where $x$ and $y$ are always positive integers.

In an algorithm, I have pre-computed $\log_2(x)$ and $\log_2(y)$ for given points of interest.

I now need to compute $\log_2(x+y)$ and $\log_2(x-y)$ but don't have the luxury to do so from a computational perspective so I started looking for some sort of correlation.

I wasn't sure if there was a relationship between $\ln(x\pm y)$ and $\ln(x)\pm\ln(y)$ so I charted some numbers in Excel and came across the following:

  • The ratio of $(Log(X+Y) / (Log(X)+Log(Y)))$ seems to mostly lie between 0.5 and 0.7.
  • For a large set of numbers the average ratio and median ratio seem to be ALWAYS between 0.56 and 0.58.
  • Of course, there are corner cases in subtraction where x-y turns out negative. How can I avoid that by the way?

So the question is:

  • Am I missing some fundamental concepts to have to find this relationship this way?
  • If the answer to the above is no, how reliable would this correlation be for all integers x and y? The magnitude I am dealing with is around 2 to the power 10,000,000.

SOME EXTRA CONTEXT:
Some have suggested more context may bring about a different approach altogether so here it is. In 2D space, I have a starting point $(x, y)$ and need to move around following some rules. Allowed directions are $\pm (horizontal$, $vertical$, $diagonal$ and $anti-diagonal)$. Some other restrictions include not moving along the diagonal of $(x, y)$ where $(x*y)$ is a power of 2. The target is to get to the top left of the grid where the concentration of power of 2 numbers is high. Lastly, we can only change direction after encountering the diagonal of a power of 2.

So we start looping at the starting point, find neighboring power of 2 coordinates and filter out all diagonal intersections between our current position and power of 2 neighbors (which become potential turning points). Once we have this list, we need to determine optimal direction so we land closest to (1, 1) in euclidean distance. This is where we cannot afford any more multiplication, division, logarithms, etc.

  • 0
    When $x-y$ is negative, $\log(x-y)$ does not make any sense by itself. To decide what to do about that, we'd need information about what you're trying to do and what led you to conclude that $\log(x-y)$ is what you need to compute.2012-08-14
  • 0
    @HenningMakholm: Thank you for the edit. I am just learning math markup on SE. Here is my related question for context (http://math.stackexchange.com/questions/182245/calculate-closest-point-without-calculating-hypotenuse-or-linear-length-in-2d-sp). Please refer to Robert Mastragostino's answer for the equation I am trying to adapt.2012-08-14
  • 1
    Keep in mind that my answer probably isn't the best if those logarithms are expensive. I'd suggest giving a more thorough account of what exactly you're trying to accomplish, so that we can potentially suggest completely new routes (e.g, do you actually need to calculate euclidean distance or can it be approximated by something else?)2012-08-14
  • 0
    @RobertMastragostino: I don't actually need to calculate the euclidean distance. Since $ln(x)$ and $ln(y)$ are already computed, I am trying to use your equation by eliminating the need to compute $ln(x\pm y)$.2012-08-14
  • 0
    @RaheelKhan, right but my point was that we're still getting a comparison that is *equivalent* to Euclidean distance. If "which is closer" isn't literally what you're going for, and is just a supposed substep in a larger problem, there may be some other notion that would better solve it. Or if you have bounds on what your numbers are (e.g, you said they were large) we may be able to come up with something that works for the cases you need.2012-08-14
  • 0
    @RobertMastragostino: A typical base 2 exponent of x or y in my case is around the order of 5,000,000. These are pre-computed. Maybe I could compute $ln(ex)$ and $ln(ey)$ where ex and ey are already exponents. That should be relatively trivial. What do you think? I am adding more context to the question as you asked.2012-08-14
  • 1
    @RaheelKhan: Do you really have all 5 million bits of each of these numbers stored? (Mind reels). Or do you mean that each number is always an exact power of 2? In the latter case, their squares are _also_ exact powers of 2, and the squared distances will therefore have exactly 2 bits set, which you can compare easily just by remembering their positions.2012-08-14
  • 0
    @RaheelKhan are you only *ever* landing on/dealing with powers of two? Because if that's the case then I think your problem is equivalent to one played out simply on the integers, and you can just use the logarithms directly without worrying about horrible computations. Also, does diagonal imply $45^{\circ}$, or whatever diagonal you happen to be standing on?2012-08-14
  • 0
    @HenningMakholm: We only a single $(x, y)$ where $(x*y)$ is NOT a power of 2. Given this $(x, y)$, we compute neighbors, intersections, etc. to get towards the top-left (1, 1) of the virtual grid. We only have 5 millions bits stored for $(x, y)$ and some of it's surrounding neighbors.2012-08-14
  • 0
    @RobertMastragostino: No, landing on a power of 2 IS the objective so our calculations are done on arbitrary points. Yes diagonals imply 45 degrees and we can only change direction is our $(x, y)$ direction intersects with a power of 2 diagonal. Our allowed directions are also limited as explained in the question.2012-08-14
  • 0
    I'm just throwing an idea at you: $\log_b(x \pm y) = \log_b x + \log_b(1 \pm \frac yx)$.2012-08-14
  • 1
    How sure are you that the Euclidean distance is what you need? If it's just for a heuristic, for example, Manhattan distance would be a lot easier to calculate and compare.2012-08-14
  • 0
    @HenningMakholm: I just plotted Euclidean against Manhattan and the similarity is excellent. What I now need to to use Manhattan ($M$) effectively is to find the angle to $(1,1)$. In other words, a ratio between x and y would do as well. Since I already have $M=X+Y$ for Manhattan, is there a way to approximate $(X/M)$ or $(X/Y)$ without actually dividing?2012-08-14

1 Answers 1

9

The defining property of the logarithm is that it converts multiplication to addition. Thus we have $\log xy = \log x + \log y$ and $\log \frac{x}{y} = \log x - \log y$. But it does not really convert addition to anything.

More precisely, conditional on Schanuel's conjecture the numbers $\log p$, as $p$ runs over the primes, are algebraically independent; that is, there is no polynomial relationship between them whatsoever (with rational coefficients). In particular, there is no polynomial relationship between the numbers $\log (2 + 3), \log 2, \log 3$ (for example).

However, if you're willing to settle for approximate relationships and if one of $x$ or $y$ is small relative to the other, you can use the Taylor series of the logarithm.