Skip to content
BranchesTags

Repository files navigation

JBroMath

Math utilities for Java.

Dependencies:

  • Java 8.
  • JUnit (for tests only).

Released into public domain.

Contents:

  1. MathUtils
    1. Conversion functions
      1. toArabicNumerals
      2. toRomanNumerals
      3. toBigDecimal
      4. toUnsignedBigInteger
      5. toPlainString
      6. toRoundedString
    2. Rounding
      1. toRoundedString
      2. round
      3. trunc
      4. ceil
      5. floor
    3. Exponentiation
      1. pow10
      2. pow
      3. powExact
    4. Modular arithmetic
      1. mod
      2. mods
      3. modAdd
      4. modSubtract
      5. modMultiply
      6. modDivide
      7. modInverse
      8. modPow
    5. Common divisors and multiples
      1. egcd
      2. gcd
      3. lcm
      4. lcmExact
      5. isRelativelyPrime
    6. Roots
      1. isqrt
      2. uisqrt
      3. icbrt
      4. iroot
    7. Perfect powers
      1. getBaseOfPerfectSquare
      2. isPerfectSquare
      3. getBaseOfPerfectCube
      4. isPerfectCube
      5. getBaseOfPerfectPower
      6. isPerfectPower
    8. Unsigned arithmetic
      1. toUnsignedBigInteger
      2. uisqrt
      3. remainderUnsigned
      4. divideUnsigned
  2. BigUtils
    1. Constants
    2. Perfect powers
      1. getBaseOfPerfectSquare
      2. isPerfectSquare
    3. Common divisors and multiples
      1. lcm
      2. isRelativelyPrime
    4. Roots
      1. isqrt
    5. Modular arithmetic
      1. mod
      2. mods
  3. PrimeUtils
    1. isPrime
    2. isGaussianPrime
    3. isMersenneNumber
    4. isMersennePrime
    5. isFermatNumber
    6. isFermatPrime
    7. passesTrialDivision
    8. passesLucasLehmer
    9. passesLucasPseudoprime
    10. passesMillerRabin
    11. passesMiller
    12. passesBailliePSW
  4. PrimesIterable
    1. getInt/Long/BigIntegerTotally
    2. getInt/Long/BigIntegerMax
    3. getNext

MathUtils

This class contains functions with primitive-type (byte, short, int, long, float, double) arguments.

  • Test coverage: 100%
  • Javadoc coverage: 100%
  • Integer/Long.MIN_VALUE/MAX_VALUE are handled properly.

Conversion functions

toArabicNumerals - converts string representation of Roman numerals to decimal value. There are three variants of this function:

inttoArabicNumeralsInt( String ) throwsIllegalArgumentException

A classic one, supports N (nulla) for zero. Converts values to int in range from 0 to 3999 (inclusively). Performs input validation. E.g., inputs like IIII, IIX or MMMMMXX are considered incorrect.

Throws IllegalArgumentException if the input is null, empty or not a valid Roman number.

doubletoArabicNumeralsDouble( String ) throwsIllegalArgumentException

Supports N for zero, S (semis) for a half and minus sign for negative values. Converts values to double. Does not check the order of letters nor the length of the input. So any big value is permitted (e.g., MMMMMMXI). Incorrect letters are verified though.

Throws IllegalArgumentException if the input contains incorrect characters. If the input is null or empty then 0.0 is returned.

inttoArabicNumeralsExcelInt( String )

A variant identical to Microsoft Excel's ARABIC( text ) function. Supports minus sign. Accepts strings up to 255 characters (inclusively).

Throws IllegalArgumentException if the input contains incorrect characters. If the input is null or empty then 0 is returned.

toRomanNumerals - converts a decimal number to its string representation as Roman numerals. There are also three variants of this function:

StringtoRomanNumeralsString( intnumber, booleanshortest ) throwsNumberFormatException

