Issue #13263 has been updated by Jabari Zakiya. An optimization for the initiall ``root**n`` can be as follows: Given any number **num** with only one bit set, and thus: ``bits = num.bit_length`` then it's exponentiation to any **n** is just: ``num**n => num << (num.bit_length - 1)*(n-1)`` ``` > num = 0x80000000 => 2147483648 > n = 1; (num**n).to_s(2) => "10000000000000000000000000000000" > n = 1; (num << (num.bit_length - 1)*(n-1)).to_s(2) => "10000000000000000000000000000000" > n = 2; (num**n).to_s(2) => "100000000000000000000000000000000000000000000000000000000000000" > n = 2; (num << (num.bit_length - 1)*(n-1)).to_s(2) => "100000000000000000000000000000000000000000000000000000000000000" > n = 3; (num**n).to_s(2) => "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" > n = 3; (num << (num.bit_length - 1)*(n-1)).to_s(2) => "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" ``` So in the C optimized **bbm** implementation the initial root**n exponentiation can be replaced with this simple machine level bit manipulation. ``` root = bit_mask = 1 << (num.bit_length - 1)/n numb = (root << (root.bit_length - 1)*(n-1) # fast cpu level root**n until ((bit_mask >>= 1) == 0) || numb == num root |= bit_mask root ^= bit_mask if (numb = root**n) > num end ``` It's interesting that if you just compare the benchmarks between using the ``**`` operator and this method in hight level Ruby the ``**`` operator is faster, but that's because in highlevel Ruby all the separate methods calls incur their individual overhead, while the ``**`` operator incurs only one, and has a highly performant C implementation. (But if you compare the differnces of the **irootn** method using the different techniques, they perform the same using benchmark/ips, which is sort of expected since this initial operation occurs only once.) Unless the C implementation of the ``**`` operator already optimizes for this case, I have to think a well done cpu level C implementation of: `` num << (num.bit_length - 1)*(n-1)`` has to be faster, because all you're doing is setting one bit in some word Wi of a number. ``` require "benchmark/ips" (2..10).each do |exp| [3, 4, 7, 13].each do |k| Benchmark.ips do |x| n = 2**exp; b = n.bit_length puts "integer exponentiation tests for power #{k} for n = 2**#{exp}" x.report("n**k" ) { n**k } x.report("n**k bits" ) { n << (b-1)*(n-1) } x.report("n**k bits1") { n << (n.bit_length-1)*(n-1) } x.compare! end end end ``` ---------------------------------------- Feature #13263: Add companion integer nth-root method to recent Integer#isqrt https://bugs.ruby-lang.org/issues/13263#change-63355 * 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>