16

I have two simple while loops in my program that I feel ought to be math equations, but I'm struggling to convert them:

float a = someValue;
int b = someOtherValue;
int c = 0;

while (a <= -b / 2) {
    c--;
    a += b;
}
while (a >= b / 2) {
    c++;
    a -= b;
}

This code works as-is, but I feel it could be simplified into math equations. The idea here being that this code is taking an offset (someValue) and adjusting a coordinate (c) to minimize the distance from the center of a tile (of size someOtherValue). Any help would be appreciated.

Rob
  • 47,999
  • 5
  • 74
  • 91
Sydius
  • 13,567
  • 17
  • 59
  • 76
  • Nice insight -- seeing that this could be condensed to a simple formula. – Pat Notz Dec 25 '08 at 06:31
  • can someone please enlight me what those two loops do? i can't for the life of me figure it out – Johannes Schaub - litb Dec 25 '08 at 07:41
  • Think of a tiling that is 'b' apart: ...|....|....|....|... where the tiles are numbered and the 0th tile is centred at 0 (it is from -b/2 to b/2). This code wants to find which tile 'a' lies in. The first loop moves a until it is not to the left of the center tile, and the second until not right. – ShreevatsaR Dec 25 '08 at 16:32
  • @litb: This might help: think of how you would implement "%" (remainder) (modulo a positive number, say) using only additions and subtractions, and without using a built-in % or division. – ShreevatsaR Dec 25 '08 at 16:42

4 Answers4

36

It can be proved that the following is correct:

c = floor((a+b/2)/b)
a = a - c*b

Note that floor means round down, towards negative infinity: not towards 0. (E.g. floor(-3.1)=-4. The floor() library functions will do this; just be sure not to just cast to int, which will usually round towards 0 instead.)

Presumably b is strictly positive, because otherwise neither loop will never terminate: adding b will not make a larger and subtracting b will not make a smaller. With that assumption, we can prove that the above code works. (And paranoidgeek's code is also almost correct, except that it uses a cast to int instead of floor.)

Clever way of proving it: The code adds or subtracts multiples of b from a until a is in [-b/2,b/2), which you can view as adding or subtracting integers from a/b until a/b is in [-1/2,1/2), i.e. until (a/b+1/2) (call it x) is in [0,1). As you are only changing it by integers, the value of x does not change mod 1, i.e. it goes to its remainder mod 1, which is x-floor(x). So the effective number of subtractions you make (which is c) is floor(x).

Tedious way of proving it:

At the end of the first loop, the value of c is the negative of the number of times the loop runs, i.e.:

  • 0 if: a > -b/2 <=> a+b/2 > 0
  • -1 if: -b/2 ≥ a > -3b/2 <=> 0 ≥ a+b/2 > -b <=> 0 ≥ x > -1
  • -2 if: -3b/2 ≥ a > -5b/2 <=> -b ≥ a+b/2 > -2b <=> -1 ≥ x > -2 etc.,

where x = (a+b/2)/b, so c is: 0 if x>0 and "ceiling(x)-1" otherwise. If the first loop ran at all, then it was ≤ -b/2 just before the last time the loop was executed, so it is ≤ -b/2+b now, i.e. ≤ b/2. According as whether it is exactly b/2 or not (i.e., whether x when you started was exactly a non-positive integer or not), the second loop runs exactly 1 time or 0, and c is either ceiling(x) or ceiling(x)-1. So that solves it for the case when the first loop did run.

If the first loop didn't run, then the value of c at the end of the second loop is:

  • 0 if: a < b/2 <=> a-b/2 < 0
  • 1 if: b/2 ≤ a < 3b/2 <=> 0 ≤ a-b/2 < b <=> 0 ≤ y < 1
  • 2 if: 3b/2 ≤ a < 5b/2 <=> b ≤ a-b/2 < 2b <=> 1 ≤ y < 2, etc.,

where y = (a-b/2)/b, so c is: 0 if y<0 and 1+floor(y) otherwise. [And a now is certainly < b/2 and ≥ -b/2.]

So you can write an expression for c as:

x = (a+b/2)/b
y = (a-b/2)/b
c = (x≤0)*(ceiling(x) - 1 + (x is integer))
   +(y≥0)*(1 + floor(y))

Of course, next you notice that (ceiling(x)-1+(x is integer)) is same as floor(x+1)-1 which is floor(x), and that y is actually x-1, so (1+floor(y))=floor(x), and as for the conditionals:
when x≤0, it cannot be that (y≥0), so c is just the first term which is floor(x),
when 0 < x < 1, neither of the conditions holds, so c is 0,
when 1 ≤ x, then only 0≤y, so c is just the second term which is floor(x) again. So c = floor(x) in all cases.

Robert Gamble
  • 106,424
  • 25
  • 145
  • 137
ShreevatsaR
  • 38,402
  • 17
  • 102
  • 126
  • Excellent answer. It works perfectly, though I will need to read it a few times to understand it fully. – Sydius Dec 25 '08 at 01:39
  • My pleasure :) Actually I guess it could be a bit simpler... I just wrote it the way I first worked it out. If something is confusing, please point it out and I'll take another look at it. – ShreevatsaR Dec 25 '08 at 02:40
  • 1
    Your version is definitely not equivalent to OP's code because OP's code potentially contains infinite loops and yours always terminates. – R.. GitHub STOP HELPING ICE Jun 07 '11 at 22:39
  • @R.: No, the OP's code cannot contain infinite loops. Read through the where I analyse exactly how many times each loop runs. – ShreevatsaR Jun 08 '11 at 02:12
  • 1
    Your analysis is wrong because it assumes floating point numbers obey the rules of algebra. They don't. In particular it's possible that `a+b==a` but `b!=0`. – R.. GitHub STOP HELPING ICE Jun 08 '11 at 02:18
  • @R..: The OP's goal was something algebraic, and he did ask about the "math equations" that achieve it. Now for the secondary question of whether my version is merely The Right Thing or equivalent too: note that b is an int (and +ve for it to make sense, as I said). He also says "This code works as-is". The standards guarantee that the results of floating-point ops will be most exact representable (roughly). Assuming that a is within bounds of int (or it doesn't make sense), it can't have infinite loops, and I don't think it can be different from mine. If you find an example I'd like to know. – ShreevatsaR Jun 08 '11 at 04:05
  • 3
    Try `a=0x10000000` and `b=1`. Then assuming IEEE float, `a-b==a`. I agree your answer agrees with what OP probably wanted, but it's important to realize floating point arithmetic often doesn't give you what you wanted. Your version of the code, rather than being a translation, is more of a bugfix. – R.. GitHub STOP HELPING ICE Jun 08 '11 at 13:05
