Why does this code misbehave?

[zapshe]

Hi, I started learning about Binary since I was curious how programming language turns into 1s and 0s. I learned that 2^64 is the number limit. I made a loop that would count up to that number :

#include "stdafx.h"
#include <iostream>
#include <cmath> 


using namespace std;

int main()
{
	for (unsigned long long x = 0; x <= 18400000000000000000; x+=100000000000000000) 
	{ 
		

		cout << x << endl;
	}
	cin.get();
}
  

This program works fine. However, adding another 0 to x+=10000000000000000 to make it reach 18 quadrillion faster ends up giving this result :

0
100000000000000000
200000000000000000
300000000000000000
400000000000000000
500000000000000000
600000000000000000
700000000000000000
800000000000000000
900000000000000000
1000000000000000000
1100000000000000000
1200000000000000000
1300000000000000000
1400000000000000000
1500000000000000000
1600000000000000000
1700000000000000000
1800000000000000000
1900000000000000000
2000000000000000000
2100000000000000000
2200000000000000000
2300000000000000000
2400000000000000000
2500000000000000000
2600000000000000000
2700000000000000000
2800000000000000000
2900000000000000000
3000000000000000000
3100000000000000000
3200000000000000000
3300000000000000000
3400000000000000000
3500000000000000000
3600000000000000000
3700000000000000000
3800000000000000000
3900000000000000000
4000000000000000000
4100000000000000000
4200000000000000000
4300000000000000000
4400000000000000000
4500000000000000000
4600000000000000000
4700000000000000000
4800000000000000000
4900000000000000000
5000000000000000000
5100000000000000000
5200000000000000000
5300000000000000000
5400000000000000000
5500000000000000000
5600000000000000000
5700000000000000000
5800000000000000000
5900000000000000000
6000000000000000000
6100000000000000000
6200000000000000000
6300000000000000000
6400000000000000000
6500000000000000000
6600000000000000000
6700000000000000000
6800000000000000000
6900000000000000000
7000000000000000000
7100000000000000000
7200000000000000000
7300000000000000000
7400000000000000000
7500000000000000000
7600000000000000000
7700000000000000000
7800000000000000000
7900000000000000000
8000000000000000000
8100000000000000000
8200000000000000000
8300000000000000000
8400000000000000000
8500000000000000000
8600000000000000000
8700000000000000000
8800000000000000000
8900000000000000000
9000000000000000000
9100000000000000000
9200000000000000000
9300000000000000000
9400000000000000000
9500000000000000000
9600000000000000000
9700000000000000000
9800000000000000000
9900000000000000000
10000000000000000000
10100000000000000000
10200000000000000000
10300000000000000000
10400000000000000000
10500000000000000000
10600000000000000000
10700000000000000000
10800000000000000000
10900000000000000000
11000000000000000000
11100000000000000000
11200000000000000000
11300000000000000000
11400000000000000000
11500000000000000000
11600000000000000000
11700000000000000000
11800000000000000000
11900000000000000000
12000000000000000000
12100000000000000000
12200000000000000000
12300000000000000000
12400000000000000000
12500000000000000000
12600000000000000000
12700000000000000000
12800000000000000000
12900000000000000000
13000000000000000000
13100000000000000000
13200000000000000000
13300000000000000000
13400000000000000000
13500000000000000000
13600000000000000000
13700000000000000000
13800000000000000000
13900000000000000000
14000000000000000000
14100000000000000000
14200000000000000000
14300000000000000000
14400000000000000000
14500000000000000000
14600000000000000000
14700000000000000000
14800000000000000000
14900000000000000000
15000000000000000000
15100000000000000000
15200000000000000000
15300000000000000000
15400000000000000000
15500000000000000000
15600000000000000000
15700000000000000000
15800000000000000000
15900000000000000000
16000000000000000000
16100000000000000000
16200000000000000000
16300000000000000000
16400000000000000000
16500000000000000000
16600000000000000000
16700000000000000000
16800000000000000000
16900000000000000000
17000000000000000000
17100000000000000000
17200000000000000000
17300000000000000000
17400000000000000000
17500000000000000000
17600000000000000000
17700000000000000000
17800000000000000000
17900000000000000000
18000000000000000000
18100000000000000000
18200000000000000000
18300000000000000000
18400000000000000000
53255926290448384
153255926290448384
253255926290448384
353255926290448384
453255926290448384
553255926290448384
653255926290448384
753255926290448384
853255926290448384
953255926290448384
1053255926290448384
1153255926290448384
1253255926290448384
1353255926290448384
1453255926290448384
1553255926290448384
1653255926290448384
1753255926290448384
1853255926290448384
1953255926290448384
2053255926290448384
2153255926290448384
2253255926290448384
2353255926290448384
2453255926290448384
2553255926290448384
2653255926290448384
2753255926290448384
2853255926290448384
2953255926290448384
3053255926290448384
3153255926290448384
3253255926290448384
3353255926290448384
3453255926290448384
3553255926290448384
3653255926290448384
3753255926290448384
3853255926290448384
3953255926290448384
4053255926290448384
4153255926290448384
4253255926290448384
4353255926290448384
4453255926290448384
4553255926290448384
4653255926290448384
4753255926290448384
4853255926290448384
4953255926290448384
5053255926290448384
5153255926290448384
5253255926290448384
5353255926290448384
5453255926290448384
5553255926290448384
5653255926290448384
5753255926290448384
6453255926290448384
6553255926290448384
6653255926290448384
6753255926290448384
6853255926290448384
6953255926290448384
7053255926290448384
7153255926290448384
7253255926290448384
7353255926290448384
7453255926290448384
7553255926290448384
7653255926290448384
7753255926290448384
7853255926290448384
7953255926290448384
8053255926290448384
8153255926290448384
8253255926290448384
8353255926290448384
8453255926290448384
8553255926290448384
8653255926290448384
8753255926290448384
9553255926290448384
9653255926290448384
9753255926290448384
9853255926290448384
9953255926290448384
10053255926290448384
10153255926290448384
10253255926290448384
10353255926290448384
10453255926290448384
10553255926290448384
10653255926290448384
10753255926290448384
10853255926290448384
10953255926290448384
11053255926290448384
11153255926290448384
11253255926290448384
11953255926290448384
12053255926290448384
12153255926290448384
12253255926290448384
12353255926290448384
12453255926290448384
12553255926290448384
12653255926290448384
12753255926290448384
12853255926290448384
12953255926290448384
13053255926290448384
13153255926290448384
13253255926290448384
13353255926290448384
13453255926290448384
13553255926290448384
13653255926290448384
13753255926290448384
13853255926290448384
13953255926290448384
14053255926290448384
14153255926290448384
14253255926290448384
14353255926290448384
14453255926290448384
14553255926290448384
14653255926290448384
14753255926290448384
14853255926290448384
14953255926290448384
15053255926290448384
15153255926290448384
15253255926290448384
15353255926290448384
15453255926290448384
15553255926290448384
15653255926290448384
15753255926290448384
15853255926290448384
15953255926290448384
16053255926290448384
16153255926290448384
16253255926290448384
16353255926290448384
16453255926290448384
16553255926290448384
16653255926290448384
16753255926290448384
16853255926290448384
16953255926290448384
17053255926290448384
17153255926290448384
17253255926290448384
17353255926290448384
17453255926290448384
17553255926290448384
17653255926290448384
17753255926290448384
17853255926290448384
17953255926290448384
18053255926290448384
18153255926290448384
18253255926290448384
18353255926290448384
106511852580896768
206511852580896768
306511852580896768
406511852580896768
506511852580896768
606511852580896768
706511852580896768
806511852580896768
906511852580896768
1006511852580896768
1106511852580896768
1306511852580896768
18106511852580896768
18206511852580896768
18306511852580896768

