https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112017-02-28T22:38:33ZRuby Issue Tracking SystemRuby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=632642017-02-28T22:38:33ZStudent (Nathan Zook)blogger@pierian-spring.net
<ul></ul><p>Newton's method has quadratic convergence. This means that a properly implemented Newton's method will blow away any BBM if more than just a few bits are needed.</p>
<p>"Properly implemented" is a big deal, because, as I have found with some research (see in particular <a href="http://www.agner.org/optimize/instruction_tables.pdf" class="external">http://www.agner.org/optimize/instruction_tables.pdf</a>), recent Intel cpus can require >30x a long to do an integer divide as a multiply. I've not dug into our multi-precision library to see how Ruby implements things, but it can matter a very great deal. From the standpoint of Ruby implementations, the overhead of Ruby calls is a huge burden on these methods, and likely dominates much of your benchmarks. In the case of square roots, this was relatively easy to overcome, but for higher-order roots, this becomes more and more of a problem.</p>
<p>A general n-th root extractor makes sense, but I believe that it is worthwhile to do a bit of digging into these techniques before deciding on an approach.</p> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=632672017-03-01T02:46:04Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>Jabari Zakiya wrote:</p>
<blockquote>
<p>This will enhance Ruby's use even more in fields like number theory, advanced math, cryptography,<br>
etc, to have fast primitive standard methods to compute these use case values.</p>
</blockquote>
<p>I'm not immediately against this but can I ask you when is this method useful? Because being amateur, I don't know any real application of integer n-th root in cryptography etc.</p> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=632792017-03-01T21:08:17Zjzakiya (Jabari Zakiya)
<ul></ul><p>Further testing shows Newton's method is sensitive to its implementation as you take larger roots.</p>
<p>Shown below are test results that show the <strong>irootn1</strong> Newton's implementation starts to give incorrect (smaller)<br>
results past a certain size root value, but the <strong>irootn2</strong> Newton's implementation gives correct results (<strong>bbm</strong><br>
will always produce correct results). In the benchmarks, <strong>irootn1</strong> may sometimes be shown to be faster because<br>
of it producing, faster, smaller wrong results.</p>
<p>Because of this, <strong>bbm</strong> seems to be generally faster versus Newton's method, especially as the roots get<br>
bigger, because the operations to perform Newton's are cpu costly, requiring a multiplication, exponentiation,<br>
addition, and two divisions, at least once per round, for arbitrary sized integers.</p>
<p>On the other hand, <strong>bbm</strong> only requires 2|3 cheap cpu bit operations and one exponentiation per round.</p>
<p>So while on paper Newton's may seem it should be faster, its cpu implementation cost is much greater, and<br>
empirical evidence establishes <strong>bbm</strong> is generally faster than these implementations of Newton's.</p>
<p>But the most important point for me is, <strong>as a user I always want correct results first and foremost.</strong></p>
<p>The only way to empirically (versus theoretically) establish which is faster is to do an optimized C version<br>
of <strong>bbm</strong> too, and do an apples-to-apples comparison against a Newton's version. But it is already clear<br>
which is simpler to code, with no worries it will produce incorrect answers. Also <strong>bbm</strong> takes much less<br>
electrical power to perform, because of its relatively smaller cpu operational costs.</p>
<p>I would that encourage that empirical results from accuracy testing, and benchmarking, should establish what<br>
is --better--, giving consideration to all relevant factors (not just speed).</p>
<p>Test results below.</p>
<pre><code>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 >
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=632822017-03-01T22:54:30Zjzakiya (Jabari Zakiya)
<ul></ul><p>Actually, this <strong>bbm</strong> version is generally a smidgen faster than the original, especially for perfect roots.</p>
<pre><code>class Integer
def irootn3(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
root = b_mask = 1 << (num.bit_length-1)/n
numb = root**n
until ((b_mask >>= 1) == 0) || numb == num
root |= b_mask
root ^= b_mask if (numb = root**n) > num
end
root *= self < 0 ? -1 : 1
end
end
</code></pre>
<pre><code>2.4.0 :781 > exp = 20000; n = 10**exp; r = 100; puts '', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn3(r)}}"
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0.077781852
0.056256279
=> nil
2.4.0 :782 > exp = 20000; n = 10**exp; r = 105; puts '', "#{tm{ puts n.irootn(r)}}", "#{ tm{ puts n.irootn3(r)}}"
29935772947204898173058573713545176883262845807813845402640946129364486101284568000214134023311247816174990535520060919558577709024260554789568837446173266139382305916243214137145048773203904
29935772947204898173058573713545176883262845807813845402640946129364486101284568000214134023311247816174990535520060919558577709024260554789568837446173266139382305916243214137145048773203904
0.086875851
0.085639275
=> nil
2.4.0 :783 >
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633322017-03-03T22:09:28ZStudent (Nathan Zook)blogger@pierian-spring.net
<ul></ul><p>If you get the wrong answer from Newton's, then you are doing it wrong. It may fail to converge, (which seems MOST unlikely in this case) but that is a different matter. But ultimately, there is 0 credibility to benchmarks that show BBM faster than Newton's past some small values, unless f(x) has a multiple root--which it never will here.</p>
<p>What IS special about this class of problems is that Newton's tends to blow up if your estimate is ever small.It is important to start above and work your way down. That is to say, your condition code is wrong. Doubling your initial estimate would be a substantial improvement in this regard. (It is helpful to actually print out the intermediate results to help understand what is happening.) Also, I do not understand why you do the exact same calculation twice in your Newton's work.</p>
<p>Seriously, though. I was only doing the ruby benchmarks before to get comparative information about O[] performance of NR verses Zimmerman. We cannot rely on them for anything else when we are going to C.</p> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633382017-03-04T18:59:40Zjzakiya (Jabari Zakiya)
<ul></ul><p>It would be really helpful if people produce empirical results of actual coded<br>
examples of techniques, to establish their efficacies.</p>
<p><strong>Math may suggest theoretical possibilities, but engineering determines their feasibility.</strong></p>
<p>I've tried to be objective in assessing alternaitve techniques, creating objective tests, and<br>
presentating empirical test results (accuracy and performance), that anyone can run themselves to verify.</p>
<p>Based on these empirical results, <strong>bbm</strong> is the "best" technique that satisfies a host of criteria I have listed.</p>
<p>The only thing Newton's method possibly has over <strong>bbm</strong> is speed, but only under certain conditions, and if<br>
you select an optimized initial estimate. If the estimate is larger than necessary you get speed degradation.<br>
If the estimate is too small you can get incorrect results. And Newton's speed advantage is only consistently<br>
observed for an optimized version for squareroots, which cannot be applied generally to any nth-root, which<br>
requires another specialized implementation.</p>
<p>Below I present a technique to create one optimized C impementation of <strong>bbm</strong> that will produce accurate results<br>
for any nth-root of any integer. I think if something like this (or possibly better; I leave that to the C<br>
devs gurus) is done, all the different relevant criteria I think should be considered (accuracy, speed, memory<br>
use, power consumption, universal cpu efficiency) will be satisfied.</p>
<p>Here is my proposal on how to optimally implement (in C) the <strong>bbm</strong> technique, to use for all nth-roots.</p>
<pre><code>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
#--------------------------------------------------------
root = bit_mask = 1 << (num.bit_length - 1)/n
numb = root**n
until ((bit_mask >>= 1) == 0) || numb == num
root |= bit_mask
root ^= bit_mask if (numb = root**n) > num
end
#--------------------------------------------------------
root *= self < 0 ? -1 : 1
end
end
</code></pre>
<p>Here is a possible C optimized implementation of the <strong>bbm</strong> that will work for all n-bit sized cpus.</p>
<p>This example assumes a 64-bit cpu for illustration purposes.</p>
<p>Let's use the example below to illustrate the technique.</p>
<p>Let: <code>num = 10**50; num.size => 21</code> bytes to represent.</p>
<p>Therefore <strong>num</strong> is represented in memory as below, where each character is a 4-bit nibble.</p>
<pre><code> W2 W1 W0
num = xxxxxxxx yyyyyyyyyyyyyyyy zzzzzzzzzzzzzzzz
</code></pre>
<p>Now the first value the algorithm computes is the <strong>bit_mask</strong> size,</p>
<p>but the first computation is this: <code>(num.bit_length - 1) => (167 - 1) = 166</code></p>
<p>We then (integer) divide this by the root value <strong>n</strong>.</p>
<p>Lets use the squareroot n = 2, but the algorithm works for any n >= 2.</p>
<p>Now: <code>bit_mask = 1 << (166/2) => bit_mask = 1 << 83</code></p>
<p>In a naive implementation this value would take up 84 bits, or two (2) 64-bit words.</p>
<p>But in an optimized implementation we only need to use one cpu register, and<br>
a word count value/register, to keep track of this value. So here the word<br>
count is 2, and the initial value for the bit_mask is the portion of it that<br>
fits in the upper word. As we shift <strong>bit_mask</strong> right, when it equals "0" we<br>
decrement the word count to "1" and set the msb for <strong>bit_mask</strong> to "1", and continue.<br>
When the <strong>bit_mask</strong> value hits "0" again, and we decrement its word count to "0"<br>
we know we've finished the process (if we make it this far, if it wasn't a perfect root).</p>
<p>This <code>bit_mask = 1 << 83</code> would computationally look like: <code>bit_mask = 0x80000 0x0000000000000000</code></p>
<p>but be initially represented as: <code>bit_mask = 0x80000</code>; <code>bit_mask_word_count = 2</code></p>
<p>So we only have to work with register sized values to work with <strong>bit_mask</strong>.</p>
<p>The <strong>root</strong> value is then also set to the initial <strong>bit_mask</strong> value, but be represented as:</p>
<pre><code> root = 0x80000 0x0000000000000000; root_word_count = 2
</code></pre>
<p>The next computation is: <code>numb = root**n</code></p>
<p>Now we know <strong>numb</strong> has the same bit size as <strong>num</strong> but we can do an optimized <code>root**n</code><br>
computation because we know here only the msb is set, so we can just do the <code>root**n</code><br>
computation on the MSword of root, and store that as <strong>numb</strong> with the bit length of <strong>num</strong>.<br>
This, again, eliminates doing an initial <strong>n-eponentiation</strong> on any arbitrary sized integer.</p>
<p>Now we start the loop: <code>until (bit_mask >> 1) || numb == numb</code></p>
<p>Here again, we only shift the value representing the current word position for <strong>bit_mask</strong><br>
stored in a cpu register, which is a fast/cheap inplace cpu operation for any sized cpu.</p>
<p>We can also do the <code>numb == num</code> comparison on a word-by-word basis, in a cpu register.</p>
<p>Now we do the operations: <code>root |= bit_mask</code> and <code>root ^= bit_mask</code></p>
<p>Again, we only operate on the current <strong>root</strong> and <strong>bit_mask</strong> words Wi that are in a cpu register<br>
until we need to operate on the next lower word.</p>
<p>As we do the operation: <code>if (numb = root**n) > num</code></p>
<p>the <strong>root</strong> exponentiation only needs to be performed on the non-zero Wi for <strong>root</strong>, as the<br>
lower "0" valued Wi will contribute nothing to the computation's value.</p>
<p>Thus, we've reduced the algorithm to a series of very fast, and computationally inexpensive, primitive<br>
cpu operations, that can easily be performed on any cpu of any size. We need no adds, multiplies, and divisions,<br>
which are much more cpu intensive/expensive, that are necessary to perform Newton's method.</p>
<p>So with one standard C optimized implemenation we will always get correct results for any/all integer roots,<br>
that will work optimally on any cpu, which uses the least amount of electrical power to perform (a key consideration<br>
for power sensitive platforms like phones, tablets, embedded systems, robots, and IoT things).</p>
<p>I am also 99.99% sure that this type of <strong>bbm</strong> optimized implementation will be faster than any other<br>
theoretically possible technique, as a general technique to always accurately produce the nth-root of an integer.</p>
<p>This can be empirically verified by creating this implemetation and doing an apples-to-apples comparison to other<br>
techniques, and assess them to the list of criteria I suggested, as well as other relevant criteria, for comparison.</p> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633552017-03-05T20:17:46Zjzakiya (Jabari Zakiya)
<ul></ul><p>An optimization for the initiall <code>root**n</code> can be as follows:</p>
<p>Given any number <strong>num</strong> with only one bit set, and thus: <code>bits = num.bit_length</code></p>
<p>then it's exponentiation to any <strong>n</strong> is just: <code>num**n => num << (num.bit_length - 1)*(n-1)</code></p>
<pre><code>> 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"
</code></pre>
<p>So in the C optimized <strong>bbm</strong> implementation the initial root**n exponentiation can be replaced with<br>
this simple machine level bit manipulation.</p>
<pre><code> 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
</code></pre>
<p>It's interesting that if you just compare the benchmarks between using the <code>**</code> operator and this method in<br>
hight level Ruby the <code>**</code> operator is faster, but that's because in highlevel Ruby all the<br>
separate methods calls incur their individual overhead, while the <code>**</code> operator incurs only one,<br>
and has a highly performant C implementation. (But if you compare the differnces of the <strong>irootn</strong> method<br>
using the different techniques, they perform the same using benchmark/ips, which is sort of expected since<br>
this initial operation occurs only once.)</p>
<p>Unless the C implementation of the <code>**</code> operator already optimizes for this case, I have to think a</p>
<p>well done cpu level C implementation of: <code> num << (num.bit_length - 1)*(n-1)</code></p>
<p>has to be faster, because all you're doing is setting one bit in some word Wi of a number.</p>
<pre><code>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
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633572017-03-06T02:58:08Zjzakiya (Jabari Zakiya)
<ul></ul><p>More efficient.</p>
<pre><code> root = bit_mask = (b = 1 << (num.bit_length - 1)/n)
numb = root << b*(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
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633642017-03-06T19:44:00Zjzakiya (Jabari Zakiya)
<ul></ul><p>A further simplification can be done for <code>numb = root**n</code></p>
<pre><code> root = bit_mask = 1 << (b = (num.bit_length - 1)/n)
numb = root**n
numb = root << b*(n-1)
numb = (1 << b) << b*(n-1)
numb = 1 << (b + b*(n-1))
numb = 1 << b*(1 + (n-1))
numb = 1 << b*n
</code></pre>
<p>Which means <strong>root</strong> and <strong>numb</strong> can be done in parallel now by the compiler.</p>
<p>Also, because <strong>root</strong> and <strong>bit_mask</strong> are the same size, only one <strong>word_count</strong><br>
variable is needed, to track which word of <strong>root</strong> is being worked on, not one for each.</p>
<p>You also only need on word_count variable for the size of <strong>numb</strong> and <strong>num</strong>.<br>
Then the comparisons <strong>numb == num</strong> and <strong>numb > num</strong> can be done on a word-by-word<br>
basis, starting from each MSword. If the MSword of <strong>numb</strong> is > or < than that for <strong>num</strong><br>
then it's "true" or "false"; if equal continue with next lower Mswords as necessary.</p>
<p>This reduces the implementations to just bit manipulations, with 1|2 bit twiddles and one shift<br>
operation per loop, and one real arithmetic operation, the <code>**</code> exponentiation inside the loop.</p>
<pre><code> root = bit_mask = 1 << (b = (num.bit_length - 1)/n)
numb = 1 << b*n # fast cpu level root**n
until ((bit_mask >>= 1) == 0) || numb == num
root |= bit_mask
root ^= bit_mask if (numb = root**n) > num
end
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=633822017-03-07T16:31:14Zjzakiya (Jabari Zakiya)
<ul></ul><p>These are the correct benchmarks to show the differences in performance doing <code>root**n</code>.<br>
Even in highlevel Ruby, the <code>1 << b*n</code> shows it is faster.</p>
<pre><code>require "benchmark/ips"
(50..60).each do |exp|
[3, 4, 7, 13].each do |n|
Benchmark.ips do |x|
num = 2**exp; root = 1 << (b = (num.bit_length-1)/n)
puts "root**n tests for root #{n} of num = 2**#{exp}"
x.report("root**n" ) { root**n }
x.report("1 << b*n" ) { 1 << b*n }
x.report("root << b*(n-1)") { root << b*(n-1) }
x.compare!
end
end
end
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=635732017-03-13T21:25:54Zjzakiya (Jabari Zakiya)
<ul></ul><p>Just FYI.</p>
<p>I simplified Newton's general nth-root method from the original implementation I posted.<br>
It's faster, and seems to produce the correct results all the time (from the tests I've run).<br>
For some roots (mostly smallish) of certain numbers it's faster than <strong>bbm</strong> by some<br>
percentage difference, but in general <strong>bbm</strong> is still faster, by whole number factors, across the board.</p>
<pre><code>original implementation of Newton's general nth-root method
def irootn2(n)
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 # optimum first root estimate(?)
while t = (e * x + num / x ** e)/n < x
x = (e * x + num / x ** e)/n
end
x
end
simpler/faster implementation of Newton's general nth-root method
def irootn2(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, x = n-1, 1 << (b-1)/(n-1) + 1 # optimum first root estimate(?)
while (t = e * x + num / x ** e)/n < x
x = t/n
end
x *= self < 0 ? -1 : 1
end
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=635822017-03-14T03:42:19Zjzakiya (Jabari Zakiya)
<ul></ul><p>Using a 1-bit greater initial estimate than for <strong>bbm</strong> makes Newton's nth-root implementation<br>
significantly faster across the board than before (with seemingly correct answers).</p>
<pre><code>def irootn2(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, x = n-1, 1 << (b-1)/(n-1) + 1 # optimum first root estimate(?)
e, x = n-1, 1 << (b-1)/n + 1 # much better first root estimate
while (t = e * x + num / x ** e)/n < x
x = t/n
end
x *= self < 0 ? -1 : 1
end
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=637072017-03-21T16:39:01Zjzakiya (Jabari Zakiya)
<ul></ul><p>FYI for general interest and curiosity.</p>
<p>In Ruby 2.4.0 the 3 implementations below of Newton's general nth-root method all produce<br>
correct results, using an initial root value that's 1-bit larger than the actual value.</p>
<p>Using <strong>benchmark-ips</strong> they are all basically equivalent in speed, with <strong>Newton3</strong><br>
being a smidgen faster across a range of number/root sizes. It is interesting to see<br>
how they differ in speed (minimally) based on the particular number and/or root value.</p>
<p>It is also interesting to see that when implemented and run with Crystal (current 0.21.1),<br>
while Crystal is faster (as expected), it is not multiple orders faster, and the performance<br>
profile is similar between the different implementations. (Replace <code>1 << ...</code> with <code>1.to_big_i << ...</code>)</p>
<p>Thus, Ruby's use of glibc, gmp, et al, libraries appears to be very, very good for doing this math,<br>
(at least to the accuracies of these libraries). It would still be intersting to see how much faster<br>
an optimized version of <strong>bbm</strong> would be (as I've proposed, or better), compared to Newton, especially<br>
since the stock implementation is still faster than any of the Newton implementations for some number/root sizes.</p>
<pre><code>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
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=637362017-03-22T20:17:58Zjzakiya (Jabari Zakiya)
<ul></ul><p>Noticed after Ruby 2.4.1 upgrade today (Wed 2017.03.22) performance is generally a bit slower.</p> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=640692017-04-04T22:55:22Zjzakiya (Jabari Zakiya)
<ul></ul><p>FYI</p>
<p>Looking at the GNU Multiple Precision Arithmetic Library I see it has functions for<br>
arbitrary size integer squareroot and nth-roots.</p>
<p>Doesn't Ruby already use this library?<br>
Have they been considered/tested in Ruby? Are they better than the suggested alternatives?</p>
<p><a href="https://gmplib.org/" class="external">https://gmplib.org/</a><br>
<a href="https://gmplib.org/gmp-man-6.1.2.pdf" class="external">https://gmplib.org/gmp-man-6.1.2.pdf</a></p>
<pre><code>p. 36 of gmblib 6.1.2 manual
5.8 Root Extraction Functions
int mpz_root (mpz t rop, const mpz t op, unsigned long int n) [Function]
Set rop to bp n opc; the truncated integer part of the nth root of op. Return non-zero if the
computation was exact, i.e., if op is rop to the nth power.
void mpz_sqrt (mpz t rop, const mpz t op) [Function]
Set rop to bpopc; the truncated integer part of the square root of op.
</code></pre> Ruby master - Feature #13263: Add companion integer nth-root method to recent Integer#isqrthttps://redmine.ruby-lang.org/issues/13263?journal_id=640712017-04-05T00:49:25Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>jzakiya (Jabari Zakiya) wrote:</p>
<blockquote>
<p>FYI</p>
<p>Looking at the GNU Multiple Precision Arithmetic Library I see it has functions for<br>
arbitrary size integer squareroot and nth-roots.</p>
<p>Doesn't Ruby already use this library?</p>
</blockquote>
<p>Yes. <a href="https://bugs.ruby-lang.org/issues/8796" class="external">https://bugs.ruby-lang.org/issues/8796</a></p>
<blockquote>
<p>Have they been considered/tested in Ruby?</p>
</blockquote>
<p>You can try compiling ruby by configure --with-gmp.</p>
<blockquote>
<p>Are they better than the suggested alternatives?</p>
</blockquote>
<p>This proposed function is something new to us, so not tested yet.</p>