2
c = (int)((a - (b / 2)) / b + 1);
a -= c * b;

Test case at http://pastebin.com/m1034e639

paranoidgeek
  • 72
  • 3
  • Using floor instead of dropping the decimal portion by converting it to an integer makes it work for negative values. – Sydius Dec 25 '08 at 01:34
1

I think you want something like this:

c = ((int) a + b / 2 * sign(a)) / b

That should match your loops except for certain cases where b is odd because the range from -b/2 to b/2 is smaller than b when b is odd.

Dave L.
  • 43,907
  • 11
  • 63
  • 62
  • "sin", not "sign", but yes, you want a sin wave function. – Ed S. Dec 25 '08 at 00:37
  • I think Dave really means sign(), defined by: int sign(x) { return x > 0 ? 1 : x < 0 ? -1 : 0; } – Greg Hewgill Dec 25 '08 at 00:42
  • Not correct: for a trivial example, take a = b = 10, then neither loop ever runs at all (so c=0) but this answer will say c=1. – ShreevatsaR Dec 25 '08 at 01:28
  • Shreevatsar: That's not true. If a = b = 10, then a >= b/2, so the later loop will run once, and c = 1. – Dave L. Dec 25 '08 at 05:24
  • Oh sorry, I wasn't thinking clearly. For a=b=10, this says c=((int) 10+5)/10, which is actually 1.5 :-) But if a and b are ints, so that "/" means integer division, then for positive a, it is floor(a+b/2)/b, so right, and for negative a it is ceil(a-b/2)/b=floor((a+b/2)/b) *except* when b|(a-b/2). – ShreevatsaR Dec 25 '08 at 05:49
  • That is, pick negative a such that it is b/2 mod b, e.g. b=10 and a=-5. Then c=-1+1=0, but ((int)-5-5)/10 is -1. But yeah, this is correct except when a is negative and b divides a-b/2; sorry for my first comment. – ShreevatsaR Dec 25 '08 at 05:52
  • BTW, if I may ask: how did you think of this? It seems something quite clever, and completely different from the others. – ShreevatsaR Dec 25 '08 at 06:02
0

Assuming b is positive, abs(c) = floor((abs(a) - b/2) / b). Then, apply sign of a to c.

buti-oxa
  • 11,261
  • 5
  • 35
  • 44