Comment on Order of magnitude is a hell of a drug
Gustephan@lemmy.world 1 day agoDo said atomic instructions produce pi though, or some functional approximation of pi? I absolutely buy that approximate pi is O(1), but it still seems like a problem involving a true irrational number should be undecidable on any real turing machine
What would be the “n” in that Big O notation, though?
If you’re saying that you want accuracy out to n digits, then there are algorithms with specific complexities for calculating those. But that’s still just an approximation, so those aren’t any better than the real-world implementation method of simply looking up that constant rather than calculating it anew.
I guess n would be infinite in the limit I’m looking for. I’m looking at this in like a “musing about theoretical complexity” angle rather than actually needing to use or know how to use pi on modern systems.
For the record, I realize how incredibly pedantic I’m being about the difference between the irrational pi and rational approximations of pi that end up being actually useful. That being said, computational complexity has enough math formalism stink on it that pedantry seems encouraged
“Modern” is a bit misleading, x87 had fldpi. The whole x87 part of the standard has been deprecated with x86_64 in favour of the whole sse series of instructions and those don’t come with pi. You instead load a constant from program memory, just like any other.
As processors (as of yet) still support those legacy modes they will also contain the constant somewhere in probably microcode storage, calculating it on the fly makes literally no sense at all: It’s (for x87) 80 bits of data, much shorter than any imaginable program, smaller than any circuitry able to compute it so you’d be spending time to save no space which is pointless.
ARM, RISC-V etc. come from the RISC tradition so they wouldn’t be caught dead including such an instruction. Both have zero registers though as zero is an absurdly useful constant, simplifying things drastically, both on the hardware front as well as within the instruction set (move is add zero to source, save to destination, clear is add zero and zero, save to destination)
Now, that’s finite constants. In particular, it’s about floating point arithmetic, which is a wonder of maths and a deep rat’s nest of numerology, but has finite precision, it’s not true real arithmetic. Real real arithmetic is undecidable, in particular comparison and expansion to decimal form are undecidable. Printing infinite strings of digits is usually not what we want to do, and limiting precision of comparisons is… not ideal, but better than having limited precision at every operation: You can decide once you’re comparing how accurate you want things to be and don’t have to worry while writing down your formula (btw Herbie exists, and that’s why packages like this exist. In that case pi is not a constant but a formula, wait, here: 4 * (atan(1/5) / 2 - atan(239)), which can be expanded as needed. Quite slow compared to floating point hardware but when you need it you need it and even if you don’t it’s still useful as a sanity check, gives you an idea of how far off the floating point results are without having to call in a favour with a mathematician.
TonyTonyChopper@mander.xyz 21 hours ago
The “true value of pi” is too large for any computer to store. Our current understanding of numbers says it’s an infinite number of digits. On the other hand, any number you use to multiply with pi is far less than an infinite number of digits. So you get the correct answer, with no worse precision than your input value, using the approximations of pi.