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

[Andreas Jakof]

this reminds me of my goal to learn more F#. I can express the same in C#, but still.

Nevertheless ... A chessboard has 64 tiles and even with a double, there are not enough bits to fully represent the complete number if you are coming closer to the 64 bit necessary for the last tile (double has 15-17 digits precision, UInt64.MaxValue will need 20 digits).

Although the approach is very elegant, there is (sadly) no Math.Log for Decimal types in .NET., which would have had enough bits. Hence a simple shift loop (or tail recursion in F#) would be more feasable?

[Nick Holmes]

Indeed.

There is a BigInteger in .Net (bigint in F#), and this does have a Log function. However, the log function (needs to) return a Double. Bottom line, log(2⁶³⁾ and log(2⁶³ +2¹⁰⁾ both return exactly 63. There is only a difference from 2¹¹ upwards.

[Nick Holmes]

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!