^Took out a LOT of lines to fit character Limit


^ This goes to 18 quadrillion and then goes to another number and starts adding again - and it does this twice, both times going as close to 18 quadrillion as it can. Why does adding another 0 do this?

[helios]

(Note: For the sake of brevity, from this point forward k = 10^17)

When x == 184*k the loop will continue running because the condition is x <= 184*k. (2^64 - 1) - 184*k is less than k, so 184*k + k will loop around to become 185*k % 2^64 = (184 + 1) * k - 2^64 = 53255926290448384, and then it will run one more time until x > 184*k.

The loop condition you want is x < 184*k.

[zapshe]

Should clarify some things. x+=10000000000000000 (10^16) - Accidentally typed an extra zero into the copied and pasted code. Also, I realize that x<= 184*k means that as long as x is less than or equal to 184*k that it should continue running. However, when x+=100000000000000000 (10^16) - It simply stops exactly at 184*k . However, if I add an extra 0, it will do as you said and loop over until x will become larger than 184*k - Even though adding another 0 still makes 184*k divisible by the number that it'll add. In fact, making x+= anything less than 10^17 will make it stop at exactly 184*k . It doesn't really make sense, but that's how it's working. Why?

By the way, I really appreciate you helping me Helios, it's very kind of you to help !

[JLBorges]

#include <iostream>
#include <limits>

int main()
{
     const auto max = std::numeric_limits<unsigned long long>::max() ;

     for( int i = 1 ; i < 7 ; ++i )
     {
         unsigned long long incr = 1000000000000000000 * i ;
         std::cout << "increment:  " << incr << "\n\n" ;
         unsigned long long ubound = max - incr ;
         unsigned long long x = 0;

         for( ; x <= ubound ; x += incr ) std::cout << x << '\n' ;
         std::cout << x << '\n' ; // can't be incremented any more

         std::cout << "\n---------------------------\n\n" ;
     }
}

increment:  1000000000000000000

0
1000000000000000000
2000000000000000000
3000000000000000000
4000000000000000000
5000000000000000000
6000000000000000000
7000000000000000000
8000000000000000000
9000000000000000000
10000000000000000000
11000000000000000000
12000000000000000000
13000000000000000000
14000000000000000000
15000000000000000000
16000000000000000000
17000000000000000000
18000000000000000000

---------------------------

