Comment on Order of magnitude is a hell of a drug
Gustephan@lemmy.world 1 day agoIs it actually? I’ll admit im pretty rusty on time complexity, but naively I’d think that pi being irrational would technically make even reading or writing it from memory an undecidable problem
It’s a number and complexity refers to functions. The natural inclusion of numbers into functions maps pi to the constant function x -> pi which is O(1).
If you want the time complexity of an algorithm that produces the nth digit of pi, the best known ones are something like O(n log n) with O(1) being impossible.
It’s usually a constant (or several ones with varying degrees of accuracy and size)
It all depends on the precision you need. You could use an infinite series to the the precision needed as you go but for most use-cases it’s just a double baked into the binary itself, hence O(1)
18107@aussie.zone 1 day ago
If you’re trying to calculate it, then it’s quite difficult.
If you just want to use it in a computer program, most programming languages have it as a constant you can request. You get to pick whether you want single or double precision, but both are atomic (a single instruction) on modern computers.
Gustephan@lemmy.world 1 day ago
Do 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
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.
exasperation@lemmy.dbzer0.com 23 hours ago
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.
Gustephan@lemmy.world 18 hours ago
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
barsoap@lemm.ee 21 hours ago
“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.