```Issue #13219 has been updated by Jabari Zakiya.

```
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 if root**n > num
end
root *= (self < 0 ? -1 : 1)
end

def iroot2; irootn(2) end
end

require "bigdecimal"
require "benchmark/ips"

Benchmark.ips do |x|
n = 10**35
puts "integer squareroot tests for n = #{n}"
x.report("iroot2"       ) { n.iroot2    }
x.report("irootn(2)"    ) { n.irootn(2) }
x.report("BigDecimal(n).sqrt(5 ).to_i") { BigDecimal(n).sqrt(5 ).to_i }
x.report("BigDecimal(n).sqrt(10).to_i") { BigDecimal(n).sqrt(10).to_i }
x.report("BigDecimal(n).sqrt(20).to_i") { BigDecimal(n).sqrt(20).to_i }
x.compare!
end
```
Yes, its much slower, even to the highlevel Ruby versions.

```
integer squareroot tests for n = 100000000000000000000000000000000000
Warming up --------------------------------------
iroot2     5.681k i/100ms
irootn(2)     5.714k i/100ms
BigDecimal(n).sqrt(5 ).to_i
3.021k i/100ms
BigDecimal(n).sqrt(10).to_i
2.953k i/100ms
BigDecimal(n).sqrt(20).to_i
2.616k i/100ms
Calculating -------------------------------------
iroot2     57.825k (¡Þ 3.3%) i/s -    289.731k in   5.016021s
irootn(2)     57.462k (¡Þ 3.7%) i/s -    291.414k in   5.078940s
BigDecimal(n).sqrt(5 ).to_i
30.543k (¡Þ 2.8%) i/s -    154.071k in   5.048265s
BigDecimal(n).sqrt(10).to_i
30.709k (¡Þ 3.1%) i/s -    153.556k in   5.005239s
BigDecimal(n).sqrt(20).to_i
26.725k (¡Þ 3.0%) i/s -    136.032k in   5.094723s

Comparison:
iroot2:    57825.2 i/s
irootn(2):    57461.9 i/s - same-ish: difference falls within error
BigDecimal(n).sqrt(10).to_i:    30708.9 i/s - 1.88x  slower
BigDecimal(n).sqrt(5 ).to_i:    30543.4 i/s - 1.89x  slower
BigDecimal(n).sqrt(20).to_i:    26725.0 i/s - 2.16x  slower

=> true
2.4.0 :202
```
And you need to know beforehand the needed correct precision to display the correct results.

```
2.4.0 :214 > n = 10**35; puts n, n.iroot2, BigDecimal(n).sqrt(5).to_i, BigDecimal(n).sqrt(10).to_i,BigDecimal(n).sqrt(20).to_i
100000000000000000000000000000000000
316227766016837933
316227766016837933
316227766016837933
316227766016837933
=> nil
2.4.0 :215 > n = 10**45; puts n, n.iroot2, BigDecimal(n).sqrt(5).to_i, BigDecimal(n).sqrt(10).to_i,BigDecimal(n).sqrt(20).to_i
1000000000000000000000000000000000000000000000
31622776601683793319988
31622776601683666666666
31622776601683666666666
31622776601683793319988
=> nil
2.4.0 :216 > n = 10**55; puts n, n.iroot2, BigDecimal(n).sqrt(5).to_i, BigDecimal(n).sqrt(10).to_i,BigDecimal(n).sqrt(20).to_i
10000000000000000000000000000000000000000000000000000000
3162277660168379331998893544
3162277660168379331499021527
3162277660168379331499021527
3162277660168379331998893544
=> nil
2.4.0 :217 > n = 10**65; puts n, n.iroot2, BigDecimal(n).sqrt(5).to_i, BigDecimal(n).sqrt(10).to_i,BigDecimal(n).sqrt(20).to_i
100000000000000000000000000000000000000000000000000000000000000000
316227766016837933199889354443271
316227766016837466536394723986322
316227766016837466536394723986322
316227766016837933199889000000000
=> nil
2.4.0 :218 >
```

----------------------------------------
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-63041

* 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
return root if bitn_mask == 0
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
return root if bitn_mask == 0
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.

```
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>
```