During the past few lectures/sections, some attention has been paid to the issue of rounding errors, and the data type limitations of the modern digital computer. While I initially had no great interest in the topic, I did find myself thinking back to a problem posed to me some time ago by Dr. Robert Dumonceaux, a professor of mathematics at St. Johns University in central Minnesota. Given some prime number p, how can one determine the value of its reciprocal 1/p to an arbitrary number of decimal points using only a pocket calculator, a sheet of scratch paper, and the principals of mathematics? He went on to outline a simple yet effective algorithm (which still resides on my graphing calculator after 3 years) for solving this problem, which I will now attempt to share with those of you reading this.

First to establish some notation: Our prime number will simply be p. The precision of our computation device will be given by n, where n is the number of digits after the decimal we can be sure are accurate. Keep in mind that for a calculator that displays say, 11 digits, only 10 of these are correct, since the final place could be a rounded value. Finally we have rv, which will be our final return value. In a program this could be represented as a string; what’s important is that the number of digits we can store isn’t limited in the same way as standard number value data types.

1) The first step will be to calculate the value 1/p to the precision d provided by our computing device. This will yield some value of the form 0.d1d2d3….dn.

2) Place this value into rv

3) Multiply 0.d1d2d3…dn by the original prime p. Assuming your initial result was an approximation of a repeating decimal rather than an exact value (an issue which will be addressed later) this will result in a product of the form p0.p1p2p3…pn

4) Calculate the difference 1 – 0.p1p2p3…pn = 0.d1d2d3…dn

5) Removing the decimal point from this result, calculate the quotient
d1d2d3…dn/p = q0.q1q2q3…qn

6) Take the decimal portion of this result, and return to step 2 with 0.q1q2q3…qn as your new decimal.

Following the above algorithm, you can see that ever run though the steps will increase the precision of your answer by n decimal places. But when should you stop? Fortunately, prime numbers have a rather convenient property such the decimal representation of their reciprocal will repeat after AT MOST p-1 digits. So, for example, 1/7 = 0.142857142857… repeats after only 6 decimal places. Thus after calculating out this far, you can represent the value to whatever precision you wish.

Dr. D’s interest in this algorithm was for the purpose of examining patterns in the precise number of decimals after which a fraction would repeat. With relation to this present course, however, it represents just trick for overcoming the limitations in precision of modern computing devices. For (relatively) small values of p, this method is easily carried out with the aid of a calculator. For larger values, one may wish to write a proper computer program to perform the calculations and keep track of the return value. In pseudo-code (assuming a precision of ten digits) we have:

reciprocal(p) {
String rv = “0.”
s = toString(1/p)
for i, 1, ceiling(p/10) { //ensure we get all digits
while (length(s) < 11) append ‘0’ to s
rv = rv + all of s after the decimal point
temp = mod(p*s, 1)
s = toString(1 – temp)
while (length(s) < 11) appends ‘0’ to s
s = mod((value of s after the decimal)/p, 1)
}
}

Regarding the practical application of such an algorithm, I wasn’t really aware of the importance of prime reciprocals prior to making this post. After some online research, however, I found that they do in fact come up in a number of interesting areas. I post some examples below:

Analysis of Prime Reciprocal Sequences in Base 10

Prime Reciprocal Magic Squares:

Prime Reciprocals and the Euler Zeta Function