Issue #13263 has been updated by Jabari Zakiya.
Further testing shows Newton's method is sensitive to its implementation as you take larger roots.
Shown below are test results that show the **irootn1** Newton's implementation starts to give incorrect (smaller)
results past a certain size root value, but the **irootn2** Newton's implementation gives correct results (**bbm**
will always produce correct results). In the benchmarks, **irootn1** may sometimes be shown to be faster because
of it producing, faster, smaller wrong results.
Because of this, **bbm** seems to be generally faster versus Newton's method, especially as the roots get
bigger, because the operations to perform Newton's are cpu costly, requiring a multiplication, exponentiation,
addition, and two divisions, at least once per round, for arbitrary sized integers.
On the other hand, **bbm** only requires 2|3 cheap cpu bit operations and one exponentiation per round.
So while on paper Newton's may seem it should be faster, its cpu implementation cost is much greater, and
empirical evidence establishes **bbm** is generally faster than these implementations of Newton's.
But the most important point for me is, **as a user I always want correct results first and foremost.**
The only way to empirically (versus theoretically) establish which is faster is to do an optimized C version
of **bbm** too, and do an apples-to-apples comparison against a Newton's version. But it is already clear
which is simpler to code, with no worries it will produce incorrect answers. Also **bbm** takes much less
electrical power to perform, because of its relatively smaller cpu operational costs.
I would that encourage that empirical results from accuracy testing, and benchmarking, should establish what
is --better--, giving consideration to all relevant factors (not just speed).
Test results below.
```
2.4.0 :567 > exp = 800; n = 10**exp; r = 74; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }" #,
64686076615
64686076615
64686076615
0.000136971
0.000171888
0.000681239
=> nil
2.4.0 :568 > exp = 800; n = 10**exp; r = 75; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
46415888336
34359738368
46415888336
0.000177774
3.7298e-05
0.000527569
=> nil
2.4.0 :569 > exp = 800; n = 10**exp; r = 100; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
100000000
67108864
100000000
0.000102902
1.6642e-05
0.000430577
=> nil
2.4.0 :570 > exp = 800; n = 10**exp; r = 200; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
10000
8192
10000
5.4696e-05
2.6753e-05
0.000941954
=> nil
2.4.0 :571 > exp = 800; n = 10**exp; r = 300; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
464
256
464
6.1939e-05
1.6915e-05
0.000279832
=> nil
2.4.0 :572 > exp = 800; n = 10**exp; r = 400; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
100
64
100
4.6034e-05
3.8532e-05
0.000322497
=> nil
2.4.0 :573 > exp = 800; n = 10**exp; r = 500; puts ' ', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }" #
39
32
39
4.1114e-05
6.3514e-05
0.000486907
=> nil
2.4.0 :574 >
```
----------------------------------------
Feature #13263: Add companion integer nth-root method to recent Integer#isqrt
https://bugs.ruby-lang.org/issues/13263#change-63279
* Author: Jabari Zakiya
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
----------------------------------------
Following the heels of adding the method ``Integer#isqrt``, to create exact integer
squareroot values for arbitrary sized integers, based on the following threads:
https://bugs.ruby-lang.org/issues/13219
https://bugs.ruby-lang.org/issues/13250
I also request adding its companion method to compute any integer nth-root too.
Below are sample methods of high level Ruby code that compute exact results.
https://en.wikipedia.org/wiki/Nth_root_algorithm
The Newton's code is a Python version I tweaked to make it look like ``Integer#isqrt``'s form.
Benchmarks show the **bbm** method is generally faster, especially as the roots become larger,
than using Newton's method, with an added benefits its simpler to code/understand, and has a lower
sensitivity to the initial root value, and handling of small numbers.
```
class Integer
def irootn(n) # binary bit method (bbm) for nth root
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 - 1)/n + 1 # add 1 for initial loop >>= 1
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 irootn1(n) # Newton's method for nth root
return nil if self < 0 && n.even?
raise "root n is < 2 or not an Integer" unless n.is_a?(Integer) && n > 1
return self if self == 0 || (self == -1 && n.odd?)
num = self.abs
b = num.bit_length
e, u, x = n-1, (x = 1 << (b-1)/(n-1)), x+1
while u < x
x = u
t = e * x + num / x ** e
u = t / n
end
x *= self < 0 ? -1 : 1
end
def irootn2(n) # Newton's restructured coded method for nth root
return nil if self < 0 && n.even?
raise "root n is < 2 or not an Integer" unless n.is_a?(Integer) && n > 1
return self if self == 0 || (self == -1 && n.odd?)
num = self.abs
b = num.bit_length
e, x = n-1, 1 << (b-1)/(n-1) + 1
while t = (e * x + num / x ** e)/n < x
x = (e * x + num / x ** e)/n
end
x *= self < 0 ? -1 : 1
end
end
require "benchmark/ips"
[50, 500, 1000, 2000, 4000, 5000].each do |exp|
[3, 4, 7, 13, 25, 33]. each do |k|
Benchmark.ips do |x|
n = 10**exp
puts "integer root tests for root #{k} of n = 10**#{exp}"
x.report("bbm" ) { n.irootn(k) }
x.report("newton1" ) { n.irootn1(k) }
x.report("newton2" ) { n.irootn2(k) }
x.compare!
end
end
end
```
Here are results.
```
def tm; t=Time.now; yield; Time.now-t end
2.4.0 :022 > exp = 111; n = 10**exp; r = 10; puts n, "#{ tm{ puts n.irootn(r)} }", "#{ tm{ puts n.irootn1(r)} }", "#{ tm{ puts n.irootn2(r)} }"
125892541179
125892541179
125892541179
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
4.6673e-05
6.5506e-05
0.000121357
=> nil
2.4.0 :023 > exp = 150; n = 10**exp; r = 50; puts n, "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn1(r)}}", "#{ tm{ puts n.irootn2(r)} }"
1000
1000
1000
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
2.28e-05
1.8762e-05
0.000128852
=> nil
2.4.0 :024 >
```
The benchmarks show that ``irootn2`` is the slowest but it has the same
form as ``Integer#isqt`` in the numeric.c and bignum.c files in trunk.
It probably can be tweaked to make it faster.
bignum.c, starting at line 6772
https://bugs.ruby-lang.org/projects/ruby-trunk/repository/revisions/57705/entry/bignum.c
numeric.c, starting at line 5131
https://bugs.ruby-lang.org/projects/ruby-trunk/repository/revisions/57705/entry/numeric.c
Thus, a hybrid method could be created that swtiches between the two.
```
def isqrt(num=self)
b = num.bit_length
x = 1 << (b-1)/2 | num >> (b/2 + 1) # optimum first root extimate
while (t = num / x) < x
x = ((x + t) >> 1)
end
x
end
def irootn2(n)
b = num.bit_length
e, x = n-1, 1 << (b-1)/(n-1) + 1 # optimum first root estimate(?)
while t = (e * x + num / x ** e)/n < x
x = (e * x + num / x ** e)/n
end
x
end
def irtn(n) # possible hybrid combination for all nth-roots
b = num.bit_length
if 2 < n # for squareroot
x = 1 << (b-1)/2 | num >> (b/2 + 1)
while (t = num / x) < x
x = ((x + t) >> 1)
end
else # for roots > 2
e, x = n-1, 1 << (b-1)/(n-1) + 1
while t = (e * x + num / x ** e)/n < x
x = (e * x + num / x ** e)/n
end
end
x *= if self < 0 ? -1 : 1
end
```
So with just a little more work, a highly performant nth-root method can be added
to the std lib, as with ``Integer#isqrt``, to take care of all the exact integer roots
for arbitrary sized integers, by whatever name that is preferable.
This will enhance Ruby's use even more in fields like number theory, advanced math, cryptography,
etc, to have fast primitive standard methods to compute these use case values.
--
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>