From: jzakiya@... Date: 2017-02-22T21:05:42+00:00 Subject: [ruby-core:79699] [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 Jabari Zakiya. Hey that's great! I'd love to help work on this too, though I'm not much of a C programmer. I can help with testing though. Below are test results comparing the **bbm** algorithm used in **iroot2** and **irootn** versus the general Newton's method. As you can see, for the range of values used, Newton becomes much slower as the numbers gets bigger. First **bbm**, for squareroot, is order O(log2(n)/2)), which I think beats Newton. But also compared to Newton, all those additions and divisions done in the inner loop become more expensive (cpu intensive) as the numbers get bigger (taking care of carries, etc), whereas the **bbm** merely does inplace bit operations. You obviously can make Newton's mechanically better, but I suspect it will never be faster on a real computer than **bbm** because of its cpu work cost to implement. In fact my I7 cpu laptop's fan started to kick in running these benchmarks, which I let cool down between runs. Both methods did create the same correct results. Test suite: ``` class Integer def irootn(n) return nil if self < 0 && n.even? raise "root n is < 2 or not an Integer" unless n.is_a?(Integer) && n > 1 num = self.abs bits_shift = (num.bit_length)/n + 2 root, bitn_mask = 0, (1 << bits_shift) until (bitn_mask >>= 1) == 0 root |= bitn_mask root ^= bitn_mask if root**n > num end root *= (self < 0 ? -1 : 1) end def iroot2; irootn(2) end end def intsqrt7(n) # Newton's method x = n y = (n + 1)/2 while y < x x = y y = (x + n/x)/2 end x end require "benchmark/ips" Benchmark.ips do |x| exp = 4000; n = 10**exp puts "integer squareroot tests for n = 10**#{exp}" x.report("iroot2" ) { n.iroot2 } x.report("irootn(2)" ) { n.irootn(2) } x.report("newtons" ) { intsqrt7(n) } x.compare! end ``` Benchmark results: ``` 2.4.0 :042 > load 'irootstest.rb' integer squareroot tests for n = 10**500 Warming up -------------------------------------- iroot2 70.000 i/100ms irootn(2) 69.000 i/100ms newtons 43.000 i/100ms Calculating ------------------------------------- iroot2 636.901 (��14.9%) i/s - 3.150k in 5.089664s irootn(2) 676.828 (�� 5.6%) i/s - 3.381k in 5.012279s newtons 427.424 (�� 4.4%) i/s - 2.150k in 5.040686s Comparison: irootn(2): 676.8 i/s iroot2: 636.9 i/s - same-ish: difference falls within error newtons: 427.4 i/s - 1.58x slower => true 2.4.0 :043 > load 'irootstest.rb' integer squareroot tests for n = 10**1000 Warming up -------------------------------------- iroot2 22.000 i/100ms irootn(2) 22.000 i/100ms newtons 14.000 i/100ms Calculating ------------------------------------- iroot2 228.501 (�� 3.9%) i/s - 1.144k in 5.014841s irootn(2) 227.442 (�� 4.8%) i/s - 1.144k in 5.042017s newtons 139.466 (�� 3.6%) i/s - 700.000 in 5.027213s Comparison: iroot2: 228.5 i/s irootn(2): 227.4 i/s - same-ish: difference falls within error newtons: 139.5 i/s - 1.64x slower => true 2.4.0 :044 > load 'irootstest.rb' integer squareroot tests for n = 10**2000 Warming up -------------------------------------- iroot2 6.000 i/100ms irootn(2) 6.000 i/100ms newtons 3.000 i/100ms Calculating ------------------------------------- iroot2 67.819 (�� 2.9%) i/s - 342.000 in 5.049151s irootn(2) 68.311 (�� 2.9%) i/s - 342.000 in 5.013356s newtons 38.863 (�� 2.6%) i/s - 195.000 in 5.024956s Comparison: irootn(2): 68.3 i/s iroot2: 67.8 i/s - same-ish: difference falls within error newtons: 38.9 i/s - 1.76x slower => true 2.4.0 :045 > load 'irootstest.rb' integer squareroot tests for n = 10**4000 Warming up -------------------------------------- iroot2 1.000 i/100ms irootn(2) 1.000 i/100ms newtons 1.000 i/100ms Calculating ------------------------------------- iroot2 17.380 (�� 5.8%) i/s - 87.000 in 5.011300s irootn(2) 17.417 (�� 5.7%) i/s - 87.000 in 5.000415s newtons 9.512 (�� 0.0%) i/s - 48.000 in 5.050706s Comparison: irootn(2): 17.4 i/s iroot2: 17.4 i/s - same-ish: difference falls within error newtons: 9.5 i/s - 1.83x slower => true 2.4.0 :046 > ``` ---------------------------------------- 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-63120 * Author: Jabari Zakiya * Status: Open * 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: