2

I made these large loops of random operations to benchmark (just because I was curious) and ran into something I just do not understand. No matter what I input for the large loop, it always produces the same result. This is the code cut down to the part I am talking about.

public int stuff;
public int result;

myJavaProgram(String[] cmdArguments)
{ 
  stuff=1;
  superLoopCalcualtion();
  System.out.println(stuff+" converted to result:"+result); 

  stuff=12345;
  superLoopCalcualtion();
  System.out.println(stuff+" converted to result:"+result); 

  stuff=9823450;
  superLoopCalcualtion();
  System.out.println(stuff+" converted to result:"+result); 
}  

public void superLoopCalcualtion()
{
  int a=stuff;
  int b=a+99;   
  int z=0;
  for (z = 0; z < 200000; z++) 
  {
    a=a+22;
    b=a*44;
    a=b+1234;
  }
  result=a;
}

And the output is this 

1 converted to result:1398361394
12345 converted to result:1398361394
9823450 converted to result:1398361394

There is no way that could be right...right??

user1803551
  • 12,965
  • 5
  • 47
  • 74
user3134006
  • 65
  • 5
  • I haven't had time to go through the numbers yet, but I bet that on one of your iterations in the `b=a*44` step, you're getting a number greater than the largest allowed integer, so it's defaulting to another value. – Davy M Nov 29 '17 at 22:01
  • Are you sure these are random operations? – shmosel Nov 29 '17 at 22:12
  • Why are you using member variables `stuff` and `result`, rather than passing a parameter `stuff` and returning `result`? – Andy Turner Nov 29 '17 at 22:14
  • reply to Davy M: I just ran some more tests and that does not appear to be it. For example, looping a=a+100; b=a/4; a=b+100; should never be able to produce a very large int, yet it also causes a constant output problem, just this time with 166 always being the result. And a=a+100; b=a+999999999; a=b+100; which in a large loop would for sure go beyond the int max, it actually does produce variable results. It seems that any large loop I make which uses multiplication or division always gets stuck on a particular result regardless of input. Very weird. – user3134006 Nov 29 '17 at 22:16
  • After 14-15 iterations, `a` and `b` don't change any more, and they are going to the same values in all three cases. Not sure why, particularly, but the rest of the 200k iterations don't make any difference. – Andy Turner Nov 29 '17 at 22:22
  • reply to shmosel: not sure what your asking. I just randomly typed in some operations there, they have no real meaning to anything real. Its just showing this strange effect of same output regardless of input that occurs when you loop any similar set of equations a ton of times. – user3134006 Nov 29 '17 at 22:24
  • reply to Andy Turner: Tried passing as parameters also and it made no difference to the result. You found that a and b stop changing after only 15 iterations?? This is so weird.... – user3134006 Nov 29 '17 at 22:28
  • tested it with `long` type the same issue. It seems that max range is reached – Ibrokhim Kholmatov Nov 29 '17 at 22:28
  • @jibrahim it works correctly with long (i.e. different results), if you make all numbers a long, meaning adding the suffix L to all numbers. – dunni Nov 29 '17 at 22:30
  • 1
    Just an FYI - if you want to reply to someone you can put @username and it will ping them. – takendarkk Nov 29 '17 at 22:32
  • As davy said, after a few iterations (6-7 here) you are hitting Integer.MAX_INT, a is going from 2005495112 in iteration 6 to -1952527032 in iteration 7. In iteration 16-17 it stabilizes at 1398361416 as @andy-turner said. – Nick Vanderhoven Nov 29 '17 at 22:35
  • Also, you left some keywords out of the method signature, so it might be that your instance variable stuff is always zero. Also, some operations for b and z are totally redundant in the `superLoopCalculation`. – Nick Vanderhoven Nov 29 '17 at 22:37
  • @dunni That didn't work for me. I tried a=(int)(a+100L); b=(int)(a/4L) a=(int)(b+100L); and a few other variations of playing with longs, and still got stuck on always same result. Am I misunderstanding what you meant? – user3134006 Nov 29 '17 at 22:38
  • @user3134006, well obviously if you cast everything back to int, you still hit max int. You have to change all variables to long as well. – dunni Nov 29 '17 at 22:39
  • 1
    Note: if you multiply by a prime number (e.g. 43), you'll get different numbers. It's a bit like using 31 in hashcode calculation. See https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier – Andy Turner Nov 29 '17 at 22:43
  • 1
    @davym when an arithmetic operation results in a value outside the range of the result type, you don't get a "default value"; you get a numeric overflow (or underflow), whose value is determinastic. – Bohemian Nov 29 '17 at 22:46
  • @Nick Vanderhoven When you go past max int, and int will just loops itself backwards into the negatives (adding 1 to the max just makes the int value come the minimum), so I don't see why it should ever get "stuck". So what is the rule here? If you go past max int, it will loop back the number into the negatives, but is only able to do that one time? To your second comment, not sure what you mean: what keywords are missing and how would that make any of my variables always 0? – user3134006 Nov 29 '17 at 23:00
  • @AndyTurner If you multiply by 44 you'll get different numbers. – user1803551 Nov 29 '17 at 23:01
  • About the keywords, its unclear what method/variable is static or instance variable and if there might be other variables in the scope with the same names.The other part is answered by other commenters. – Nick Vanderhoven Nov 29 '17 at 23:06
  • @Bohemian Exactly! So, you agree that the MAX_INT thing should not be a cause of it getting "stuck"? – user3134006 Nov 29 '17 at 23:10
  • @user1803551 so, your saying this is some weird quirk of math? (not to do with the max int thing?) Could you elaborate on how this effect of getting stuck is occurring then? – user3134006 Nov 29 '17 at 23:14
  • Yes, I'll write an answer that tries to explain it best. – user1803551 Nov 29 '17 at 23:33
  • @NickVanderhoven What are you talking about? It's all perfectly clear and reproducible. – shmosel Nov 29 '17 at 23:59
  • @shmosel I was just pointing out as a sidemark that there is no return type and it looks like it is a main method quickly altered for pasting here. That's exactly why my first thought was the same as AndyTurner: why not passing the variables as parameter to the method. – Nick Vanderhoven Nov 30 '17 at 05:33
  • @NickVanderhoven It's a constructor. – shmosel Nov 30 '17 at 10:19

