3 ms·
It's easy to compute things quickly if you pretend that you can do arbitary-precision arithmetic in constant time. Want a quadrillion digits of Pi? Easy, just
by cperciva 12y ago
It's easy to compute things quickly if you pretend that you can do arbitary-precision arithmetic in constant time. Want a quadrillion digits of Pi? Easy, just use the Brent–Salamin AGM algorithm and you'll get them in about 500 arithmetic operations. NP-complete problems? No problem at all, rephrase them as subset-sum problems and use the polynomial-integer-operations dynamic programming algorithm. I don't think you can solve PSPACE in a polynomial number of integer operations, but I can't see how to prove it immediately.
In "real" terms, computing the Nth fibonacci number takes O(M(N)) = O(N log N 2^(O(log* N))) operations.
- fdej 12y agoMinor pedantry: the best proved bound for M(N) is O(N log N 8^(log* N)). You can easily pretend that log* N is constant, though...
- cperciva 12y agoOops, forgot the O() inside the exponential. Fixed, thanks.
- Spiritus 12y agoOut of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.
- antics 12y agoThis is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of problems. For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time. So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis. Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.
- phireal 12y agoIt's Colin Percival: author of tarsnap, former BSD security officer and considered something of an authority on crytography. I presume his maths skills are therefore suitably well polished to be able to pull this stuff from memory.
- antics 12y agoI want to dispel the rumor that this is magic. This is standard material in undergrad algorithms classes. See, for example, Jeff Erickson's algorithms notes here[1]. It's literally the first page of the chapter on dynamic programming. [1] http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf http://web.engr.illinois.edu/~jeffe/teaching/algorithms/note...
- phireal 12y agoI appreciate that it's not magic and agree that it should be demystified. Having said that, doing it once in the past in an undergrad class and remembering it 10 years later when a relevant article on some website is posted are two different things.
- raverbashing 12y agoYeah, but "kids these days" only want to know Java or Angular.js and bawl at the first sight of math.
- cperciva 12y ago
- tomp 12y agoHe's in cryptography, he also started university at age 13. https://news.ycombinator.com/item?id=35076 https://news.ycombinator.com/item?id=35076
- tomp 12y agoAnother similar "algorithm": sleep sort. Basically, take a list of integers, and for each element n create a thread that sleeps n seconds, after which it appends n to the result list. Assuming the original list is dense (there are no gaps between integers), we can sort it in O(n)! :)
- robinhouston 12y agoEven if the computation could be done by magic, simply writing the result to memory would take O(n) operations, since the nth Fibonacci number has O(n) bits.