A classic one. Permits zero (the result would be N - nulla). The value of number should lie in range [ 0 .. 3999 ]. If the argument shortest is set to true then the shortest possible output is generated (but it won't be a classic one). Example:

toRomanNumeralsString( 49, false ) = XLIX - correct classic way;

toRomanNumeralsString( 49, true ) = IL - it means L - I = 50 - 1 = 49 according to Roman-to-Arabic conversion rules. And this is the shortest possible way to write 49 in Roman numerals. A reversed conversion can be done by toArabicNumeralsExcelInt function. Microsoft Excel would accept IL correctly too.

Throws NumberFormatException if number < 0 or number ≥ 4000.

StringtoRomanNumeralsString( doublenumber, booleanshortest ) throwsNumberFormatException

The same as a previous one but accepts half values also (which turn into S - semis).

Throws NumberFormatException if number ≤ -1000000 or number ≥ 1000000.

StringtoRomanNumeralsExcelString( intnumber, intmode ) throwsNumberFormatException, IllegalArgumentException

A variant identical to Microsoft Excel's ROMAN( number, mode ) function. The mode values are:

  • 0 - Classic form of Roman numerals: I, V, X, L, C, D, M and subtractive sequences CM, CD, XC, XL, IX, IV are allowed.
  • 1 - More concise: LM, LD, VC, VL are also allowed.
  • 2 - More concise: XM, XD, IC, IL.
  • 3 - More concise: VM, VD.
  • 4 - Minimal (according to Excel's terms): IM, ID.

Note that the mode 4 doesn't produce absolutely minimal representation of all the numbers. Use toRomanNumeralsString with shortest set to true if the absolutely minimal form is required. Example: ROMAN( 78; 4 ) = LXXVIII but minimal is IIXXC. And ARABIC function correctly accepts both of these input strings.

Throws NumberFormatException if number < 0 or number ≥ 4000.

Throws IllegalArgumentException if mode < 0 or mode > 4.

BigDecimaltoBigDecimal( Number ) throwsNumberFormatException

Converts a number to BigDecimal.

  • If the number is double or float then decimal (not binary) representation is used.
  • If the number class is not one of standard Java number classes then conversion is made via doubleValue() call.
  • If the number is not finite (infinity or NaN) then NumberFormatException is thrown.

toUnsignedBigInteger - converts an unsigned number to BigInteger. There are two versions of this method:

BigIntegertoUnsignedBigInteger( int )
BigIntegertoUnsignedBigInteger( long )

One for int argument and one for long.

toPlainString - converts a floating-point number to its string representation without an exponent field.

StringtoPlainString( double )
StringtoPlainString( float )
  • NaN, Infinity and -Infinity produce "NaN", "Infinity" and "-Infinity" respectively.
  • When the number is integer, the fractional part is omitted (1.0 would result in "1", not in "1.0").
  • Positive and negative zeros produce "0" and "-0" respectively.
  • Fractional part is represented without an exponent field (0.00000001 would result in "0.00000001", not in "1e-8").

StringtoRoundedString( Numbernumber, intprecision )

Rounds a number to precision decimal places and returns a plain string representation (without an exponent field) of the resulting number.

  • NaN, Infinity and -Infinity produce "NaN", "Infinity" and "-Infinity" respectively.
  • Both positive and negative zero produce "0" (if a negative number becomes -0.0 after rounding, it would result in "0" too).
  • If number is negative then the output equals to "-" + toRoundedString( -number ).
  • Round half up method is used for rounding positive numbers.
  • Negative precision is supported (5123.6 with precision -2 outputs "5100").

Rounding

toRoundedString - rounds a number to specified quantity of decimal places and returns a plain string representation of the result.

doubleround( doublevalue, intdecimals )

Symmetric rounding half away from zero to decimals places to the right of the decimal point.

This method differs from Math.round( double ) for negative numbers, because the latter uses asymmetric rounding half up.

round( 12.7, 0 ) = 13.0round( -12.25, 1 ) = -12.3

doubletrunc( doublevalue, intdecimals )

Rounding towards zero (truncating) to decimals places to the right of the decimal point.

trunc( 12.7, 0 ) = 12.0trunc( -12.25, 1 ) = -12.2

doubleceil( doublevalue, intdecimals )

Rounding up (ceiling) to decimals places to the right of the decimal point.

ceil( 12.7, 0 ) = 13.0ceil( -12.25, 1 ) = -12.2

doublefloor( doublevalue, intdecimals )

Rounding down (flooring) to decimals places to the right of the decimal point.

floor( 12.7, 0 ) = 12.0floor( -12.25, 1 ) = -12.3

Exponentiation

doublepow10( inty )

Returns 10 raised to power y (10y). More info here: JDK-4358794: Math package: implement pow10 (power of 10) with optimization for integer powers. This method is more precise than Math.pow when the base is a power of 10.

pow - returns x raised to power y (xy). There are three variations:

doublepow( doublex, inty )

Overload of Math.pow( double x, double y ) method for integer exponent. Returns NaN and infinity in the same situations as Math.pow does.

longpow( longx, inty ) throwsArithmeticExceptionintpow( intx, inty ) throwsArithmeticException

Purely integer exponentiation. These two methods throw exception if x = 0 and y < 0 (resulting in infinity). May overflow. Use powExact if overflow check is needed.

longpowExact( longx, inty ) throwsArithmeticExceptionintpowExact( intx, inty ) throwsArithmeticException

Returns value of x raised in power y (xy), throwing an exception if the result overflows long (or int respectively). Analogous to Math.multiplyExact and other Math.<...>Exact methods.

Also, throws ArithmeticException if x = 0 and y < 0 (the result becomes infinite).

Modular arithmetic

intmod( intv, intm )
longmod( longv, longm )

Returns v (mod m). The value returned lies in range [ 0 .. |m| - 1 ].

This method differs from v % m in that it always returns non-negative value.

If m = 0 then MathUtils.NOT_FOUND is returned.

intmods( intv, intm )
longmods( longv, longm )

Signed mod. The value returned lies in range [ -( |m| - 1 ) / 2 .. |m| / 2 ].

If m = 0 then MathUtils.NOT_FOUND is returned.

intmodAdd( longa, longb, intm )
longmodAdd( longa, longb, longm )

Modular addition. Returns ( a + b )( mod m ).

Differs from ( a + b ) % m in that it always returns non-negative value and never overflows.

If m = 0 then MathUtils.NOT_FOUND is returned.

intmodSubtract( longa, longb, intm )
longmodSubtract( longa, longb, longm )

Modular subtraction. Returns ( a - b )( mod m ).

Differs from ( a - b ) % m in that it always returns non-negative value and never overflows.

If m = 0 then MathUtils.NOT_FOUND is returned.

intmodMultiply( longa, longb, intm )
longmodMultiply( longa, longb, longm )

Modular multiplication. Returns ( a * b )( mod m ).

Differs from ( a * b ) % m in that it always returns non-negative value and never overflows.

If m = 0 then MathUtils.NOT_FOUND is returned.

int[] modDivide( inta, intb, intm )
long[] modDivide( longa, longb, longm )

Modular division. Returns a solution of equation ( x * b )( mod m ) = a.

The solution has the form: x = x0 + increment * k, where

  • 0 ≤ k < gcd, k is integer
  • increment = m / gcd
  • x0 = a / gcd * modInverse( b, m )
  • gcd = gcd( b, m )

If a % gcd != 0 then the equation cannot be solved.

The value returned is a tuple ( x0, increment, quantity ), where quantity is the quantity of solutions, it equals to gcd. If there's no solution, a tuple ( MathUtils.NOT_FOUND, 0, 0 ) is returned.

intmodInverse( inta, intm )
longmodInverse( longa, longm )

Modular multiplicative inverse. Analogous to BigInteger.modInverse.

Returns s = a-1 (mod m), s is such a number that (s * a) (mod m) = 1.

If such number s doesn't exist, MathUtils.NOT_FOUND is returned (if a and m are not coprime).

If m = 0 then MathUtils.NOT_FOUND is returned.

The result is always non-negative if it exists.

intmodPow( longbase, longexponent, intm )
longmodPow( longbase, longexponent, longm )

Raise base to exponent power mod m. Returns baseexponent (mod m).

If exponent < 0 and base is not relatively prime to m then MathUtils.NOT_FOUND is returned.

If m = 0 then MathUtils.NOT_FOUND is returned.

Common divisors and multiples

int[] egcd( inta, intb )
long[] egcd( longa, longb )

Extended Euclidean greatest common divisor (GCD) algorithm function.

A tuple ( gcd, x, y ) is returned, where gcd is greatest common divisor of a and b.

x and y are integers such that x * a + y * b = gcd.

intgcd( inta, intb )
longgcd( longa, longb )

Greatest common divisor (GCD).

intlcm( inta, intb )
longlcm( longa, longb )

Least common multiple (LCM). May overflow. Use lcmExact if overflow check is needed.

intlcmExact( inta, intb ) throwsArithmeticExceptionlonglcmExact( longa, longb ) throwsArithmeticException

Least common multiple with overflow check. Analogous to Math.multiplyExact and other Math.<...>Exact methods.

Throws ArithmeticException if the result overflows int (or long respectively).

booleanisRelativelyPrime( inta, intb )
booleanisRelativelyPrime( longa, longb )

Determine if a is relatively prime to b, i.e. gcd( a, b ) = 1.

Roots

longisqrt( longn ) throwsArithmeticExceptionintisqrt( intn ) throwsArithmeticException

Returns integer square root of n.

The greatest integer less than or equal to the square root of n. In other words, trunc( sqrt( n ) ). Example:

isqrt( 27 ) = 5 because 5 * 5 = 25 ≤ 27 and 6 * 6 = 36 > 27

Throws exception if n < 0.

intuisqrt( longn )
intuisqrt( intn )

Unsigned integer square root. The argument and the returned value are treated as unsigned.

longicbrt( longn )
inticbrt( intn )

Integer cubic root. Returns trunc( cbrt( n ) ).

longiroot( longn, intpower ) throwsArithmeticExceptionintiroot( intn, intpower ) throwsArithmeticException

Returns integer root of n of given degree power. In other words, returns trunc( power√n ).

Throws exception if one of the following conditions holds:

  • n < 0 and power is even (the result is a complex number)
  • n = 0 and power < 0 (resulting in infinity)
  • n = 1 and power = 0 (the result is 1∞, which is undefined)
  • n > 1 and power = 0 (the result is n∞ = ∞)

Perfect powers

longgetBaseOfPerfectSquare( longn )

Finds a root of a perfect square.

Given integer number n, find integer number s such that s2 = n.

Returns MathUtils.NOT_FOUND if such number s doesn't exists.

booleanisPerfectSquare( longn )

Determine if a given number n is a perfect square.

longgetBaseOfPerfectCube( longn )

Given integer number n, find integer number s such that s3 = n.

Returns MathUtils.NOT_FOUND if such number s doesn't exists.

booleanisPerfectCube( longn )

Determine if a given number n is a perfect cube.

getBaseOfPerfectPower - finds a root of a perfect power.

longgetBaseOfPerfectPower( longn, intpower )

Given integer numbers n and power, find integer number s such that spower = n.

Returns MathUtils.NOT_FOUND if such number s doesn't exists.

long[] getBaseOfPerfectPower( longnumber )

Given integer number, find if there exist integer numbers s and q such that number = sq, q > 1.

The value returned is a tuple ( s, q ). The base s is minimal, the power q is maximal of all suitable tuples ( s, q ).

If such numbers s and q don't exist, null is returned.

isPerfectPower - determine if a given number n is a perfect power.

booleanisPerfectPower( longn, intpower )

This method checks n against only one given power.

booleanisPerfectPower( longn )

This method checks if there exist such numbers s and q that n = sq, q > 1. In other words, if n is a perfect power of any power q > 1.

Unsigned arithmetic

toUnsignedBigInteger - converts an unsigned number to BigInteger.

uisqrt - unsigned integer square root.

intremainderUnsigned( intdividend, intdivisor )
longremainderUnsigned( longdividend, longdivisor )

Returns the unsigned remainder from dividing the first argument by the second where each argument and the result is interpreted as an unsigned value.

This method is an optimized version of Integer/Long.remainderUnsigned.

intdivideUnsigned( intdividend, intdivisor )
longdivideUnsigned( longdividend, longdivisor )

Returns the unsigned quotient from dividing the first argument by the second where each argument and the result is interpreted as an unsigned value.

This method is an optimized version of Integer/Long.divideUnsigned.

BigUtils

This class contains functions with BigInteger and BigDecimal arguments.

  • Test coverage: 100%
  • Javadoc coverage: 100%

Constants

This class contains additional often used BigInteger (with BI_ prefix) and BigDecimal (with BD_ prefix) constants. BigInteger:

  • 2: BI_TWO
  • 3: BI_THREE
  • 4: BI_FOUR
  • 5: BI_FIVE
  • Integer.MIN_VALUE: BI_MIN_INT = -231
  • Integer.MAX_VALUE: BI_MAX_INT = 231 - 1
  • Long.MIN_VALUE: BI_MIN_LONG = -263
  • Long.MAX_VALUE: BI_MAX_LONG = 263 - 1

BigDecimal:

  • 0.5: BD_HALF
  • 2: BD_TWO
  • 3: BD_THREE
  • 4: BD_FOUR
  • 5: BD_FIVE

Perfect powers (BigUtils)

BigIntegergetBaseOfPerfectSquare( BigIntegern )

Finds a root of a perfect square.

Given integer number n, find integer number s such that s2 = n.

Returns null if such number s doesn't exists.

booleanisPerfectSquare( BigIntegern )

Determine if a given number n is a perfect square.

Common divisors and multiples (BigUtils)

BigIntegerlcm( BigIntegera, BigIntegerb )

Least common multiple (LCM).

booleanisRelativelyPrime( BigIntegera, BigIntegerb )

Determine if a is relatively prime to b, i.e. gcd( a, b ) = 1.

Roots (BigUtils)

BigIntegerisqrt( BigIntegern ) throwsArithmeticException

Returns integer square root of n. Throws exception if n < 0.

Modular arithmetic (BigUtils)

BigIntegermod( BigIntegerv, BigIntegerm ) throwsArithmeticException

Returns v (mod m). The value returned lies in range [ 0 .. |m| - 1 ].

This method differs from BigInteger.mod in that it supports negative modulus (like primitive-type remainder): mod( x, m ) = mod( x, -m ).

If m = 0 then ArithmeticException is thrown.

BigIntegermods( BigIntegerv, BigIntegerm ) throwsArithmeticException

Signed mod. The value returned lies in range [ -( |m| - 1 ) / 2 .. |m| / 2 ].

If m = 0 then ArithmeticException is thrown.

PrimeUtils

This class contains functions for primality testing and proving.

  • Test coverage: 100%
  • Javadoc coverage: 100%

booleanisPrime( longn )
booleanisPrime( BigIntegern )

Deterministic primality test. Polynomial time (compared to the length of n).

  • Negative number n is considered (by methods of this class) prime if -n is prime.
  • Numbers 0 and 1 aren't prime.
  • n is prime if its only divisors are 1 and n itself. Otherwise n is composite.

For performance reasons, BigInteger version uses Baillie-PSW test (for now) which isn't deterministic though no composite numbers were found yet that pass this test. So it's almost deterministic but would be replaced in future by some deterministic test.

booleanisGaussianPrime( longreal, longimaginary )
booleanisGaussianPrime( BigIntegerreal, BigIntegerimaginary )

Gaussian integer primality test.

Gaussian integer is a complex number whose real and imaginary parts are both integers. Prime gaussian number is a gaussian non-zero integer that has no divisors except the trivial ones.

Divisors of 1 are: 1, -1, i and -i. Trivial divisors of n are divisors of 1 and their multiplications by n.

booleanisMersenneNumber( BigIntegern )

Method to check if a given number is a Mersenne number (primality of the number is not checked). Linear time.

booleanisMersennePrime( BigIntegern )

Mersenne numbers deterministic primality test (Mersenne number is an integer in the form Mp = 2p - 1). Polynomial time.

booleanisFermatNumber( BigIntegern )

Method to check if a given number is a Fermat number. Linear time.

booleanisFermatPrime( BigIntegern )

Fermat number deterministic primality test (Fermat number is an integer in the form Fn = 22^n + 1). Constant time.

booleanpassesTrialDivision( longn )
booleanpassesTrialDivision( BigIntegern )

Trial division deterministic test. Exponential time.

booleanpassesLucasLehmer( BigIntegern )

Lucas-Lehmer deterministic primality test for Mersenne numbers. Polynomial time.

Argument n must be a Mersenne number. Use isMersenneNumber function to determine if it is.

booleanpassesLucasPseudoprime( BigIntegern )

Lucas probabilistic primality test. Polynomial time. Not to be confused with Lucas test.

If a number fails this test then it's definitely composite. Otherwise it's probably prime.

Argument n must be an odd integer greater than one, not a strong pseudoprime to base 2, not a perfect square.

passesMillerRabin - probabilistic Miller-Rabin primality test. Polynomial time.

If a number fails this test then it's definitely composite. Otherwise it's probably prime.

booleanpassesMillerRabin( intn, intbase )
booleanpassesMillerRabin( BigIntegern, BigIntegerbase )

Strong pseudoprimality test with a given base.

Argument n must be an odd integer greater than one. Argument base must be relatively prime to n.

This method is an adaptation of the standard Java method BigInteger.passesMillerRabin.

The difference is that the base is defined as an argument and is not generated randomly.

booleanpassesMillerRabin( BigIntegern )

This method tests n pseudoprimality against several random bases. It's similar to BigInteger.isProbablePrime with maximal certainty.

This test does not rely on Riemann hypothesis (GRH).

passesMiller - deterministic Miller primality test. Polynomial time.

booleanpassesMiller( longn )

This method tests n pseudoprimality against several predefined bases. It's verified to be correct and does not rely on GRH.

booleanpassesMiller( BigIntegern )

This method relies on generalized Riemann hypothesis (GRH) which is not proved yet.

booleanpassesBailliePSW( BigIntegern )

Probabilistic Baillie-Pomerance-Selfridge-Wagstaff primality test. Polynomial time.

If a number fails this test then it's definitely composite. Otherwise it's probably prime.

There are no composite numbers found that pass this test yet. All numbers in long range are verified.

PrimesIterable

Prime numbers sequence generator.

  • Test coverage: 100%
  • Javadoc coverage: 100%

PrimesIterable< Integer > getIntegerTotally( intquantity )
PrimesIterable< Long > getLongTotally( longquantity )
PrimesIterable< BigInteger > getBigIntegerTotally( BigIntegerquantity ) throwsIllegalArgumentException

Generate a sequence of BigInteger prime numbers.

A sequence is generated lazily (next number is calculated only if required).

The resulting sequence would contain exactly quantity numbers.

The result can be enumerated in a for-loop construction, e.g.:

for ( BigIntegerbi : getBigIntegerTotally( BigInteger.valueOf( 5 ) ) ) System.out.println( bi );

The output of this example would contain 5 numbers: 2, 3, 5, 7, 11.

An exception is thrown if quantity is null.

PrimesIterable< Integer > getIntegerMax( intmax )
PrimesIterable< Long > getLongMax( longmax )
PrimesIterable< BigInteger > getBigIntegerMax( BigIntegermax ) throwsIllegalArgumentException

Generate a sequence of long prime numbers up to max value inclusively.

A sequence is generated lazily (next number is calculated only if required).

All the numbers in a resulting sequence would lie in range [ 2 .. max ] (both sides included).

The result can be enumerated in a for-loop construction, e.g.:

for ( longl : getLongMax( 5L ) ) System.out.println( l );

The output of this example would contain 3 numbers: 2, 3, 5.

intgetNext( intn )
longgetNext( longn )
BigIntegergetNext( BigIntegern )

Seeking of the next prime number that is greater than or equal to n.

  • For negative n, -getNext( -n ) is returned.
  • If n is null then null is returned.

Examples: getNext( 7 ) = 7, getNext( 9 ) = 11.

About

Math utilities

Resources

Readme
License
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

Packages

Used by

Contributors

Languages