From: blogger@... Date: 2017-02-24T09:11:16+00:00 Subject: [ruby-core:79746] [Ruby trunk Feature#13219] bug in Math.sqrt(n).to_i, to compute integer squareroot, new word to accurately fix it Issue #13219 has been updated by Nathan Zook. Jabari Zakiya wrote: > Oh I see where at least part of the error comes from. > > In this > > ``` > def inverse_newton_sqrt(n) > raise if n < 0 > return Math.sqrt(n).to_i if n < 1 << 53 > ``` > > See top of this thread at ``#1 `` > I showed earlier I found that **Math.sqrt(n).to_i** starts given incorrect > results for n > 9_999_899_999_899_999_322_536_673_279 > > I replaced ``if n < 1 << 53`` with ``if n <= 9_999_899_999_899_999_322_536_673_279 `` > > This eliminated the shown errors upto n = 10**40, when it started to be one-off again. > > This is on a 64-bit Linux OS I7 cpu laptop. Actually, with some understanding of how floating point arithmetic works, the first even root past 1 << 53 is likely to be bad: ~~~ irb(main):1081:0> def msi(n) x = Math.sqrt(n).to_i big = x * x > n small = x * x + 2 * x < n puts [n, x, big, small] end irb(main):1082:0> msi(1<<53) 9007199254740992 94906265 false false => nil irb(main):1083:0> msi(94906266 ** 2 - 1) 9007199326062755 94906266 true false => nil ~~~ ;) ---------------------------------------- Feature #13219: bug in Math.sqrt(n).to_i, to compute integer squareroot, new word to accurately fix it https://bugs.ruby-lang.org/issues/13219#change-63171 * Author: Jabari Zakiya * Status: Closed * Priority: Normal * Assignee: * Target version: ---------------------------------------- In doing a math application using **Math.sqrt(n).to_i** to compute integer squareroots of integers I started noticing errors for numbers > 10**28. I coded an algorithm that accurately computes the integer squareroot for arbirary sized numbers but its significantly slower than the math library written in C. Thus, I request a new method **Math.intsqrt(n)** be created, that is coded in C and part of the core library, that will compute the integer squareroots of integers accurately and fast. Here is working highlevel code to accurately compute the integer squareroot. ``` def intsqrt(n) bits_shift = (n.to_s(2).size)/2 + 1 bitn_mask = root = 1 << bits_shift while true root ^= bitn_mask if (root * root) > n bitn_mask >>= 1 return root if bitn_mask == 0 root |= bitn_mask end end def intsqrt1(n) return n if n | 1 == 1 # if n is 0 or 1 bits_shift = (Math.log2(n).ceil)/2 + 1 bitn_mask = root = 1 << bits_shift while true root ^= bitn_mask if (root * root) > n bitn_mask >>= 1 return root if bitn_mask == 0 root |= bitn_mask end end require "benchmark/ips" Benchmark.ips do |x| n = 10**40 puts "integer squareroot tests for n = #{n}" x.report("intsqrt(n)" ) { intsqrt(n) } x.report("intsqrt1(n)" ) { intsqrt1(n) } x.report("Math.sqrt(n).to_i") { Math.sqrt(n).to_i } x.compare! end ``` Here's why it needs to be done in C. ``` 2.4.0 :178 > load 'intsqrttest.rb' integer squareroot tests for n = 10000000000000000000000000000000000000000 Warming up -------------------------------------- intsqrt(n) 5.318k i/100ms intsqrt1(n) 5.445k i/100ms Math.sqrt(n).to_i 268.281k i/100ms Calculating ------------------------------------- intsqrt(n) 54.219k (�� 5.5%) i/s - 271.218k in 5.017552s intsqrt1(n) 55.872k (�� 5.4%) i/s - 283.140k in 5.082953s Math.sqrt(n).to_i 5.278M (�� 6.1%) i/s - 26.560M in 5.050707s Comparison: Math.sqrt(n).to_i: 5278477.8 i/s intsqrt1(n): 55871.7 i/s - 94.47x slower intsqrt(n): 54219.4 i/s - 97.35x slower => true 2.4.0 :179 > ``` Here are examples of math errors using **Math.sqrt(n).to_i** run on Ruby-2.4.0. ``` 2.4.0 :101 > n = 10**27; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 1000000000000000000000000000 31622776601683 999999999999949826038432489 31622776601683 999999999999949826038432489 31622776601683 999999999999949826038432489 => nil 2.4.0 :102 > n = 10**28; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 10000000000000000000000000000 100000000000000 10000000000000000000000000000 100000000000000 10000000000000000000000000000 100000000000000 10000000000000000000000000000 => nil 2.4.0 :103 > n = 10**29; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 100000000000000000000000000000 316227766016837 99999999999999409792567484569 316227766016837 99999999999999409792567484569 316227766016837 99999999999999409792567484569 => nil 2.4.0 :104 > n = 10**30; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 1000000000000000000000000000000 1000000000000000 1000000000000000000000000000000 1000000000000000 1000000000000000000000000000000 1000000000000000 1000000000000000000000000000000 => nil 2.4.0 :105 > n = 10**31; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 10000000000000000000000000000000 3162277660168379 9999999999999997900254631487641 3162277660168379 9999999999999997900254631487641 3162277660168379 9999999999999997900254631487641 => nil 2.4.0 :106 > n = 10**32; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 100000000000000000000000000000000 10000000000000000 100000000000000000000000000000000 10000000000000000 100000000000000000000000000000000 10000000000000000 100000000000000000000000000000000 => nil 2.4.0 :107 > n = 10**33; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 1000000000000000000000000000000000 31622776601683793 999999999999999979762122758866849 31622776601683793 999999999999999979762122758866849 31622776601683792 999999999999999916516569555499264 => nil 2.4.0 :108 > n = 10**34; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 10000000000000000000000000000000000 100000000000000000 10000000000000000000000000000000000 100000000000000000 10000000000000000000000000000000000 100000000000000000 10000000000000000000000000000000000 => nil 2.4.0 :109 > n = 10**35; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 100000000000000000000000000000000000 316227766016837933 99999999999999999873578871987712489 316227766016837933 99999999999999999873578871987712489 316227766016837952 100000000000000011890233980627554304 => nil 2.4.0 :110 > n = 10**36; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 1000000000000000000000000000000000000 1000000000000000000 1000000000000000000000000000000000000 1000000000000000000 1000000000000000000000000000000000000 1000000000000000000 1000000000000000000000000000000000000 => nil 2.4.0 :111 > n = 10**37; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 10000000000000000000000000000000000000 3162277660168379331 9999999999999999993682442519108007561 3162277660168379331 9999999999999999993682442519108007561 3162277660168379392 10000000000000000379480317059650289664 => nil 2.4.0 :112 > ``` -- https://bugs.ruby-lang.org/ Unsubscribe: