What is the limit on for loop boundary?

[Moonraker101]

I really want to know what the limit of a for loop boundary is. By boundary I mean the constraint portion of the for loop. For example, the program that I am working on requires that I obtain the sum total of even integers that do not exceed 4 million. Here is some sample code:

const int limit = 4000000
.
.
.
.
int main()
{
for(int i = 0; i < limit; i++) // i has to be less than 4 million
{
. // Don't want to bore you with the details
.
.
.
.
}

return 0
}

The problem is I don't get a value. When I change the limit variable to 10 I do get a sum value. I read somewhere that it depends on hardware and OS. Is this true? Is there a way around this?

If you need more information regarding the source code let me know. Thanks in advance.

[Hippogriff]

I have never heard of a limit on a for loop, it just depends on how fast your CPU is and how fast your computer can read through them all.

4000000 will take quite a while to loop through, you might want to think of ways to optimize the code without just brute forcing through every number. (I would give you examples but my math skills aren't exactly great).

(I think I actually did this project euler problem before, but I forgot the exact way I solved it).

[Raezzor]

There is no limit on how many time it will run except for what you code. If you are having a problem it might be somewhere else. Without seeing the rest of your code it's hard to tell. Also, please use code tags when posting code (<> on the right of the text box when replying or editing.)

[toum]

The limit is the maximum value an int can contain, which is 2 147 483 647.

[m4ster r0shi]

the sum total of even integers that do not exceed 4 million

You don't need a computer for this. What you want is...

2 + 4 + 6 + 8 + ... + 4000000 =

2 * (1 + 2 + 3 + 4 + ... + 2000000) =

2 * (2000000 * 2000001 / 2) =

2000000 * 2000001 =

4000002000000

However, this is not what problem 2 from project
euler asks... http://projecteuler.net/problem=2

[Chervil]

The problem is not the for loop itself.
Rather it is simple arithmetic overflow of the total field.

This is the important part of the code (quote):
// Don't want to bore you with the details

The correct answer is 3999998000000 which requires 42 bits to store as an integer.
Try using type long long for the field which accumulates the total. That should be at least 64 bit long and able to correctly hold the result. (You might also use a floating-point value such as double or long double to hold the result).

(I quote the result for even integers lass than 4 million. If the requirement is less than or equal to 4 million, adjust accordingly).

[Moonraker101]

Thanks for the quick responses guys, I appreciate it.
Here is the full source code:

#include <iostream>

using std::cout;
using std::endl;

const int limit = 4000000;

int Fibonacci(int num);   // Prototype Function


int main()
{
	int sum = 0;

	for(int i = 0; i <= limit; i++)
	{
	    if(Fibonacci(i) % 2 == 0)   // If Fibonacci number is even then add to the sum
		{
			sum += Fibonacci(i);

		     
		}

	}

	cout << "Answer: " << sum  << endl;

	system("Pause");
   return 0;
}


int Fibonacci(int num)
{
	if(num == 0)     // Prevents awkward negative number in the equation below, simply returns a 0 or a 1 
		return 0;    //
	if(num == 1)     //
		return 1;    //

	return Fibonacci(num  -  1) + Fibonacci(num - 2);

}

[m4ster r0shi]

By considering the terms in the Fibonacci sequence whose values
do not exceed four million, find the sum of the even-valued terms.

Read ^ this ^ carefully.

It's Fibonacci(i) that must not exceed four million; not i.

[Chervil]

The problem here is the recursive function Fibonacci()
This is an extremely inefficient algorithm, though it is an interesting one for studying recursion.

In a purely practical task such as this, you need a faster method, such as using static variables to retain the previous two terms in the series.

Try this to see how slowly it executes:

    for(int i = 0; i <= 100; i++)
    {
        int f = Fibonacci(i);
        cout << "i: " << i << "    f: " << f << endl;
    }

[Chervil]

I don't know about the actual question, the previous post may be the answer:

It's Fibonacci(i) that must not exceed four million; not i.

But anyway, a demonstration of how the Fibonnacci function works. This program simply counts how many times the function is called on each iteration. The count is reset to zero each time.

#include <iostream>
#include <iomanip>

    using std::cout;
    using std::endl;
    using std::setw;

unsigned long long FiboCalled = 0;

unsigned int Fibonacci(unsigned int num)
{
    FiboCalled++;    // count how many times function is called.

    if (num < 2)
        return num; // Simply returns a 0 or a 1

    return Fibonacci(num - 1) + Fibonacci(num - 2);
}

int main()
{
    for (int i=0; i< 100; i++)
    {
        FiboCalled = 0; // initialise count
        cout << " i: " << setw(3) << i
             << " Fibonacci(i): " << setw(11) << Fibonacci(i);
        cout << "       Called " << setw(12) << FiboCalled << " times" << endl;
    }

    return 0;
}

After the 47th term, the 32-bit integer is not large enough to hold the result, and overflow occurs. You could switch to type unsigned long long which will work up to about 93 terms. Beyond that, a bigint library may be required.

 i:   0 Fibonacci(i):           0       Called            1 times
 i:   1 Fibonacci(i):           1       Called            1 times
 i:   2 Fibonacci(i):           1       Called            3 times
 i:   3 Fibonacci(i):           2       Called            5 times
 i:   4 Fibonacci(i):           3       Called            9 times
 i:   5 Fibonacci(i):           5       Called           15 times
 i:   6 Fibonacci(i):           8       Called           25 times
 i:   7 Fibonacci(i):          13       Called           41 times
 i:   8 Fibonacci(i):          21       Called           67 times
 i:   9 Fibonacci(i):          34       Called          109 times
 i:  10 Fibonacci(i):          55       Called          177 times
 i:  11 Fibonacci(i):          89       Called          287 times
 i:  12 Fibonacci(i):         144       Called          465 times
 i:  13 Fibonacci(i):         233       Called          753 times
 i:  14 Fibonacci(i):         377       Called         1219 times
 i:  15 Fibonacci(i):         610       Called         1973 times
 i:  16 Fibonacci(i):         987       Called         3193 times
 i:  17 Fibonacci(i):        1597       Called         5167 times
 i:  18 Fibonacci(i):        2584       Called         8361 times
 i:  19 Fibonacci(i):        4181       Called        13529 times
 i:  20 Fibonacci(i):        6765       Called        21891 times
 i:  21 Fibonacci(i):       10946       Called        35421 times
 i:  22 Fibonacci(i):       17711       Called        57313 times
 i:  23 Fibonacci(i):       28657       Called        92735 times
 i:  24 Fibonacci(i):       46368       Called       150049 times
 i:  25 Fibonacci(i):       75025       Called       242785 times
 i:  26 Fibonacci(i):      121393       Called       392835 times
 i:  27 Fibonacci(i):      196418       Called       635621 times
 i:  28 Fibonacci(i):      317811       Called      1028457 times
 i:  29 Fibonacci(i):      514229       Called      1664079 times
 i:  30 Fibonacci(i):      832040       Called      2692537 times
 i:  31 Fibonacci(i):     1346269       Called      4356617 times
 i:  32 Fibonacci(i):     2178309       Called      7049155 times
 i:  33 Fibonacci(i):     3524578       Called     11405773 times
 i:  34 Fibonacci(i):     5702887       Called     18454929 times
 i:  35 Fibonacci(i):     9227465       Called     29860703 times
 i:  36 Fibonacci(i):    14930352       Called     48315633 times
 i:  37 Fibonacci(i):    24157817       Called     78176337 times
 i:  38 Fibonacci(i):    39088169       Called    126491971 times
 i:  39 Fibonacci(i):    63245986       Called    204668309 times
 i:  40 Fibonacci(i):   102334155       Called    331160281 times
 i:  41 Fibonacci(i):   165580141       Called    535828591 times
 i:  42 Fibonacci(i):   267914296       Called    866988873 times
 i:  43 Fibonacci(i):   433494437       Called   1402817465 times
 i:  44 Fibonacci(i):   701408733       Called   2269806339 times
 i:  45 Fibonacci(i):  1134903170       Called   3672623805 times
 i:  46 Fibonacci(i):  1836311903       Called   5942430145 times
 i:  47 Fibonacci(i):  2971215073       Called   9615053951 times
 i:  48 Fibonacci(i):   512559680       Called  15557484097 times
 i:  49 Fibonacci(i):  3483774753       Called  25172538049 times

But anyway, there are much faster and more efficient ways to to calculate each term, which use iteration rather than recursion.

[Cubbi]

there are much faster and more efficient ways to to calculate each term, which use iteration rather than recursion.

Iteration rather than or recursion.
Both can be easily used to calculate fibonaccis in O(n) or even O(log n) calls/iterations. In my opinion, the recursive solutions for O(log n) are easier to understand.

[Chervil]

@ Cubbi. Useful comment. Thanks.

[Darkmaster]

shouldnt the limit of for(int i =0; i<limit; ++i) be the maximum number an integer can be?

[Chervil]

The limit would be when overflow occurs while calculating a particular term. I think that would have to be done within the Fibonacci function itself (maybe set a bool flag, or set the result to zero or something).