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.
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).
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.)
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 longlong 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).
#include <iostream>
using std::cout;
using std::endl;
constint 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);
}
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:
1 2 3 4 5
for(int i = 0; i <= 100; i++)
{
int f = Fibonacci(i);
cout << "i: " << i << " f: " << f << endl;
}
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;
unsignedlonglong FiboCalled = 0;
unsignedint Fibonacci(unsignedint 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 unsignedlonglong 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.
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.
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).