Photo by travelnow.or.crylater on Unsplash

Reflections on The Square Root of Two

A brief tutorial on the square root of two calculation and digit counting in hexadecimal base.

Recently our software development team recruited a new team member and we had to concoct a home exam in order to filter out less than suitable candidates. Oddly enough, none of our candidates passed the test. Therefore, we wanted to share our test as a short tutorial for the benefit of the community.

The original question reads as follows: ”Regarding sqrt(2), when written in decimal form 1 occurs 99925 times in the first 1 million digits. how many times does the digit 2 occur in the first 1 million hexadecimal digits?

Such as most other things in life this question too has a one line solution, this time using bc (the arbitrary precision calculator). The scale parameter needs to be a bit above 1000000 in order to get the required number of digits in the result.

echo ‘obase=16;scale=1204120;sqrt(2)’ | bc | grep 2 -o | wc -l

Alas, since we wanted to test the candidates` proficiency in C++ we could not accept this solution although the multilingual programmer could verify this way that the final answer should indeed be 62603.

A more relevant solution would be writing a class in C++ capable of arbitrary precision calculation and then implementing one of the square root algorithms. Following is such a solution.

Note that there are other implementations to arbitrary precision calculation in C++, like this one called after its counterpart class in JAVA . The difference being that the following implementation focus on the task at hand and as such it is not as general and as a consequence it is also simpler to understand.

First, lets look at the header. Notice we set the base to 16, any other value will give you the correct answer in that other base. An optimization could be made here since the running time of the square root algorithm we use depends on the number of digits computed. We could save considerable amount of time by setting base to be a very large number (e.g. 1e9) but this would entail converting the result to hexadecimal display in order to count the occurrences of the required digit.

And the implementation of the arbitrary precision operations are mostly straightforward. Notice that for this tutorial we do not need to implement negative numbers and this further simplifies the implementation.

The root square itself is based on this description of the Shifting Nth root algorithm with one major simplification that we did not have to worry with alignment since we are taking the square of a one digit number. Notice that each iteration adds another digit to the result.

Lastly, for the purpose of presenting the results, here is the main routine

To conclude, we have presented here a solution to the problem of counting a particular digit in an arbitrarily precise square root of two. As an added bonus the solution would also work for any other base. And for the brave hearts among the readers we have also suggested a way to optimize the solution for speed. We hope you have enjoyed this tutorial and hope that you will find it useful one day.