3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible.
The function \(\operatorname { INT } ( X )\) gives the largest integer that is less than or equal to \(X\). For example: \(\operatorname { INT } ( 6.9 ) = 6\), \(\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7\).
| Line 10 | Input a positive integer, \(N\) |
| Line 20 | Let \(C = 1\) |
| Line 30 | If \(C ^ { 2 } \geqslant N\) jump to line 110 |
| Line 40 | Let \(X = \sqrt { \left( N - C ^ { 2 } \right) }\) [you may record your answer as a surd or a decimal] |
| Line 50 | Let \(Y = \operatorname { INT } ( X )\) |
| Line 60 | If \(X = Y\) jump to line 100 |
| Line 70 | If \(C > Y\) jump to line 110 |
| Line 80 | Add 1 to \(C\) |
| Line 90 | Go back to line 30 |
| Line 100 | Print \(C , X\) and stop |
| Line 110 | Print 'FAIL' and stop |
- Apply the algorithm to the input \(N = 500\). You only need to write down values when they change and there is no need to record the use of lines \(30,60,70\) or 90 .
- Apply the algorithm to the input \(N = 7\).
- Explain why lines 70 and 110 are needed.
The algorithm has order \(\sqrt { N }\).
- If it takes 0.7 seconds to run the algorithm when \(N = 3000\), roughly how long will it take when \(N = 12000\) ?