ruby-core

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: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>