Introduction
There once was a wise servant who saved the life of a prince.
The king promised to pay whatever the servant could dream up.
Knowing that the king loved chess, the servant told the king he would like to have grains of wheat.
One grain on the first square of a chessboard, with the number of grains doubling on each successive square.
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
