Calculating the total number of grains of wheat and squares needed for x amount of wheat

[carl123]

There is a story of the inventor of chess. The king wanted to reward him with riches, but he only asked for the following. One grain of wheat for the first square, two on the second, four on the third, doubling the amount for each square until 64 squares are accounted for.

Questions

1) Design a program for calculating the total number of grains of wheat. You will want to use iteration/looping. Do not forget to keep track of which square you are on and the number of grains of wheat that you currently have.

2) Write the program to determine the number of squares needed to get at least 1000, 1,000,000 and 1,000,000,000 grains of wheat.


My code so far, works perfectly for number 1, Not sure how to go about number 2.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
int calc = 1;
int sqNum = 1;
unsigned long long total = 1;
cout << "Square " << sqNum << " has " << total << " grain of wheat" << endl;
for (int i = 1; i<64; ++i){
sqNum++;
calc = (calc * 2);
total = total + calc;
cout << "Square " << sqNum << " has " << total << " grains of wheat " << endl;

}

return 0;
}

[Peter87]

Are you sure number 1 is working? Print the value of calc for each step and I think you will see something go wrong.

For number 2 you need to check when the grains of wheat reaches the limit you are searching for. The loop variable will tell you how many squares are needed.

[Peter87]

And lets hope your unsigned long long has more than 64 bits otherwise you will not be able to store the final amount of grains.

[MiiNiPaa]

And lets hope your unsigned long long has more than 64 bits otherwise you will not be able to store the final amount of grains.

Actually total number of grains is 2⁶⁴ - 1, which fits in unsigned 64bit variable.

[Peter87]

MiiNiPaa wrote:

Actually total number of grains is 2⁶⁴ - 1, which fits in unsigned 64bit variable.

Yes you are right. I guess I thought something like this: The number of grains in square i is 2ⁱ so the last square contains 2⁶⁴ which is one too big to be stored in an unsigned 64-bit number.

But the first square contains only 1 grain so that means we need to count from zero (2⁰ = 1).

This is of course obvious when thinking how binary numbers work so I shouldn't have made the mistake. For some reason it's harder to think in terms of chessboard squares and grains of wheat. ;)

The code above is doing a similar mistake. It starts counting 2 grains on the first square.

[carl123]

Sorry, I'm not sure I understood what you meant. Can you explain further?

[Peter87]

Don't get confused by my last post. It was mostly aimed at MiiNiPaa.

Back to the problem with "number 1". Have you printed the value of calc? What do you see happens?