1 Answers1

6

What you're seeing here is a (camouflaged) overflow that results in an effective multiplication factor being 0, thus effectively ending the value changes in the loop.

Overflow in action

To see this, let's consider a simplified code example using bytes which allows the loop to be shorter:

byte a = stuff;
for (byte z = 0; z < 8; z++) {
    a = (byte) (a * 2);
}

I omitted code that prints the numbers nicely in decimal and binary for each iteration. Here are the results for stuff being 1, 11 and 127 (Byte.MAX_VALUE):

1
---
0: 1        00000001
1: 2        00000010
2: 4        00000100
3: 8        00001000
4: 16       00010000
5: 32       00100000
6: 64       01000000
7: -128     10000000
8: 0        00000000

11
---
0: 11       00001011
1: 22       00010110
2: 44       00101100
3: 88       01011000
4: -80      10110000
5: 96       01100000
6: -64      11000000
7: -128     10000000
8: 0        00000000

127
---
0: 127      01111111
1: -2       11111110
2: -4       11111100
3: -8       11111000
4: -16      11110000
5: -32      11100000
6: -64      11000000
7: -128     10000000
8: 0        00000000

To understand this, consider that multiplying a binary number by 2 adds a 0 from the right. If we do this continually, we "push" the numbers on the left outside of the range that our data structure can hold. For byte that range is 8 bits. Thus, after multiplying 8 times by 2 we guarantee that no matter what the number contained beforehand, it is now all 0s. Continuing has no effect, thus we reached stagnation (or staleness, whatever the term is).

