View Single Post
Old 2021-07-29, 02:22   #11
charybdis's Avatar
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
charybdis is offline   Reply With Quote