increment:  2000000000000000000

0
2000000000000000000
4000000000000000000
6000000000000000000
8000000000000000000
10000000000000000000
12000000000000000000
14000000000000000000
16000000000000000000
18000000000000000000

---------------------------

increment:  3000000000000000000

0
3000000000000000000
6000000000000000000
9000000000000000000
12000000000000000000
15000000000000000000
18000000000000000000

---------------------------

increment:  4000000000000000000

0
4000000000000000000
8000000000000000000
12000000000000000000
16000000000000000000

---------------------------

increment:  5000000000000000000

0
5000000000000000000
10000000000000000000
15000000000000000000

---------------------------

increment:  6000000000000000000

0
6000000000000000000
12000000000000000000
18000000000000000000

--------------------------

http://coliru.stacked-crooked.com/a/48c0b6d606da9858

[zapshe]

Not gonna lie, I'm just starting out and that code looks slightly complicated for me to understand - But that could just be because I haven't slept and it's hours into the AM. Will look over again after some rest, but it would be appreciated it you could break down the code and tell me what each part does. You don't have to though - Thanks for the help JLBorges !

[helios]

However, when x+=100000000000000000 (10^16) - It simply stops exactly at 184*k . However, if I add an extra 0, it will do as you said and loop over until x will become larger than 184*k - Even though adding another 0 still makes 184*k divisible by the number that it'll add. In fact, making x+= anything less than 10^17 will make it stop at exactly 184*k . It doesn't really make sense, but that's how it's working. Why?

2^64 - 184*k is greater than k/10, so 184*k + k/10 fits in a 64-bit integer, so the value doesn't loop around.

What determines whether the loop monotonically increases x is not the divisibility of the limit by the increment, but whether there exists an integer m such that limit < limit*m < 2^64.

[JLBorges]

#include <iostream>
#include <limits>

int main()
{
     // max is the largest value that unsigned long long can hold
     const auto max = std::numeric_limits<unsigned long long>::max() ;

     for( int i = 1 ; i < 7 ; ++i )
     {
         // the increment incr is 1000000000000000000 * i
         // ie. through the loop, incr becomes 1000000000000000000, 2000000000000000000
         //                           3000000000000000000 ... up to 6000000000000000000
         unsigned long long incr = 1000000000000000000 * i ;
         std::cout << "increment:  " << incr << "\n\n" ;

         unsigned long long x = 0;

         // ubound is the largest value of x to which we can add incr and
         // still not exceed the largest value that unsigned long long can hold
         unsigned long long ubound = max - incr ;

         // print values of x, in steps of incr, up to ubound
         for( ; x <= ubound ; x += incr ) std::cout << x << '\n' ;

         // at this point, x is still less than or equal to max, but we can't add
         // incr to it without breaching the largest value that unsigned long long can hold
         // print out this largest possible value that x reached
         // this is the last number printed out for this particular value of incr
         std::cout << x << '\n' ; // x can't be incremented any more

         std::cout << "\n---------------------------\n\n" ;
     }
}

[zapshe]

Thanks Helios, I understand now. Having x<= k makes the program unable to compute the last addition needed to complete the task since it would be greater than 2^64 - forcing it to jump to another number and begin adding again until it will be able to add k to achieve both x being greater than 184*k but less than 2^64. However, taking out a 0 (or multiple ones) allows it to compute since the 2^64 limit wont be breached when it tried to add one more time to make x greater than 184*k. -- My only question is that when it loops, why does it choose to subtract instead of doing something like crash or overload? Moreover, how does it know what to subtract? - since for the first subtraction, it will always take away roughly 183.47*k and then begin adding again.

Thanks JLBorges, looking at the code now I understand it better. However, I still haven't learned some of the functions that have been used and the way they've been used, so I don't think I'd be able to write a set of code like this, yet.

Thanks to both of you, it has been very informative. I'm going through a very good tutorial of C++, but I like to explore every nook and cranny when I get the chance to, it makes one learn better. So, you guys helping me has been a great help, thanks!

[helios]

My only question is that when it loops, why does it choose to subtract instead of doing something like crash or overload? Moreover, how does it know what to subtract? - since for the first subtraction, it will always take away roughly 183.47*k and then begin adding again.

I answered this in my first reply. Addition with n-bit unsigned operands is performed in modulo 2^n arithmetic:

result = (addend1 + addend2) % 2^n
result = (minuend - subtrahend + 2^n) % 2^n

(184*k + k) % 2^64 = 185 * k % 2^64 = 53255926290448384

binary(184*k)   =  1111111101011001111011101000001100111011001100000000000000000000
binary(k)       =         101100011010001010111100001011101100010100000000000000000
sum             = 10000000010111101001100111111101110011000101110100000000000000000
                  ^ bit 64
sum modulo 2^64 =          10111101001100111111101110011000101110100000000000000000

decimal(10111101001100111111101110011000101110100000000000000000) = 53255926290448384

https://www.wolframalpha.com/input/?i=185e%2B17+modulo+2%5E64

[zapshe]

Oh, that's right. Sorry to make you re-explain it. Thanks Helios !