Package Util
Class Calc
java.lang.Object
Util.Calc
The Calc class provides a series of static methods for performing various mathematical
computations like modular inverses, exponentiation, factorial, combinations,
greatest common divisor (GCD), least common multiple (LCM), and Euler's Totient function.
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic long
choose
(int n, int k) Computes n choose k (combinatorics: combinations of n items taken k at a time).static long
choose
(int n, int k, long mod) Computes n choose k under a specific modulus.static long
exp
(long val, long pow, long mod) Performs modular exponentiation efficiently using the right-to-left binary method.static long
fact
(int n) Computes the factorial of a number This version does not utilize modulus.static long
fact
(int n, long mod) Computes the factorial of n using the given modulus.static long[]
factorials
(int max) Returns an array of computed factorial values up to the provided maximum.static long[]
factorials
(int max, long mod) Returns an array of computer factorial values up to the provided maximum using the given modulus.static int
gcd
(int a, int b) Computes the greatest common divisor (GCD) of two integers using the Euclidean algorithm.static long
gcd
(long a, long b) Computes the greatest common divisor (GCD) of two long integers using the Euclidean algorithm.static long
lcm
(long a, long b) Computes the least common multiple (LCM) of two long integers using the relation LCM(a, b) = (a * b) / GCD(a, b).static long
modInverse
(long val, long mod) Computes the modular multiplicative inverse of a value under a given modulo using the extended Euclidean algorithm.static long
modInverse2
(long val, long mod) Computes the modular inverse using Fermat's Little Theorem, which requires the modulus to be prime.static long
phi
(long n) Computes Euler's Totient function φ(n), which counts the number of integers up to n that are coprime to n.static void
populateFact
(int max) Populates the array of internal factorial values without considering modulus.static void
populateFact
(int max, long mod) Populates the internal array of factorial and inverse factorial values using a given modulus.
-
Constructor Details
-
Calc
public Calc()
-
-
Method Details
-
modInverse
public static long modInverse(long val, long mod) Computes the modular multiplicative inverse of a value under a given modulo using the extended Euclidean algorithm. This method is efficient for large numbers and recursive in nature. Runs inO(log(value % mod))
, worst caseO(mod)
.- Parameters:
val
- The value for which to find the inverse.mod
- The modulus under which to compute the inverse.- Returns:
- The modular inverse of the value.
-
modInverse2
public static long modInverse2(long val, long mod) Computes the modular inverse using Fermat's Little Theorem, which requires the modulus to be prime. Runs inO(log(mod))
.- Parameters:
val
- The value to compute the inverse of.mod
- The modulus. This should be a prime number.- Returns:
- The modular inverse of the value.
-
exp
public static long exp(long val, long pow, long mod) Performs modular exponentiation efficiently using the right-to-left binary method. This method supports both positive and negative exponents. Runs inO(log(pow))
.- Parameters:
val
- The base of the exponentiation.pow
- The exponent (can be negative).mod
- The modulus for the operation.- Returns:
- The result of (val^pow) % mod.
-
factorials
public static long[] factorials(int max) Returns an array of computed factorial values up to the provided maximum. Array size ismax + 1
. This version does not utilize modulus. Runs inO(max)
.- Parameters:
max
- The maximum value for which the factorial is calculated.- Returns:
- An array of longs with the factorials up to
max!
.
-
factorials
public static long[] factorials(int max, long mod) Returns an array of computer factorial values up to the provided maximum using the given modulus. Runs inO(max)
.- Parameters:
max
- The maximum value for which the factorial is calculated.mod
- The modulus to be used for the computation.- Returns:
- An array of longs with the factorials up to
max! % mod
.
-
populateFact
public static void populateFact(int max) Populates the array of internal factorial values without considering modulus. Used forfact(int)
andchoose(int, int)
Runs inO(max)
.- Parameters:
max
- The maximum value for which the factorial is calculated.
-
populateFact
public static void populateFact(int max, long mod) Populates the internal array of factorial and inverse factorial values using a given modulus. It initializes the required arrays for computing combinations modularly. Used forfact(int, long)
andchoose(int, int, long)
Runs inO(max)
.- Parameters:
max
- The maximum value for which the factorial is calculated.mod
- The modulus to be used for the computation.
-
fact
public static long fact(int n) Computes the factorial of a number This version does not utilize modulus. Can be initialized withpopulateFact(int)
, otherwise auto-initialized. Runs inO(1)
individually,O(n)
if factorials need repopulation.- Parameters:
n
- The input number.- Returns:
n!
as a long value.
-
fact
public static long fact(int n, long mod) Computes the factorial of n using the given modulus. Can be initialized withpopulateFact(int, long)
, otherwise auto-initialized. Runs inO(1)
individually,O(n)
if factorials need repopulation. Changing mod values each call will make this method run inO(n)
every time. Consider usingfactorials(int, long)
to create your own factorial arrays for every unique mod value needed.- Parameters:
n
- The input numbermod
- The modulus.- Returns:
n! % mod
as a long value.
-
choose
public static long choose(int n, int k) Computes n choose k (combinatorics: combinations of n items taken k at a time). This version does not utilize modulus. This method utilizes an internal factorial array that can be initialized withpopulateFact(int)
, otherwise auto-initialized. Runs inO(1)
individually,O(n)
if factorials need repopulation.- Parameters:
n
- The total number of items.k
- The number of items to choose.- Returns:
- The number of combinations.
-
choose
public static long choose(int n, int k, long mod) Computes n choose k under a specific modulus. This method utilizes internal factorial and inverse factorial arrays that can be initialized withpopulateFact(int, long)
, otherwise auto-initialized. Runs inO(1)
individually,O(n)
if factorials need repopulation. Changing mod values each call will make this method run inO(n)
every time. Consider usingfactorials(int, long)
to create your own factorial arrays for every unique mod value needed.- Parameters:
n
- The total number of items.k
- The number of items to choose.mod
- The modulus.- Returns:
- The number of combinations computed under the given modulus.
-
gcd
public static int gcd(int a, int b) Computes the greatest common divisor (GCD) of two integers using the Euclidean algorithm. Runs inO(log(min(a, b)))
time.- Parameters:
a
- The first number.b
- The second number.- Returns:
- The GCD of a and b.
-
gcd
public static long gcd(long a, long b) Computes the greatest common divisor (GCD) of two long integers using the Euclidean algorithm. Runs inO(log(min(a, b)))
time.- Parameters:
a
- The first number.b
- The second number.- Returns:
- The GCD of a and b.
-
lcm
public static long lcm(long a, long b) Computes the least common multiple (LCM) of two long integers using the relation LCM(a, b) = (a * b) / GCD(a, b). Runs inO(log(min(a, b)))
time- Parameters:
a
- The first number.b
- The second number.- Returns:
- The LCM of a and b.
-
phi
public static long phi(long n) Computes Euler's Totient function φ(n), which counts the number of integers up to n that are coprime to n. Runs inO(sqrt(n))
time.- Parameters:
n
- The input number.- Returns:
- The value of Euler's Totient function for n.
-