Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Henning Makholm Aug 14 '12 at 1:44
    
@HenningMakholm: Thank you for the edit. I am just learning math markup on SE. Here is my related question for context (math.stackexchange.com/questions/182245/…). Please refer to Robert Mastragostino's answer for the equation I am trying to adapt. –  Raheel Khan Aug 14 '12 at 1:51
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?) –  Robert Mastragostino Aug 14 '12 at 1:53
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. –  Henning Makholm Aug 14 '12 at 2:15
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. –  Henning Makholm Aug 14 '12 at 11:15

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.