Project

General

Profile

Actions

Feature #13250

closed

Initial estimate for Integer#sqrt should be improved

Added by Student (Nathan Zook) over 7 years ago. Updated over 7 years ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:79754]

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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0