[ruby-core:80271] [Ruby trunk Feature#13263] Add companion integer nth-root method to recent Integer#isqrt

Issue #13263 has been updated by jzakiya (Jabari Zakiya).


FYI for general interest and curiosity.

In Ruby 2.4.0 the 3 implementations below of Newton's general nth-root method all produce
correct results, using an initial root value that's 1-bit larger than the actual value.

Using **benchmark-ips** they are all basically equivalent in speed, with **Newton3**
being a smidgen faster across a range of number/root sizes. It is interesting to see
how they differ in speed (minimally) based on the particular number and/or root value.

It is also interesting to see that when implemented and run with Crystal (current 0.21.1),
while Crystal is faster (as expected), it is not multiple orders faster, and the performance
profile is similar between the different implementations. (Replace ``1 << ...`` with ``1.to_big_i << ...``)

Thus, Ruby's use of glibc, gmp, et al, libraries appears to be very, very good for doing this math,
(at least to the accuracies of these libraries). It would still be intersting to see how much faster
an optimized version of **bbm** would be (as I've proposed, or better), compared to Newton, especially 
since the stock implementation is still faster than any of the Newton implementations for some number/root sizes.

```
def irootn(n)   # Newton's method for nth root
  return nil if self < 0 && n.even?
  raise "root n not an Integer >= 2" unless n.is_a?(Integer) && n > 1
  return self if (self | 1) == 1 || (self == -1 && n.odd?)
  num = self.abs

                     Newton1                                               Newton2                                     Newton3
  e, u, x = n-1, (x = 1 << (num.bit_length-1)/n + 1), x+1    e, x = n-1, 1 << (num.bit_length-1)/n + 1    e, x = n-1, 1 << (num.bit_length-1)/n + 1
  while u < x                                                while (t = (e * x + num / x ** e))/n < x     while (t = (e * x + num / x ** e)/n) < x
    x = u                                                       x = t/n                                      x = t
    t = e * x + num / x ** e                                 end                                          end
    u = t / n               
  end                                                        

  x *= self < 0 ? -1 : 1
end
```

----------------------------------------
Feature #13263: Add companion integer nth-root method to recent Integer#isqrt
https://bugs.ruby-lang.org/issues/13263#change-63707

* Author: jzakiya (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:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>