Rice grains on a chessboard

[vmanrao]

Hey guys I'm a beginner with C++ and am doing a practice problem for my class and am having trouble figuring this problem out.

A man wants 1 grain for the 1st square on a chessboard. 2 grains on the 2nd. 4 grains on the 3rd. 8 grains for the 4th square. etc etc (doubling for each square)

I have to write a program that will tell me how many squares it would take to reach at least 1,000 grains of rice, 1,000,000 grains of rice, and 1,000,000,000 grains of rice.

Every thing has to be in INT's not doubles. If anyone can help me out it would be greatly appreciated. I'm completely lost on how to do this. Thanks!

[Banfa]

Have you written anything yet.

How about a program that prints out the number of grains of on each square for the first 31 squares? You can work on the limits later.

If you can't do a program like that then try using pen and paper to write down the number of grains of rice on the first 4 or 5 squares. Once you have the method for doing that translate it into a programable algorithm.

[donbock]

@vmanrao
You can't count the number of grains of rice with an INT -- the largest number guaranteed to fit in an unsigned INT on all compilers is 65535. You'll have to find a tricky way to solve the problem.

[Banfa]

Yes but if you take INT to mean integer arithmetic and take into account what's been asked to be calculated then you will notice that it does fit inside 32 bit integer arithmetic.

[whodgson]

On my machine declaring only ints, employing a for loop with the condition set to i<31 the squares hold the following number of rice grains:
boardsq 0 = 1
boardsq 1 = 2
boardsq 2 = 4
boardsq 3 = 8
boardsq 4 = 16
boardsq 5 = 32
boardsq 6 = 64
boardsq 7 = 128
boardsq 8 = 256
boardsq 9 = 512
boardsq 10 = 1024 <------
boardsq 11 = 2048
boardsq 12 = 4096
boardsq 13 = 8192
boardsq 14 = 16384
boardsq 15 = 32768
boardsq 16 = 65536
boardsq 17 = 131072
boardsq 18 = 262144
boardsq 19 = 524288
boardsq 20 = 1048576 <-------
boardsq 21 = 2097152
boardsq 22 = 4194304
boardsq 23 = 8388608
boardsq 24 = 16777216
boardsq 25 = 33554432
boardsq 26 = 67108864
boardsq 27 = 134217728
boardsq 28 = 268435456
boardsq 29 = 536870912
boardsq 30 = 1073741824 <-------
boardsq 31 = -2147483648
At square 31 the result returns a negative which is still valid if multiplied by -1
After square 31 the result returned is zero (0) ..... but in this case the requirements are met. Someone might like to suggest the pseudo code which will get to square no 64.

[donbock]

@vmanrao
Do you need to find the first square to hold that many grains of rice; or do you need to find the minimum number of squares such that the sum of all grains of rice is at least that number?

[donbock]

@whodgson
Do these values look strangely familiar? There is an elegant and very rapid algorithm lurking behind the pattern made by these values.

[newb16]

But in the base (namely , 2) where these numbers look familiar, numbers like 1000, 1000000 look unfamiliar and will require effort to implement arithmetic operation with multi-word precision.

[Banfa]

No because one of the beauties of C and C++ is the ability to use which ever base, 8, 10, 16(and by extension 2) is convenient at the time so you can use base 16(2) operations for calculation but base 10 operations for comparison.