Issue #13250 has been updated by Nobuyoshi Nakada.


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.


----------------------------------------
Feature #13250: Initial estimate for Integer#sqrt should be improved
https://bugs.ruby-lang.org/issues/13250#change-63180

* Author: Nathan Zook
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
----------------------------------------
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.





-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>