Arbitrary precision is not a panacea
Having access to arbitrary precision arithmetic does not necessarily make numerical calculation difficulties go away. You still need to know what you're doing.
Before you extend precision, you have to know how far to extend it. If you don't extend it enough, your answers won't be accurate enough. If you extend it too far, you waste resources. Maybe you're OK wasting resources, so you extend precision more than necessary. But how far is more than necessary?
As an example, consider the problem of finding values of n such that tan(n) > n discussed a couple days ago. After writing that post, someone pointed out that these values of n are one of the sequences on OEIS. One of the values on the OEIS site is
k = 1428599129020608582548671.
Let's verify that tan(k) > k. We'll use our old friend bc because it supports arbitrary precision. Our k is a 25-digit number, so lets tell bc we want to work with 30 decimal places to give ourselves a little room. (bc automatically gives you a little more room than you ask for, but we'll ask for even more.)
bc doesn't have a tangent function, but it does have s() for sine and c() for cosine, so we'll compute tangent as sine over cosine.
$ bc -l scale = 30 k = 1428599129020608582548671 s(k)/c(k) - k
We expect this to return a positive value, but instead it returns
-1428599362980017942210629.31"
So is OEIS wrong? Or is bc ignoring our scale value? It turns out neither is true.
You can't directly compute the tangent of a large number. You use range reduction to reduce it to the problem of computing the tangent of a small angle where your algorithms will work. Since tangent has period I, we reduce k mod I by computing k - ak/IaI. That is, we subtract off as many multiples of I as we can until we get a number between 0 and I. Going back to bc, we compute
pi = 4*a(1) k/pi
This returns
454737226160812402842656.500000507033221370444866152761
and so we compute the tangent of
t = 0.500000507033221370444866152761*pi = 1.570797919686740002588270178941
Since t is slightly larger than I/2, the tangent will be negative. We can't have tan(t) greater than k because tan(t) isn't even greater than 0. So where did things break down?
The calculation of pi was accurate to 30 significant figures, and the calculation of k/pi was accurate to 30 significant figures, given our value of pi. So far has performed as promised.
The computed value of k/pi is correct to 29 significant figures, 23 before the decimal place and 6 after. So when we take the fractional part, we only have six significant figures, and that's not enough. That's where things go wrong. We get a value ak/Ia that's greater than 0.5 in the seventh decimal place while the exact value is less than 0.5 in the 25th decimal place. We needed 25 - 6 = 19 more significant figures.
This is the core difficulty with floating point calculation: subtracting nearly equal numbers loses precision. If two numbers agree to m decimal places, you can expect to lose m significant figures in the subtraction. The error in the subtraction will be small relative to the inputs, but not small relative to the result.
Notice that we computed k/pi to 29 significant figures, and given that output we computed the fractional part exactly. We accurately computed ak/IaI, but lost precision when we computed we subtracted that value from k.
Our error in computing k - ak/IaI was small relative to k, but not relative to the final result. Our k is on the order of 1025, and the error in our subtraction is on the order of 10-7, but the result is on the order of 1. There's no bug in bc. It carried out every calculation to the advertised accuracy, but it didn't have enough working precision to produce the result we needed.
Related posts