3 ms·
Draw 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 meanin
by cyber_kinetist 5y ago
Draw 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.