Grains

Instructions

Calculate the number of grains of wheat on a chessboard.

A chessboard has 64 squares. Square 1 has one grain, square 2 has two grains, square 3 has four grains, and so on, doubling each time.

Write code that calculates:

• the number of grains on a given square
• the total number of grains on the chessboard

GNU awk and Arbitrary Precision Arithmetic

By default, numbers in awk are represented as double-precision floating point numbers. This provides 53 bits of precision (see Table 16.3 in the manual). Unfortunately, this is insufficient to complete this exercise (spoiler alert, one test requires 63 bits of precision).

"Insufficient precision" looks like this:

$ gawk 'BEGIN {
  n = 2 ^ 54
  if (n == n + 1)
    print "not enough precision"
  else
    print "OK"
}'

not enough precision

GNU awk has the capability to use arbitrary-precision numbers, if the relevant libraries have been compiled into the awk executable. Check your awk version, and look for "GNU MPFR":

$ gawk --version
GNU Awk 5.0.1, API: 2.0 (GNU MPFR 4.0.2, GNU MP 6.2.0)
...

If it's present, enable the capability using the -M option:

$ gawk -M 'BEGIN {
  n = 2 ^ 54
  if (n == n + 1)
    print "not enough precision"
  else
    print "OK"
}'

OK

What if my awk doesn't have -M? You'll have to call out to an external program that can do arbitrary precision arithmetic, like bc. See the section Using getline into a Variable from a Pipe for an example how to do this.

Further reading: Arbitrary Precision Arithmetic

---

Source

The CodeRanch Cattle Drive, Assignment 6