Feature #13250
closedInitial estimate for Integer#sqrt should be improved
Description
r57705, by Nobu, in response to issue #13219, added Integer#sqrt. The initial estimator used is 1 << (b-1)/2 | n >> (b+1)/2
. For this style of estimator, 1 << (b-1)/2 | n >> (b+3)/2
would be best. (Basically, there is a fencepost error in the current commit.)
However, much better initial estimates can be made. In particular, using the hardware floating point square root will almost certainly eliminate 3-4 rounds of approximation. Even for smaller numbers, this represents a substantial gain.
If for some reason, it is problematic to use fsqrt, a small table lookup can eliminate a couple of rounds.
Updated by Student (Nathan Zook) over 7 years ago
Think about this some more, the fastest solution would be to actually to a N-R round in the floating point unit as well. I will have something in a few days.
Updated by nobu (Nobuyoshi Nakada) over 7 years ago
Nathan Zook wrote:
The initial estimator used is
1 << (b-1)/2 | n >> (b+1)/2
. For this style of estimator,1 << (b-1)/2 | n >> (b+3)/2
would be best. (Basically, there is a fencepost error in the current commit.)
It is (1 << (b-1)/2) | (n >> (b/2+1))
(+1 after /2), which equals the latter formula.
Updated by jzakiya (Jabari Zakiya) over 7 years ago
It would be nice if you backported this code into point releases of older versions too.
Updated by nobu (Nobuyoshi Nakada) over 7 years ago
- Status changed from Open to Closed
Applied in changeset r57713.
bignum.c: improve estimate
- bignum.c (estimate_initial_sqrt, rb_big_isqrt): improve initial
estimate by sqrt(). [ruby-core:79754] [Feature #13250]