From: nobu@... Date: 2017-02-24T22:29:09+00:00 Subject: [ruby-core:79757] [Ruby trunk Feature#13250] Initial estimate for Integer#sqrt should be improved 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: