Meme of two women fighting while a man smokes from a pipe in the background.
The women fighting are labeled "mathematicians defining pi" and "engineers just using 3 because it's within tolerance"
The man smoking is labeled "astrophysicists" and the pipe is labeled "pi = 1"
Computer science: pi is O(1)
Is 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 usually a constant (or several ones with varying degrees of accuracy and size)
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.
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.
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
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.
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
It all depends on the precision you need. You could use an infinite series to get to the precision needed but for most use-cases it’s just a double baked into the binary itself, hence O(1)