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
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 π, we reduce k mod π by computing k – ⌊k/π⌋π. That is, we subtract off as many multiples of π as we can until we get a number between 0 and π. Going back to
bc, we compute
pi = 4*a(1) k/pi
and so we compute the tangent of
t = 0.500000507033221370444866152761*pi = 1.570797919686740002588270178941
Since t is slightly larger than π/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
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 ⌊k/π⌋ 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 ⌊k/π⌋π, but lost precision when we computed we subtracted that value from k.
Our error in computing k – ⌊k/π⌋π 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.
3 thoughts on “Arbitrary precision is not a panacea”
You might be interested in (or you may already be aware of) spigot (available from https://www.chiark.greenend.org.uk/~sgtatham/spigot/) which is a streaming exact real calculator.
It correctly calculated
>spigot.exe -d30 “let x = 1428599129020608582548671 in tan(x)-x”
(at least I assume the answer was correct – it confirmed that tan(x)>x at least) to 30 decimals more or less instantly. Your point from other posts about bc being available everywhere is a good one, but I am probably going to add spigot to my “personal toolbox” (it’s a single self contained executable).
This is an excellent point.
What should be possible is to track the error in the value. E.g., instead of reporting “3”, report “3 +/- something”. If you have two similar numbers, and you know your accuracy, then you can bound the error in the computation of the difference.
I would expect some tools to do this already?
Yes, you can do this with interval arithmetic. There are libraries for this, but I haven’t used them.