From: jzakiya@... Date: 2017-02-23T05:31:38+00:00 Subject: [ruby-core:79714] [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. I did a simplifications in **isqrt1**, replacing all the '+'s with '|' operatioins, leaving only the math subtraction operation ``n -= t ``. I'll see if I can get rid of that. This makes it a bit faster, especially for numbers ``< 10**400``, where it starts being faster than **iroot2**. This suggests, for optimal overall speed, that a hybrid method can be crafted, like I proposed for using **Math.sqrt(n).to_i**, like: ``def sqrt_i(n); n < UPPER_BOUND ? n.iroot2 : isqrt1(n) end`` ``` 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 isqrt(n) r = 0 x = 1 << ((n.bit_length >> 1 ) << 1) while x != 0 do t = r + x if n >= t n -= t r = (r >> 1) + x else r >>= 1 end x >>= 2 end r end def isqrt1(n) r = 0 x = 1 << ((n.bit_length >> 1 ) << 1) until x == 0 t = r | x r >>= 1 (n -= t; r |= x) if n >= t x >>= 2 end r end Benchmark.ips do |x| exp = 400; 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("isqrt(n)" ) { isqrt(n) } x.report("isqrt1(n)" ) { isqrt1(n) } x.compare! end ``` ``` 2.4.0 :118 > load 'irootstest.rb' integer squareroot tests for n = 10**50 Warming up -------------------------------------- iroot2 4.157k i/100ms isqrt(n) 3.590k i/100ms isqrt1(n) 4.029k i/100ms Calculating ------------------------------------- iroot2 41.870k (�� 3.7%) i/s - 212.007k in 5.070841s isqrt(n) 36.039k (�� 3.6%) i/s - 183.090k in 5.087128s isqrt1(n) 40.580k (�� 3.4%) i/s - 205.479k in 5.069789s Comparison: iroot2: 41870.0 i/s isqrt1(n): 40579.8 i/s - same-ish: difference falls within error isqrt(n): 36039.1 i/s - 1.16x slower => true 2.4.0 :119 > load 'irootstest.rb' integer squareroot tests for n = 10**100 Warming up -------------------------------------- iroot2 1.385k i/100ms isqrt(n) 879.000 i/100ms isqrt1(n) 883.000 i/100ms Calculating ------------------------------------- iroot2 14.004k (�� 3.2%) i/s - 70.635k in 5.049521s isqrt(n) 8.558k (�� 3.9%) i/s - 43.071k in 5.040986s isqrt1(n) 9.173k (�� 3.8%) i/s - 45.916k in 5.012857s Comparison: iroot2: 14003.5 i/s isqrt1(n): 9173.2 i/s - 1.53x slower isqrt(n): 8557.9 i/s - 1.64x slower => true 2.4.0 :120 > load 'irootstest.rb' integer squareroot tests for n = 10**200 Warming up -------------------------------------- iroot2 425.000 i/100ms isqrt(n) 377.000 i/100ms isqrt1(n) 393.000 i/100ms Calculating ------------------------------------- iroot2 4.248k (�� 4.1%) i/s - 21.250k in 5.010948s isqrt(n) 3.722k (�� 4.5%) i/s - 18.850k in 5.075627s isqrt1(n) 3.876k (�� 4.9%) i/s - 19.650k in 5.081749s Comparison: iroot2: 4248.2 i/s isqrt1(n): 3876.3 i/s - 1.10x slower isqrt(n): 3721.7 i/s - 1.14x slower => true 2.4.0 :121 > load 'irootstest.rb' integer squareroot tests for n = 10**300 Warming up -------------------------------------- iroot2 252.000 i/100ms isqrt(n) 219.000 i/100ms isqrt1(n) 238.000 i/100ms Calculating ------------------------------------- iroot2 2.477k (�� 6.5%) i/s - 12.348k in 5.008024s isqrt(n) 2.263k (�� 6.6%) i/s - 11.388k in 5.060793s isqrt1(n) 2.407k (�� 4.0%) i/s - 12.138k in 5.050951s Comparison: iroot2: 2476.8 i/s isqrt1(n): 2407.2 i/s - same-ish: difference falls within error isqrt(n): 2262.7 i/s - same-ish: difference falls within error => true 2.4.0 :122 > load 'irootstest.rb' integer squareroot tests for n = 10**400 Warming up -------------------------------------- iroot2 101.000 i/100ms isqrt(n) 156.000 i/100ms isqrt1(n) 165.000 i/100ms Calculating ------------------------------------- iroot2 972.069 (�� 6.0%) i/s - 4.848k in 5.006825s isqrt(n) 1.495k (�� 7.3%) i/s - 7.488k in 5.038471s isqrt1(n) 1.611k (�� 7.0%) i/s - 8.085k in 5.045823s Comparison: isqrt1(n): 1610.8 i/s isqrt(n): 1494.9 i/s - same-ish: difference falls within error iroot2: 972.1 i/s - 1.66x slower ``` ---------------------------------------- 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-63136 * 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: