Project

General

Profile

Feature #13250

Initial estimate for Integer#sqrt should be improved

Added by Student (Nathan Zook) about 2 years ago. Updated about 2 years ago.

Status:
Closed
Priority:
Normal
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.

Associated revisions

Revision 4dcad25b
Added by nobu (Nobuyoshi Nakada) about 2 years ago

bignum.c: improve estimate

  • bignum.c (estimate_initial_sqrt, rb_big_isqrt): improve initial estimate by sqrt(). [ruby-core:79754] [Feature #13250]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@57713 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 57713
Added by nobu (Nobuyoshi Nakada) about 2 years ago

bignum.c: improve estimate

  • bignum.c (estimate_initial_sqrt, rb_big_isqrt): improve initial estimate by sqrt(). [ruby-core:79754] [Feature #13250]

Revision 57713
Added by nobu (Nobuyoshi Nakada) about 2 years ago

bignum.c: improve estimate

  • bignum.c (estimate_initial_sqrt, rb_big_isqrt): improve initial estimate by sqrt(). [ruby-core:79754] [Feature #13250]

Revision 57713
Added by nobu (Nobuyoshi Nakada) about 2 years ago

bignum.c: improve estimate

  • bignum.c (estimate_initial_sqrt, rb_big_isqrt): improve initial estimate by sqrt(). [ruby-core:79754] [Feature #13250]

History

Updated by Student (Nathan Zook) about 2 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) about 2 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) about 2 years ago

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

#4

Updated by nobu (Nobuyoshi Nakada) about 2 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]

Also available in: Atom PDF