Discussion on: Daily Challenge #134 - Rice and Chessboard Problem

Here is an F# tail recursive bit shifting version;

let squaresNeeded (x:uint64) =
    let rec inner (grains:uint64) tile =
        match grains with
        | 0UL -> tile
        | _ -> inner (grains >>> 1) (tile + 1)

    inner x 0

In order to check it was doing tail recursion (F# doesn't tell you), I made this version using BigIntegers, which is no longer limited to a tiny 8x8 chess board;

let squaresNeededBig (x:bigint) =    
    let rec inner (grains:bigint) square =
        match grains with
        | z when z.IsZero -> square
        | _ -> inner (grains >>> 1) (square + 1)

    inner x 0

So, lets make a chess board with sides of 2^10, and therefore area of 2²⁰ (that's just the number of squares!). Then we can fill that, which is 2²²⁰ -1 grains of sand.

let squares = 1 <<< 20;
let grains =  (bigint.Pow((bigint 2), squares)-bigint.One)
printfn "Squares needed is %d" (squaresNeededBig grains)

And after a few seconds, it gives the correct answer, and confirms tail recursion. Not sure what the point of all that was, but I had a bit of fun with it!