Thread: Why this code converge? View Single Post
 2021-07-29, 02:22 #11 charybdis     Apr 2020 11010101112 Posts Write $$\left\lceil \sqrt{b^2-a} \right\rceil$$ as $$\sqrt{b^2-a}+\epsilon$$, where $$\epsilon$$ is between 0 and 1. Let's see what happens when we square this. We get $$b^2-a+2\epsilon\sqrt{b^2-a}+\epsilon^2$$. We know that $$b^2-a$$ is a multiple of p, so the value of b on the next iteration is at most (and turns out to be equal to) $$2\epsilon\sqrt{b^2-a}+\epsilon^2$$, which is around $$2\epsilon b$$ (until b gets close to sqrt(p), when it will tend to be smaller; for b < sqrt(p) it will be 0). In other words, we multiply b by $$2\epsilon$$ to get the new value of b. If $$\epsilon$$ behaved like a uniformly random number between 0 and 1, then we would expect values of b to decrease in the long term (exercise: what is the expected rate of decrease?). From the Taylor expansion we see that $$\epsilon$$ is roughly equal to the fractional part of $$\frac{a}{2b}$$. For small b this does behave essentially like a uniformly random number between 0 and 1; for some larger b it is skewed towards the smaller end, but this still means we expect b to fall. There may be a neater explanation; this is just the first thing I came up with. Last fiddled with by charybdis on 2021-07-29 at 02:35