Issue #13219 has been updated by Jabari Zakiya.
So the clear winner, and new champeen is...**newtons_fast**, at least for squareroots.
Just goes to show, don't f**k with Newton!
```
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 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
def newtons_fast(n) # Newton's method with ¢ån < initial_x <= 2*¢ån
raise if n<0
return n if n<=1
x = 1<<((n.bit_length+1)/2)
y = (x + n/x)/2
while y < x
x = y
y = (x + n/x)/2
end
x
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("isqrt1(n)" ) { isqrt1(n) }
x.report("newtons_fast(n)") { newtons_fast(n)
x.compare!
end
```
```
2.4.0 :138 > load 'irootstest.rb'
integer squareroot tests for n = 10**5
Warming up --------------------------------------
iroot2 85.000k i/100ms
isqrt1(n) 87.646k i/100ms
newtons_fast(n) 191.796k i/100ms
Calculating -------------------------------------
iroot2 1.014M (¡Þ 2.9%) i/s - 5.100M in 5.031392s
isqrt1(n) 1.049M (¡Þ 3.0%) i/s - 5.259M in 5.018645s
newtons_fast(n) 2.846M (¡Þ 4.6%) i/s - 14.385M in 5.066760s
Comparison:
newtons_fast(n): 2845709.1 i/s
isqrt1(n): 1048817.1 i/s - 2.71x slower
iroot2: 1014498.5 i/s - 2.81x slower
=> true
2.4.0 :139 > load 'irootstest.rb'
integer squareroot tests for n = 10**50
Warming up --------------------------------------
iroot2 4.077k i/100ms
isqrt1(n) 3.992k i/100ms
newtons_fast(n) 24.377k i/100ms
Calculating -------------------------------------
iroot2 41.189k (¡Þ 6.1%) i/s - 207.927k in 5.071463s
isqrt1(n) 40.293k (¡Þ 3.4%) i/s - 203.592k in 5.058807s
newtons_fast(n) 260.960k (¡Þ 3.4%) i/s - 1.316M in 5.050191s
Comparison:
newtons_fast(n): 260959.7 i/s
iroot2: 41188.8 i/s - 6.34x slower
isqrt1(n): 40292.7 i/s - 6.48x slower
=> true
2.4.0 :140 > load 'irootstest.rb'
integer squareroot tests for n = 10**500
Warming up --------------------------------------
iroot2 74.000 i/100ms
isqrt1(n) 127.000 i/100ms
newtons_fast(n) 3.775k i/100ms
Calculating -------------------------------------
iroot2 741.359 (¡Þ 4.6%) i/s - 3.700k in 5.001895s
isqrt1(n) 1.258k (¡Þ 7.0%) i/s - 6.350k in 5.077988s
newtons_fast(n) 37.762k (¡Þ 4.5%) i/s - 188.750k in 5.008756s
Comparison:
newtons_fast(n): 37761.5 i/s
isqrt1(n): 1257.6 i/s - 30.03x slower
iroot2: 741.4 i/s - 50.94x slower
=> true
2.4.0 :141 > load 'irootstest.rb'
integer squareroot tests for n = 10**5000
Warming up --------------------------------------
iroot2 1.000 i/100ms
isqrt1(n) 5.000 i/100ms
newtons_fast(n) 340.000 i/100ms
Calculating -------------------------------------
iroot2 11.196 (¡Þ 8.9%) i/s - 56.000 in 5.013699s
isqrt1(n) 53.056 (¡Þ 3.8%) i/s - 265.000 in 5.002572s
newtons_fast(n) 3.402k (¡Þ 3.1%) i/s - 17.000k in 5.002400s
Comparison:
newtons_fast(n): 3401.9 i/s
isqrt1(n): 53.1 i/s - 64.12x slower
iroot2: 11.2 i/s - 303.85x 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-63139
* 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>