3 ms·
>you can even precisely compute irrational numbers like sqrt(2) to their limits of precision in o(1). Can you elaborate? I have a feeling they would also be O(
by charcircuit 5y ago
>you can even precisely compute irrational numbers like sqrt(2) to their limits of precision in o(1).
Can you elaborate? I have a feeling they would also be O(1) on digital computers.
- cyber_kinetist 5y agoDraw a square (using a compass), calculate its diagonal length, voila. Though it really depends on the accuracy of your compass and ruler, and it's kinda meaningless to do any complexity analysis (what even is 'N' in this case?) For digital computers, square-root algorithms that calculate digit-by-digit would take O(N), if you take N as the number of digits. If your precision is fixed, then you can get an approximate solution by using iterative methods (like Newton-Raphson). In that case, the complexity would be more like O(log(N) f(N)) to calculate up to N digits (where f(N) is the cost of doing one iteration with N-bit numbers)
- charcircuit 5y agoif you have m-bit numbers you can simply loop all of them and find which one when squared is closest to 2. This alogrithm will run in O(1). Alternatively you can do the same thing with drawing a square and measuring the distance between the center and the corner. Perhaps it's a little cheaty since you have to include a precomputed sprt(2) for the diagonal length of a pixel.