Awesome
Roots
Introduction
This gem originally provided two methods root and roots to find all the nth roots of real and complex values.
For details on their mathematical foundation and implementation details see my paper:
Roots in Ruby
https://www.scribd.com/doc/60067570/Roots-in-Ruby
In 2017 I added the methods iroot2 and iroot|irootn to find the integer roots for arbitrary sized integers.
Installation
Add this line to your application's Gemfile:
gem 'roots'
And then execute:
$ bundle
Or install it yourself as:
$ gem install roots
Then require as:
require 'roots'
Description
Starting with Roots 2.0.0 (2017-2-21) the methods iroot2 and irootn were added (with iroot added as an alias to irootn 2017-6-1). With 2.1.0 iroot2 uses optimized Newton's method. With 2.2.0 (2017-6-17) iroot|n uses optimized Newton's method for any nth root. All are instance_methods of class Integer and accurately compute the exact real value square|nth roots for arbitrary sized integers.
If you have an application where you need the exact correct integer real value for roots, especially for arbitrary sized (large) integers, use these methods instead of root|s. These methods work strictly in the integer domain, and do not first create floating point approximations of these roots and then convert them to integers.
They are useful for applications in pure math, Number Theory, Cryptography, etc, where you need to find the exact real integer roots of polynomials, encryption functions, etc.
The methods root and roots work for all the Numeric classes (integers, floats, complex, rationals), and produce floating point results. They, thus, produce floating point approximations to the exact Integer values for real roots for arbitrary sized integers.
Usage
iroot2
Use syntax: ival.iroot2
Return the largest Integer +root+ of Integer ival such that root**2 <= ival
A negative ival will result in 'nil' being returned.
9.iroot2 => 3
-9.iroot2 => nil
120.iroot2 => 10
121.iroot2 => 11
121.iroot2.class => Integer
(10**10).iroot2 => 100000
(10**10).root(2) => 100000.0
(10**10).roots(2)[0] => 100000.0+0.0i
(10**11).iroot2 => 316227
(10**11).root(2) => 316227.76601684
(10**11).roots(2)[0] => 316227.76601684+0.0i
(10**110).iroot2 => 10000000000000000000000000000000000000000000000000000000
(10**110).root(2) => 1.0e+55
(10**110).roots(2)[0] => 1.0e+55+0.0i
(10**111).iroot2 => 31622776601683793319988935444327185337195551393252168268
(10**111).root(2) => 3.1622776601683795e+55
(10**111).roots(2)[0] => 3.1622776601683795e+55+0.0i
irootn or iroot
Use syntax: ival.irootn(n) or ival.iroot(n), where n is an Integer > 1
Return the largest Integer +root+ of Integer ival such that root**n <= ival
A negative ival for an even root n will result in 'nil' being returned.
81.irootn(2) => 9
81.irootn 3 => 4
81.iroot 4 => 3
81.iroot(4).class => Integer
-81.irootn(3) => -4
-81.irootn(4) => nil
100.irootn 4.5 => RuntimeError: root n is < 2 or not an Integer
100.iroot -2 => RuntimeError: root n is < 2 or not an Integer
(10**110).iroot(2) => 10000000000000000000000000000000000000000000000000000000
(10**110).irootn(3) => 4641588833612778892410076350919446576
(10**110).iroot 4 => 3162277660168379331998893544
(10**110).iroot(5) => 10000000000000000000000
(10**110).irootn(6) => 2154434690031883721
(10**110).irootn(7) => 5179474679231211
(10**110).irootn(8) => 56234132519034
(10**110).iroot(9) => 1668100537200
(10**110).iroot 10 => 100000000000
root
Use syntax: val.root(n,{k})
root(n,k=0) n is root 1/n exponent, integer > 0
k is nth ccw root 1..n , integer >=0
If k not given default root returned, which are:
for +val => real root |val**(1.0/n)|
for -val => real root -|val**(1.0/n)| when n is odd
for -val => first ccw complex root when n is even
9.root(2) => 3.0
-32.root(5,3) => (-2.0+0.0i)
73.root 6 => 2.04434322
73.root 6,1 => (2.04434322+0.0i)
(-100.43).root 6,6 => (1.86712994-1.07798797i)
Complex(3,19).root 7,4 => (-1.47939161+0.37266673i)
roots
Use syntax: val.roots(n,{opt})
roots(n,opt=0) n is root 1/n exponent, integer > 0
opt, optional string input, are:
0 : default (no input), return array of n ccw roots
'c'|'C': complex, return array of complex roots
'e'|'E': even, return array even numbered roots
'o'|'O': odd , return array odd numbered roots
'i'|'I': imag, return array of imaginary roots
'r'|'R': real, return array of real roots
An empty array is returned for an opt with no members.
9348134943.roots(9); -89.roots(4,'real'); 2.2.roots 3,'Im'
For Ruby >= 1.9 can also use a symbol as option: 384.roots 4,:r
Can ask: How many complex roots of x: x.roots(n,'c').size
What's the 3rd 5th root of (4+9i): Complex(4,9).root(5,3)
8.roots 3 => [(2.0+0.0i), (-1.0+1.73205081i), (-1.0-1.73205081i)]
Roots.digits_to_show
With version 1.1.0 this method was added to allow users to set
and see the number of decimal digits displayed. If no input is
given, the number of digits previously set is shown. The default
value is 8. Providing an input value sets the number of digits to
display. An input value < 1 will be set to a value of 1, to
display at least one decimal digit. An input greater than the
maximum digits shown for a given Ruby will display that maximum.
Roots.digits_to_show => 8
10.root 5 => 1.58489319
Roots.digits_to_show 11 => 11
10.root 5 => 1.58489319246
Roots.digits_to_show 16 => 16
10.root 5 => 1.5848931924611136
Roots.digits_to_show 17 => 17
10.root 5 => 1.5848931924611136
Roots.digits_to_show 0 => 1
10.root 5 => 1.6
Mathematical Foundations
For complex number (x+iy) = a*e^(i*arg) = a*[cos(arg) + i*sin(arg)]
The root values of a number are:
1) root(n) = (x + iy)^(1/n)
2) root(n) = (a*e^(i*arg))^(1/n)
3) root(n,k) = (a*e^i*(arg + 2kPI))^(1/n)
4) root(n,k) = a^(1/n)*(e^i*(arg + 2kPI))^(1/n)
5) root(n,k) = |a^(1/n)|*e^i*(arg + 2kPI)/n
6) root(n,k) = |a^(1/n)|*(cos(arg/n+2kPI/n) + i*sin(arg/n+2kPI/n))
define mag = |a^(1/n)|, theta = arg/n, and delta = 2PI/n
7) root(n,k)= mag*[cos(theta + k*delta) + i*sin(theta + k*delta)], k=0..n-1
Thus, there are n distinct roots (values).
For integer numbers:
For binary based (digital) computers (cpu), all integers are represented as
binary numbers. To find the root 'n' of an integer 'num' we can use the following
process to find the largest integer nth 'root' such that root**n <= num.
For an integer composed of 'b' bits an nth root 'n' will have at most (b/n + 1) bits.
For squareroots n = 2:
For 9 = 0b1001, it has b = 4 bits, and its squareroot has at most (4/2 + 1) = 3 bits.
The squareroot of 9 is 3 = 0b11, which is 2 bits.
For 100 = 0b1100100, b = 7, and its squareroot has at most (7/2 + 1) = 4 bits.
The squareroot of 100 is 10 = 0b1010, which is 4 bits.
For cuberoots n = 3:
For 8 = 0b1000, it has b = 4 bits, and its cuberoot has at most (4/3 + 1) = 2 bits.
The cuberoot of 8 is 2 = 0b10, which is 2 bits.
For 125 = 0b1111101, b = 7, and its cuberoot has at most (7/3 + 1) = 3 bits.
The cuberoot of 125 is 5 = 0b101, which is 3 bits.
Algorithm:
bits_shift = (num.bit_length)/n + 1 # determine max number of root bits
bitn_mask = 1 << bits_shift # set value for max bit position of root
root = 0 # initialize the value for root
until bitn_mask == 0 # step through all the bit positions for root
root |= bitn_mask # set current bit position to '1' in root
root ^= bitn_mask if root**n > num # set it back to '0' if root too large
bitn_mask >>= 1 # set bitn_mask to next smaller bit position
end
root # return exact integer value for root
Starting with 2.1.0 Newton's method for squareroots is used instead of bbm.
Starting with 2.2.0 Newton's method for general nth roots is used instead of bbm.
https://en.wikipedia.org/wiki/Nth_root_algorithm
Author
Jabari Zakiya
License
GPL-2.0+