public class Numbers extends Object
Modifier and Type | Field and Description |
---|---|
static long[][] |
binomial
Array containing the binomial coefficients (n over k)
=
binomial [n][k] for
0 ≤ n, k ≤ 66. |
static double |
gamma
Euler-Mascheroni constant γ = 0.577215664901532860605.
|
static double |
GAMMA
Euler-Mascheroni constant γ = 0.577215664901532860605.
|
static double |
RADIANS
The constant 2π/360, the ratio of 1 radians per degree.
|
static double |
SQRT_1_2
Square root of 1/2.
|
static double |
SQRT2
constant representing the square root of 2.
|
static double |
SQRT3
constant representing the square root of 3.
|
static char |
TB0
Symbol in balanced ternary system for 0.
|
static char |
TBM
Symbol in balanced ternary system for -1.
|
static char |
TBP
Symbol in balanced ternary system for +1.
|
static double |
ZETA_11
The value of the Riemann Zeta function ζ(11).
|
static double |
ZETA_13
The value of the Riemann Zeta function ζ(13).
|
static double |
ZETA_15
The value of the Riemann Zeta function ζ(15).
|
static double |
ZETA_17
The value of the Riemann Zeta function ζ(17).
|
static double |
ZETA_19
The value of the Riemann Zeta function ζ(19).
|
static double |
ZETA_21
The value of the Riemann Zeta function ζ(21).
|
static double |
ZETA_23
The value of the Riemann Zeta function ζ(23).
|
static double |
ZETA_25
The value of the Riemann Zeta function ζ(25).
|
static double |
ZETA_3
The value of the Riemann Zeta function ζ(3).
|
static double |
ZETA_5
The value of the Riemann Zeta function ζ(5).
|
static double |
ZETA_7
The value of the Riemann Zeta function ζ(7).
|
static double |
ZETA_9
The value of the Riemann Zeta function ζ(9).
|
Modifier and Type | Method and Description |
---|---|
static String |
add3(String m,
String n)
Returns the sum of m and n in the ternary system.
|
static char |
bbp(long position)
Returns the hexadecimal digit of π at the given position,
according to the Bailey-Borwein-Plouffe algorithm.
|
static Rational |
bernoulli(int n)
Returns the Bernoulli number Bn of the nonnegative integer
n.
|
static Rational[] |
bernoulliNumbers(int n)
Returns an array of n+1 rational numbers with entry number j
representing the Bernoulli number Bj, j = 0, 1, ..., n.
|
static long[] |
bestRationalApproximation(double x,
int limit)
Returns the best rational approximation of a real number x,
that is, the integers p, q such that x ≈ p/q.
|
static double |
beta(double z,
double w)
Returns the beta function value
B(z,w) = ∫01 tz-1
(1-t)w-1 dt.
|
static double |
binomial(long n,
long k)
Returns the binomial coefficient (n choose k)
as a floating point number.
|
static long |
binToDec(String bin)
Returns a binary string as an integer.
|
static double |
binToDouble(String bin)
Returns a binary string as a decimal floating-point number.
|
static String |
binToHex(String bin)
Returns a binary string as a hexadecimal string.
|
static long[] |
continuedFraction(double x,
int limit)
Returns an array containing coefficients of the continued fraction of
the number x, with at most
limit coefficients. |
static String |
decToBin(double z)
Returns z as a binary string with at most 70 digits right of
the binary point.
|
static String |
decToBin(double z,
int limit)
Returns z as a binary string with at most
limit
positions right of the binary point. |
static String |
decToBin(long n)
Returns n as a binary string.
|
static String |
decToBin(long n,
int minimumLength)
Returns n as a binary string of the specified minimum length.
|
static String |
decToBinByte(long n)
Returns n as a binary string in a 1-byte form.
|
static String |
decToHex(double z)
Returns z as a hexadecimal string with at most 20 digits right of
the hexadecimal point.
|
static String |
decToHex(double z,
int limit)
Returns z as a hexadecimal string with at most
limit
positions right of the hexadecimal point. |
static String |
decToHex(long n)
Returns n as a hexadecimal string.
|
static String |
decToHex2Byte(long n)
Returns n as a hexadecimal string in 2-byte form.
|
static String |
decToTern(double z)
Returns z as a ternary string with at most 40 digits right of
the ternary point.
|
static String |
decToTern(double z,
int limit)
Returns z as a ternary string with at most
limit
positions right of the ternary point. |
static String |
decToTern(long n)
Returns n as a ternary string.
|
static String |
decToTern(long n,
int minimumLength)
Returns n as a ternary string of the specified minimum length.
|
static String |
decToTernB(double z)
Returns z as a balanced ternary string with at most
40 digits right of
the ternary point.
|
static String |
decToTernB(double z,
int limit)
Returns z as a balanced ternary string with at most
limit
positions right of the ternary point. |
static String |
decToTernB(long n)
Returns n as a balanced ternary string.
|
static String |
decToTernB(long n,
int minimumLength)
Returns n as a balanced ternary string of the specified minimum length.
|
static long |
div3b(long n)
Returns the integer division n/3 in the balanced ternary system.
|
static long[] |
euclid(long m,
long n)
Returns an array of three integers x[0], x[1], x[2] as given by the extended
Euclidian algorithm for positive integers m and n.
|
static BigInteger |
exactBinomial(int n,
int k)
Returns the exact binomial coefficient (n choose k)
as an integer.
|
static BigInteger |
factorial(int n)
Returns the exact value of n!.
|
static double |
gamma(double x)
The Euler Gamma function
|
static long |
gcd(long m,
long n)
Returns the greatest common divisor of the integers m and n.
|
static String |
grayCode(long x)
Returns the Gray code of an integer.
|
static String |
grayCode(long x,
int minimumLength)
Returns the Gray code of an integer x, with a given minimum length.
|
static String |
grayCodeToBinary(String grayCode)
Returns binary representation of the integer in which is represented by a Gray code string.
|
static String |
grayCodeToBinary(String grayCode,
int minimumLength)
Returns binary representation of the integer in which is represented by a Gray code string.
|
static long |
grayCodeToLong(String grayCode)
Returns the integer represented by a Gray code string.
|
static String |
hexToBin(String hex)
Returns a hexadecimal string as a binary string.
|
static long |
hexToDec(String hex)
Returns a hexadecimal string as a decimal integer.
|
static double |
hexToDouble(String hex)
Returns a hexadecimal string as a decimal floating-point number.
|
static double |
hypotenuse(double a,
double b)
Returns sqrt(a^2 + b^2) without under/overflow.
|
static double |
incBeta(double a,
double b,
double x)
The incomplete beta function for 0 <= x <= 1.
|
static double |
incGamma(double a,
double x)
incomplete Gammma function.
|
static boolean |
isPower(long n)
Tests whether there exist integers m and k such that
n = mk.
|
static boolean |
isPrime(long n)
Tests deterministically whether the given integer is prime.
|
static boolean |
isStrongProbablePrime(int n,
int a)
Returns true if n is a strong probable prime to base a,
and false if n is not prime.
|
static int |
largestPrimeFactor(int n)
Determines the largest prime factor of a number, using naive trial division, appropriate
only for comparatively small integers.
|
static long |
lcm(long m,
long n)
Returns the least common multiple of m and n.
|
static int |
leastPrimeFactor(int n)
Determines the least prime factor of a number, using naive trial division, appropriate
only for comparably small integers.
|
static double |
lnFactorial(long n)
Returns ln (n!).
|
static double |
lnGamma(double x)
Logarithm of the Euler Gamma function.
|
static double |
mod(double n,
double m)
Returns the value of n mod m, even for negative values.
|
static long |
mod(long n,
long m)
Returns the value of n mod m, even for negative values.
|
static char |
mod3b(long n)
Returns the symbol in the balanced ternary system representing the value
n mod 3.
|
static double |
modPow(double x,
long e,
double n)
Returns the value of (xe) mod n.
|
static int |
modPow(long x,
long e,
int m)
Returns the value of xe mod n.
|
static long |
modPow(long x,
long e,
long n)
Returns the value of xe mod n.
|
static BigInteger[] |
numberOfPartitions(int n)
Returns an array of the numbers of partitions up to the number n.
|
static long |
ord(long m,
long n)
Returns the order ord(m,n) of m modulo n.
|
static ArrayList<LinkedList<Integer>> |
partitions(int n)
Returns a list of all partitions of a small integer n.
|
static double |
pow(double x,
long e)
Returns the value of xe.
|
static long |
pow(long x,
long e)
Returns the value of xe.
|
static long |
pow2(int n)
Returns the value of 2n.
|
static double |
root(int n,
double z)
Returns the nth root of z, with an accuracy of 1e-12 z.
|
static long[] |
solveLinearDiophantine(long a,
long b,
long c)
Returns the array {d,x,y} such that the linear Diophantine equation
ax + by = c is solved and d = gcd(a,b). |
static long |
sqr(long x)
Returns the value of x2.
|
static int |
sum(Collection<Integer> list)
Returns the sum of the integers of the specified list.
|
static String |
ternaryComplement(String tern)
Returns the ternary complement of the specified number in ternary
representation.
|
static long |
ternBToDec(String tern)
Returns a balanced ternary string as an integer.
|
static double |
ternBToDouble(String tern)
Returns a balanced ternary string as a decimal floating-point number.
|
static long |
ternToDec(String tern)
Returns a ternary string as an integer.
|
static double |
ternToDouble(String tern)
Returns a ternary string as a decimal floating-point number.
|
static String |
ternToTernB(String tern)
Returns a ternary string as an balanced ternary string.
|
public static final double gamma
GAMMA
,
BigNumbers.GAMMA
,
Constant Field Valuespublic static final double GAMMA
BigNumbers.GAMMA
,
Constant Field Valuespublic static final double SQRT2
BigNumbers.SQRT_TWO
,
Constant Field Valuespublic static final double SQRT3
public static final double SQRT_1_2
BigNumbers.SQRT_ONE_HALF
,
Constant Field Valuespublic static final double RADIANS
Math.PI
,
BigNumbers.RADIANS
,
Constant Field Valuespublic static final double ZETA_3
BigNumbers.ZETA_3
,
Constant Field Valuespublic static final double ZETA_5
BigNumbers.ZETA_5
,
Constant Field Valuespublic static final double ZETA_7
BigNumbers.ZETA_7
,
Constant Field Valuespublic static final double ZETA_9
BigNumbers.ZETA_9
,
Constant Field Valuespublic static final double ZETA_11
BigNumbers.ZETA_11
,
Constant Field Valuespublic static final double ZETA_13
BigNumbers.ZETA_13
,
Constant Field Valuespublic static final double ZETA_15
BigNumbers.ZETA_15
,
Constant Field Valuespublic static final double ZETA_17
BigNumbers.ZETA_17
,
Constant Field Valuespublic static final double ZETA_19
BigNumbers.ZETA_19
,
Constant Field Valuespublic static final double ZETA_21
BigNumbers.ZETA_21
,
Constant Field Valuespublic static final double ZETA_23
BigNumbers.ZETA_23
,
Constant Field Valuespublic static final double ZETA_25
BigNumbers.ZETA_25
,
Constant Field Valuespublic static final long[][] binomial
binomial
[n][k] for
0 ≤ n, k ≤ 66.
Here binomial
[n][k] = 0 if n < k.public static final char TBM
public static final char TB0
public static final char TBP
public static double beta(double z, double w)
z
- first argumentw
- second argumentgamma(double)
public static double incBeta(double a, double b, double x)
1 I_x (a,b) = -------- int_0^x t^{a-1} (1-t)^{b-1} dt. B(a,b)It can be well approximated by the continued fraction
x^a (1-x)^b { 1 } I_x (a,b) = ------------- { ----------------- } a B(a,b) { d_1 } { 1 + ------------ } { d_2 } { 1 + -------- } { d_3 } { 1 + ---- } { ... }with the coefficients
(a+m)(a+b+m) m(b-mm) d_{2m+1} = - -------------- x, d_{2m} = -------------- x. (a+2m)(a+2m-1) (a+2m-1)(a+2m)The approximation converges rapidly for
a+1 x > -----. a+b+1If this condition is not satisfied, then just 1-x does, and we can apply the symmetry relation
I_x (a,b) = 1 - I_{1-x} (b,a).
a
- first parameter of the beta function, a > 0b
- second parameter of the beta function, b > 0x
- indexbeta(double,double)
public static double gamma(double x)
Γ(x) = ∫0∞ tx-1 e-t dt.
x
- the argumentbeta(double, double)
public static double lnGamma(double x)
x
- the argumentgamma(double)
public static double incGamma(double a, double x)
a
- the argument, a > 0x
- the argumentgamma(double)
public static BigInteger exactBinomial(int n, int k)
n
- an integerk
- an integerpublic static double binomial(long n, long k)
n
- an integerk
- an integerpublic static double lnFactorial(long n)
n
- an integerpublic static BigInteger factorial(int n)
n
- the value to be computedIllegalArgumentException
- if n < 0public static long mod(long n, long m)
n mod m = n - ⎣n/m⎦ for m ≠ 0, and n mod 0 = n.
For instance, 5 mod 3 = 2, but -5 mod 3 = 1, 5 mod (-3) = -1, and -5 mod (-3) = -2. See R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics. 2nd Edition. Addison-Wesley, Upper Saddle River, NJ 1994, §3.4 (p.82)n
- the value to be raised to the powerm
- the moduluspublic static double mod(double n, double m)
n
- the value to be computedm
- the moduluspublic static long pow(long x, long e)
x
- the value to be raised to the powere
- the exponentIllegalArgumentException
- if e < 0public static double pow(double x, long e)
x
- the value to be raised to the powere
- the exponentpublic static long pow2(int n)
n
- the exponentpublic static int modPow(long x, long e, int m)
x
- the value to be raised to the powere
- the exponentm
- the modulusArithmeticException
- if e < 0 and gcd(x, n) > 1public static long modPow(long x, long e, long n)
x
- the value to be raised to the powere
- the exponentn
- the modulusArithmeticException
- if e < 0 and gcd(x, n) > 1public static double modPow(double x, long e, double n)
x
- the value to be raised to the powere
- the exponentn
- the moduluspublic static double hypotenuse(double a, double b)
norm
of a vector
x = (x0, ..., xn-1) by
double norm = 0; for (int i = 0; i < x.length; i++) { norm = Numbers.hypotenuse(norm, x[i]); }
a
- the first triangle legb
- the first triangle legpublic static double root(int n, double z)
Double.POSITIVE_INFINITY
is returned
depending on whether |z| < 0, |z| = 1, or z > 1;
if n = 0 and z < -1, then the value is not defined and an exception is thrown.
If n < 0, then root(-n, z) is returned.n
- the radicalz
- the radicandIllegalArgumentException
- if (a) n = 0 and z < -1,
or (b) z < 0 and n is evenpublic static long sqr(long x)
x
- the value to be squaredpublic static long gcd(long m, long n)
m
- the first integern
- the second integerpublic static long[] euclid(long m, long n)
x[0] = gcd(m, n) = x[1] m + x[2] n.
This methods implements a recursive version of the extended Euclidian algorithm.m
- the first integer, must be positiven
- the second integer, must be positivegcd(long,long)
,
BigNumbers.euclid(java.math.BigInteger,java.math.BigInteger)
public static long lcm(long m, long n)
m
- the first integern
- the second integergcd(long,long)
public static boolean isPrime(long n)
n
- the integer to testpublic static long[] solveLinearDiophantine(long a, long b, long c)
ax + by = c
is solved and d = gcd(a,b). If the equation is not solvable, then {0,0,0} is returned. Note that the equation is solvable if and only if gcd(a,b) divides c. Moreover, from a given solution {x0, y0} a general solution can be computed byx = x0 + bt/d, y = y0 - at/d
for t ∈ ℤ. Cf. R. Schulze.Pillot: Elementare Algebra und Zahlentheorie. Springer, Berlin Heidelberg 2007, Satz 3.12.a
- first coefficient of the linear Diophantine equationb
- second coefficient of the linear Diophantine equationc
- third coefficient of the linear Diophantine equationpublic static boolean isStrongProbablePrime(int n, int a)
n
- the number to be tested on strong probable primalitya
- the base of the strong probable primality testIllegalArgumentException
- if n ≤ 3, or a ≤ 1,
or a ≥ n - 1BigNumbers.isStrongProbablePrime(BigInteger,BigInteger)
public static int leastPrimeFactor(int n)
n
- an integerpublic static int largestPrimeFactor(int n)
n
- an integerpublic static long ord(long m, long n)
ord(m,n) = mini { i > 0 : mi = 1 mod n },
The order is found by Floyd's cycle finding algorithm.m
- the first integern
- the second integerpublic static boolean isPower(long n)
n
- the number to be checkedpublic static long[] continuedFraction(double x, int limit)
limit
coefficients.
Note that by the finite precision of x the higher continuous fraction
coefficients get more and more imprecise. For instance, for the
Euler number the coefficients are correct up to the limit 20.x
- the number to be expanded as a continuous fractionlimit
- the maximum number of continuous fraction coefficients to be computedlimit
containing the continuous fraction coefficientspublic static long[] bestRationalApproximation(double x, int limit)
limit
. Usually, the value of limit
should be about 20.x
- the number to be approximatedlimit
- the maximum number of continued fraction coefficients being consideredy
where y[0]
= p and
y[1]
= q such that x ≈ p/qcontinuedFraction(double,int)
public static Rational bernoulli(int n)
Bn | = - |
|
| ( |
| ) | Bj |
bernoulliNumbers(int)
may be
used more efficiently, giving the whole list of Bernoulli numbers
up to Bn.n
- a nonnegative integerIllegalArgumentException
- if n<0bernoulliNumbers(int)
public static Rational[] bernoulliNumbers(int n)
n
- a nonnegative integerIllegalArgumentException
- if n<0bernoulli(int)
public static BigInteger[] numberOfPartitions(int n)
For details see R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics. 2nd Edition. Addison-Wesley, Upper Saddle River, NJ 1994, §7.1 (p. 330)
n
- a positive integerp
of the numbers of partitions where
p[i]
is the number of partitions of i
≤ n.partitions(int)
public static ArrayList<LinkedList<Integer>> partitions(int n)
The running time behavior of this algorithm is very bad, the required
time complexity is estimated as O((n!)2).
The computation of the partitions for a small number n < 50
is done in less than 30 seconds, but for instance n = 60 requires
about 4 minutes on a 2 GHz dual core processor system.
If you are interested only in the number of partitions, you may consider
numberOfPartitions(int)
.
For details see R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics. 2nd Edition. Addison-Wesley, Upper Saddle River, NJ 1994, §7.1 (p. 330)
n
- a positive integernumberOfPartitions(int)
public static int sum(Collection<Integer> list)
list
- a list of integerspublic static char bbp(long position)
position
- the position of the searched hexadecimal digitpublic static String decToBin(long n)
n
- the decimal value to be represented in binary formpublic static String decToBin(long n, int minimumLength)
n
- the decimal value to be represented in binary formminimumLength
- the minimum length of the returned binary stringpublic static String decToBinByte(long n)
n
- the decimal number to be represented in a 1 byte binary form.public static long binToDec(String bin)
bin
- the binary string to be represented in decimal formNumberFormatException
- if the string is not binarypublic static String decToBin(double z)
z
- the decimal value to be represented in binary form.public static String decToBin(double z, int limit)
limit
positions right of the binary point.z
- the decimal value to be represented in binary form.limit
- the maximum position after the binary point.public static double binToDouble(String bin)
bin
- the binary string to be represented in decimal form.NumberFormatException
- if the string is not binarypublic static String binToHex(String bin)
bin
- the binary string to be represented in hexadecimal formNumberFormatException
- if the string is not binarypublic static String decToTern(long n)
n
- the decimal value to be represented in ternary formpublic static String decToTern(long n, int minimumLength)
n
- the decimal value to be represented in ternary formminimumLength
- the minimum length of the returned ternary stringpublic static long ternToDec(String tern)
tern
- the ternary string to be represented in decimal formNumberFormatException
- if the string is not ternarypublic static String decToTern(double z)
z
- the decimal value to be represented in ternary form.public static String decToTern(double z, int limit)
limit
positions right of the ternary point.z
- the decimal value to be represented in ternary form.limit
- the maximum position after the ternary point.public static double ternToDouble(String tern)
tern
- the ternary string to be represented in decimal form.NumberFormatException
- if the string is not ternarypublic static String ternaryComplement(String tern)
tern
- number in ternary representationpublic static String add3(String m, String n)
m
- number in ternary representationn
- number in ternary representationpublic static long div3b(long n)
n
- the decimal value to be divisedpublic static char mod3b(long n)
n
- the decimal value to be divisedpublic static String decToTernB(long n)
n
- the decimal value to be represented in ternary formpublic static String decToTernB(long n, int minimumLength)
n
- the decimal value to be represented in balanced ternary formminimumLength
- the minimum length of the returned ternary stringpublic static long ternBToDec(String tern)
tern
- the ternary string to be represented in decimal formNumberFormatException
- if the string is not ternarypublic static String decToTernB(double z)
z
- the decimal value to be represented in balanced ternary form.public static String decToTernB(double z, int limit)
limit
positions right of the ternary point.z
- the decimal value to be represented in balanced ternary form.limit
- the maximum position after the ternary point.public static double ternBToDouble(String tern)
tern
- the ternary string to be represented in decimal form.NumberFormatException
- if the string is not balanced ternarypublic static String ternToTernB(String tern)
tern
- the ternary string to be represented in balanced ternary formNumberFormatException
- if the string is not ternarypublic static String decToHex(long n)
n
- the decimal value to be represented in hexadecimal form.public static String decToHex(double z)
z
- the decimal value to be represented in hexadecimal form.public static String decToHex(double z, int limit)
limit
positions right of the hexadecimal point.z
- the decimal value to be represented in hexadecimal form.limit
- the maximum position after the hexadecimal point.public static String decToHex2Byte(long n)
n
- the decimal number to be represented in a 2 byte hexadecimal form.public static String hexToBin(String hex)
hex
- the hexadecimal string to be represented in decimal form.NumberFormatException
- if the string is not hexadecimalpublic static long hexToDec(String hex)
hex
- the hexadecimal string to be represented in decimal form.NumberFormatException
- if the string is not hexadecimalpublic static double hexToDouble(String hex)
hex
- the hexadecimal string to be represented in decimal form.NumberFormatException
- if the string is not hexadecimalpublic static String grayCode(long x, int minimumLength)
x
- an integerminimumLength
- the minimum length of the returned Gray code stringpublic static String grayCode(long x)
x
- an integerpublic static long grayCodeToLong(String grayCode)
grayCode
- a Gray code stringNumberFormatException
- if the Gray code string does not contain a parsable longpublic static String grayCodeToBinary(String grayCode, int minimumLength)
grayCode
- a Gray code stringminimumLength
- the minimum length of the returned Gray code stringNumberFormatException
- if the string does not represent a Gray codegrayCodeToBinary(String)
public static String grayCodeToBinary(String grayCode)
grayCode
- a Gray code stringNumberFormatException
- if the string does not represent a Gray codegrayCodeToBinary(String, int)