ruby-core

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