From: jzakiya@...
Date: 2017-02-25T00:42:16+00:00
Subject: [ruby-core:79764] [Ruby trunk Feature#13250] Initial estimate for Integer#sqrt should be improved

Issue #13250 has been updated by Jabari Zakiya.


It would be nice if you backported this code into point releases of older versions too.

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

* 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>