Pushing significant bits outside the "visible" range is called overflow, because the binary representation can't contain them and they... overflow. In decimal, this results in a change of the sign1. If you look at the example for 1, that overflow happens only at the last iteration because the number was small enough, that is equivalent to saying that it had a lot of free space on the right. 127 on the other hand overflows immediately as it is the maximal value for byte, that is, all the bits are needed.

1 In Java all numbers are signed.

Applying to your code

From here, it's a matter of adding complexity step by step until we reach your code, but the underlying phenomenon is the same.

For starters, we can increase our binary representation capacity by using short, int and long, but that just delays the inevitable. Instead of needing 8 iterations, we will need 12, 32 and 64, respectively.

Next, we can change the multiplication factor. An even number is just multiplications of 2, so we will reach the same results. Note that with the special case of 2^n we will always reach the result faster because we are effectively just cutting down on iterations. However, with an odd number we will never reach (decimal) 0; the overflow will always skip it and we will reach our starting number again. Here is stuff = 1 (byte) with multiplication factor 3 for 64 (Byte.MAX_VALUE / 2 + 1) iterations:

1
---
0: 1        00000001
1: 3        00000011
2: 9        00001001
3: 27       00011011
4: 81       01010001
5: -13      11110011
6: -39      11011001
7: -117     10001011
8: -95      10100001
9: -29      11100011
10: -87     10101001
11: -5      11111011
12: -15     11110001
13: -45     11010011
14: 121     01111001
15: 107     01101011
16: 65      01000001
17: -61     11000011
18: 73      01001001
19: -37     11011011
20: -111    10010001
21: -77     10110011
22: 25      00011001
23: 75      01001011
24: -31     11100001
25: -93     10100011
26: -23     11101001
27: -69     10111011
28: 49      00110001
29: -109    10010011
30: -71     10111001
31: 43      00101011
32: -127    10000001
33: -125    10000011
34: -119    10001001
35: -101    10011011
36: -47     11010001
37: 115     01110011
38: 89      01011001
39: 11      00001011
40: 33      00100001
41: 99      01100011
42: 41      00101001
43: 123     01111011
44: 113     01110001
45: 83      01010011
46: -7      11111001
47: -21     11101011
48: -63     11000001
49: 67      01000011
50: -55     11001001
51: 91      01011011
52: 17      00010001
53: 51      00110011
54: -103    10011001
55: -53     11001011
56: 97      01100001
57: 35      00100011
58: 105     01101001
59: 59      00111011
60: -79     10110001
61: 19      00010011
62: 57      00111001
63: -85     10101011
64: 1       00000001

I don't want to go into the bit math so much because I feel it's out of the scope of the question at this point. Suffice to say that on the MAX_VALUE / 2 + 1 iteration you will reach the starting number again (and for some numbers also before that).

The point is that your 44 is even, so you get the stagnating result.

Now to your addition operations. As much as you play with them, before and after the multiplication, it doesn't do more than change the result by a constant. The effect remains the same. Consider

for (byte z = 0; z < 10; z++) {
    a = (byte) (a + 1);
    a = (byte) (a * 2);
}

The result is

1
---
0: 1        00000001
1: 4        00000100
2: 10       00001010
3: 22       00010110
4: 46       00101110
5: 94       01011110
6: -66      10111110
7: 126      01111110
8: -2       11111110
9: -2       11111110
10: -2      11111110

So we are stagnating on -2. In decimal you can see this easily with the loop formula: (-2 + 1) * 2 = -2. Your "random" choice of numbers in the loop resulted (deterministically) in settling on the number 1398361394 after ~15 iterations (using longs will delay this result by some number of iterations). Just do the math iteration by iteration and you will reach a loop formula like the above.

Conclusion time

Be very careful of overflow! Be sure that the data structure you choose is always sufficient to contain the range of numbers you are working with. Worst case, you have the (non-primitive) type BigInteger for arbitrary precision (but it's much slower). Regardless of any of the parameters discussed above, once you overflow your mathematical result will be wrong (unless you are doing overflow math on purpose).

Community
  • 1
  • 1
user1803551
  • 12,965
  • 5
  • 47
  • 74