On Sun, 22 Mar 2020 at 22:16, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> With resolutions of the XXX items, I think this'd be committable.
>
Thanks for looking at this!
Here is an updated patch with the following updates based on your comments:
* Now uses integer arithmetic to compute res_weight and res_ndigits,
instead of floor() and ceil().
* New comment giving a more detailed explanation of how blen is
chosen, and why it must sometimes examine the first digit of the input
and reduce blen by 1 (which can occur at any step, as shown in the
example given).
* New comment giving a proof that the number of steps required is
guaranteed to be less than 32.
* New comment explaining why the initial integer square root using
Newton's method is guaranteed to converge. I couldn't find a formal
reference for this, but there's a Wikipedia article on it -
https://en.wikipedia.org/wiki/Integer_square_root and I think it's a
well-known result in the field.
Regards,
Dean