Kotlin MP BigNum library
Kotlin Multiplatform BigNum library is a pure kotlin implementation of arbitrary precision arithmetic operations. It follows the same approach as Kotlin does on JVM to keep the interface familiar.
Notes & Roadmap
This is an implementation of pure kotlin arbitrary integer and floating-point arithmetic support.
The APIs might change until v1.0
Version 0.3.0 brings API changes to BigDecimal API see changelog for full list.
Also, there is a plan to implement platform native versions.
Testing to verify that the library works properly is mostly done against Java BigInteger and BigDecimal implementations.
Should I use this in production?
The library is still under development, but at the moment it is feature complete, further improvements will be optimizations and bug-fixing.
Integration
Gradle
implementation("com.ionspin.kotlin:bignum:0.3.3")
Snapshot builds
repositories {
maven {
url = uri("https://oss.sonatype.org/content/repositories/snapshots")
}
}
implementation("com.ionspin.kotlin:bignum:0.3.4-SNAPSHOT")
Serialization
Serializers for KotlinX Serializtion library are provided, see more here kotlinx serialization support
Note that because kotlinx doesn't support linux ARM targets as well as MinGW x86, serialization support library doesn't either. Additionally, because of a bug when building serialization support library only JS IR variant is provided.
Usage
Integers
Creating Big Integers
To create a big integer you can parse a string:
BigInteger.parse("-1122334455667788990011223344556677889900", 10)
Or use the extensions or companion function for Long
, Int
, Byte
or Short
val bigIntegerExtension = 234L.toBigInteger()
val bigIntegerCompanion = BigInteger.fromLong(234L)
Or use extensions functions for String
"12345678".toBigInteger()
Basic Arithmetic Operations
Addition
val a = BigInteger.fromLong(Long.MAX_VALUE)
val b = BigInteger.fromInt(Integer.MAX_VALUE)
val sum = a + b
println("Sum: $sum")
----- Output -----
Sum: Sum: 9223372039002259454
Subtraction
val a = BigInteger.fromLong(Long.MIN_VALUE)
val b = BigInteger.fromLong(Long.MAX_VALUE)
val difference = a - b
println("Difference: $difference")
----- Output -----
Difference: -18446744073709551615
Multiplication
val a = BigInteger.fromLong(Long.MAX_VALUE)
val b = BigInteger.fromLong(Long.MIN_VALUE)
val product = a * b
println("Product: $product")
----- Output -----
Product: -85070591730234615856620279821087277056
Division - Quotient
val a = BigInteger.fromLong(Long.MAX_VALUE)
val b = BigInteger.fromInt(Int.MAX_VALUE)
val dividend = a + b
val divisor = BigInteger.fromLong(Long.MAX_VALUE)
val quotient = dividend / divisor
println("Quotient: $quotient")
----- Output -----
Quotient: 1
Division - Remainder
val a = BigInteger.fromLong(Long.MAX_VALUE)
val b = BigInteger.fromInt(Int.MAX_VALUE)
val dividend = a + b
val divisor = BigInteger.fromLong(Long.MAX_VALUE)
val remainder = dividend % divisor
println("Remainder: $remainder")
----- Output -----
Remainder: 2147483647
Division - Quotient and Remainder
val a = BigInteger.fromLong(Long.MAX_VALUE)
val b = BigInteger.fromInt(Int.MAX_VALUE)
val dividend = a + b
val divisor = BigInteger.fromLong(Long.MAX_VALUE)
val quotientAndRemainder = dividend divrem divisor
println("Quotient: ${quotientAndRemainder.quotient} \nRemainder: ${quotientAndRemainder.remainder}")
----- Output -----
Quotient: 1
Remainder: 2147483647
Bitwise Operations
Shift Left
val a = BigInteger.fromByte(1)
val shifted = a shl 215
println("Shifted: $shifted")
----- Output -----
Shifted: 52656145834278593348959013841835216159447547700274555627155488768
Shift Right
val a = BigInteger.parseString("100000000000000000000000000000000", 10)
val shifted = a shr 90
----- Output -----
Shifted: 80779
Xor
val operand = BigInteger.parseString("11110000", 2)
val mask = BigInteger.parseString("00111100", 2)
val xorResult = operand xor mask
println("Xor result: ${xorResult.toString(2)}")
----- Output -----
Xor result: 11001100
And
val operand = BigInteger.parseString("FFFFFFFFFF000000000000", 16)
val mask = BigInteger.parseString("00000000FFFF0000000000", 16)
val andResult = operand and mask
println("And result: ${andResult.toString(16)}")
----- Output -----
And result: ff000000000000
Or
val operand = BigInteger.parseString("FFFFFFFFFF000000000000", 16)
val mask = BigInteger.parseString("00000000FFFF0000000000", 16)
val orResult = operand or mask
println("Or result: ${orResult.toString(16)}")
----- Output -----
Or result: ffffffffffff0000000000
Binary Not
Unlike Java BigInteger which does two's complement inversion, this method does bitwise inversion,
i.e.:
If the number was "1100" binary, not() returns "0011" => "11" => 4 in base 10
In the same case Java BigInteger would return "1011" => -13 two's complement base 10
val operand = BigInteger.parseString("11110000", 2)
val result = operand.not()
println("Not operation result: ${result.toString(2)}")
----- Output -----
Inv result: 1111
Modular integers
A modInverse
function that is equivalent to java BigInteger modInverse
is available. Note that this method will produce a BigInteger not a ModularBigInteger
Big integers can be converted to modularIntegers with same modulo, and then inverse()
method is available. This method will return ModularBigInteger
val a = 100_002.toBigInteger()
val modularA = a.toModularBigInteger(500.toBigInteger())
println("ModularBigInteger: ${modularA.toStringWithModulo()}")
----- Output -----
ModularBigInteger: 2 mod 500
If you want to create more ModularBigIntegers with the same module, you can retrieve creator by calling getCreator
More inforamtion about the ModularBigIntegers can be found in the third section
Floating Point
Creating
Parsing
To create a BigDecimal you can parse a string in expanded or scientific notation
Scientific
val bigDecimal = BigDecimal.parseString("1.23E-6)")
println("BigDecimal: $bigDecimal")
----- Output -----
BigDecimal: 1.23E-6
Expanded
val bigDecimal = BigDecimal.parseString("0.00000123")
println("BigDecimal: $bigDecimal")
----- Output -----
BigDecimal: 1.23E-6
From Long, Int, Short, Byte
You can convert standard types to BigDecimal, i.e. Long
val bigDecimal = BigDecimal.fromLong(7111)
println("BigDecimal: $bigDecimal")
----- Output -----
BigDecimal: 7.111E+3
Or you can specify an exponent. when you do specify an exponent, input value (long, int, short, byte) is considered to be in scientific notation.
val bigDecimal = BigDecimal.fromLongWithExponent(1, -5L)
println("BigDecimal: $bigDecimal")
println("BigDecimalExpanded: ${bigDecimal.toStringExpanded()}")
----- Output -----
BigDecimal: 1.0E-5
BigDecimalExpanded: 0.00001
Extension functions
For String
val bigDecimal = "12345678.123".toBigInteger
Or for Double
of Float
val bigDecimalFromFloat = 123.456f.toBigDecimal()
val bigDecimalFromDouble = 123.456.toBigDecimal()
Long
, Int
, Short
, Byte
val bigDecimalFromLong = 10.toLong().toBigDecimal()
val bigDecimalFromInt = 10.toInt().toBigDecimal()
val bigDecimalFromShort = 10.toShort().toBigDecimal()
val bigDecimalFromByte = 10.toByte().toBigDecimal()
toString
By default toString() is returned in scientific output, but expanded output is also available
val bigDecimal = BigDecimal.parseString("123.456")
println("BigDecimal: ${bigDecimal.toStringExpanded()}")
bigDecimal.toStringExpanded() == "123.456"
----- Output -----
BigDecimal: 123.456
toByteArray and fromByteArray
Converts the BigInteger to and from big endian byte array.
val bigIntOriginal = BigInteger.fromULong(ULong.MAX_VALUE)
val byteArray = bigIntOriginal.toByteArray()
val reconstructed = BigInteger.fromByteArray(byteArray)
println("${bigIntOriginal == reconstructed}")
----- Output -----
true
There are two helper methods when converting from two's complement array (the same form that Java BigInteger provides):
fromTwosComplementByteArray
val negativeInput = ubyteArrayOf(0xFFU, 0x55U, 0x44U, 0x34U)
val negativeBigInt = BigInteger.fromTwosComplementByteArray(negativeInput.asByteArray())
toTwosComplementByteArray
val negativeBigInt = BigInteger.parseString("-AABBCC", 16)
val negativeBigIntArray = negativeBigInt.toTwosComplementByteArray()
Arithmetic operations
Standard arithmetic operations that are present:
- Addition
- Subtraction
- Multiplication
- Division
- Exponentiation
- Increase by one
- Decrease by one
- Absolute value
- Negate
- Signum
(Suspiciously missing is square root, should be added soon™)
Operations are executed with existing significands and then rounded down afterwards. Decimal mode parameter controls the precision and rounding mode
DecimalMode
This is a counterpart to the Java BigDecimal MathContext and scale at the same time. Decimal mode API is under revision and will be improved during 0.3.0-0.4.0 library lifecycle
data class DecimalMode(val decimalPrecision : Long = 0, val roundingMode : RoundingMode = RoundingMode.NONE, val scale: Long = -1)
decimalPrecision
defines how many digits should significand have
roundingMode
defines rounding mode.
Decimal mode resolution
-
DecimalMode
supplied to the operation always overrides all otherDecimalModes
set inBigDecimal
s -
If a
DecimalMode
is set when creating aBigDecimal
that mode will be used for all operations. -
If two
BigDecimal
s have differentDecimalModes
with different RoundingModes anArithmeticException
will be thrown. If the modes are same, but the precision is different, larger precision will be used.
Scale
Scale, or the number of digits to the right of the decimal, can also be specified. Default is no scale, which puts no restriction on number of digits to the right of the decimal. When scale is specified, a RoundingMode
other than RoundingMode.NONE
is also required. When arithmetic operations have both operands unlimited precision and no scaling, the result is also unlimited precision and no scale. When an operation mixes an unlimited precision operand and a scaled operand, the result is unlimited precision. WHen both operands have scale, whether unlimited precision or limited precision, then these rules for scale of the result are used:
- add, subtract - max of the two scales
- multiply - sum of the two scales
- divide - min of the two scales
Infinite precision
Precision 0 and roundingMode none attempt to provide infinite precisions. Exception is division (and exponentiation with negative parameter), where default precision is the sum of precisions of operands (or 6, if the sum is below 6). If result of the operation cannot fit inside precision and RoundingMode is NONE, ArithmeticException
will be thrown.
Example from the tests:
fun readmeDivisionTest() {
assertFailsWith(ArithmeticException::class) {
val a = 1.toBigDecimal()
val b = 3.toBigDecimal()
val result = a/b
}
assertTrue {
val a = 1.toBigDecimal()
val b = 3.toBigDecimal()
val result = a.div(b, DecimalMode(20, RoundingMode.ROUND_HALF_AWAY_FROM_ZERO))
result.toString() == "3.3333333333333333333E-1"
}
}
Convenience rounding methods
BigDecimal
class contains two convenience rounding methods, the roundToDigitPositionAfterDecimalPoint(digitPosition: Long, roundingMode: RoundingMode)
which rounds to a specific position after the decimal point, like in the following example:
assertTrue {
val rounded = BigDecimal.fromIntWithExponent(123456789, 3)
.roundToDigitPositionAfterDecimalPoint(3, RoundingMode.CEILING)
rounded.toStringExpanded() == "1234.568"
}
and roundToDigitPosition(digitPosition: Long, roundingMode: RoundingMode)
which rounds to a specifi digit precision regardless of decimal point, like in the following example:
assertTrue {
val rounded = BigDecimal.parseString("1234.5678")
.roundToDigitPosition(3, RoundingMode.ROUND_HALF_TOWARDS_ZERO)
rounded.toStringExpanded() == "1230"
}
assertTrue {
val rounded = BigDecimal.parseString("0.0012345678")
.roundToDigitPosition(4, RoundingMode.ROUND_HALF_TOWARDS_ZERO)
rounded.toStringExpanded() == "0.001"
}
Rounding modes
Name | Description |
---|---|
FLOOR | Towards negative infinity |
CEILING | Towards positive infinity |
AWAY_FROM_ZERO | Away from zero |
TOWARDS_ZERO | Towards zero |
NONE | Infinite decimalPrecision, and beyond |
ROUND_HALF_AWAY_FROM_ZERO | Round towards nearest integer, using towards zero as tie breaker when significant digit being rounded is 5 |
ROUND_HALF_TOWARDS_ZERO | Round towards nearest integer, using away from zero as tie breaker when significant digit being rounded is 5 |
ROUND_HALF_CEILING | Round towards nearest integer, using towards infinity as tie breaker when significant digit being rounded is 5 |
ROUND_HALF_FLOOR | Round towards nearest integer, using towards negative infinity as tie breaker when significant digit being rounded is 5 |
Modular Integers
Modular arithmetic operations are supported only between integers with the same modulo.
Creating Modular Integers
First define the modulo you are going to use by getting an instance of the creator, and than use that creator to create instances of modular integers
val creator = ModularBigInteger.creatorForModulo(100)
val modularBigInteger = creator.fromLong(150)
println("ModularBigInteger: ${modularBigInteger.toStringWithModulo()}")
----- Output -----
ModularBigInteger: 50 mod 100
Otherwise behavior is similar to normal integers
Sources
For examples of rounding modes consult Comparison of approaches for rounding to an integer on Wikipedia
This library draws inspiration from libraries like Java BigInteger, GNU MP Arithmetic Library, Javolution JScience, as well as following literature
Modern Computer Arithmetic
Richard P. Brent and Paul Zimmermann
Version 0.5.9 of 7 October 2010
Hacker`s Delight
Henry S. Warren, Jr.
Second Edition
Art of Computer Programming, Volume 2: Seminumerical Algorithms
Donald E. Knuth
3rd Edition
Refinement of a newton reciprocal algorithm for arbitrary precision numbers
Yiping Cheng, Ze Liu
And many other blogs and posts scattered over the internet.
If you want to try building BigNum library yourself, those are the sources I would recommend to start with.
Development environment
If you are planning on contributing to the development of the library, you can set a local gradle variable in gradle.properties
in your gradle home directory (i.e. on Linux ~/.gradle/gradle.properties) called bignumPrimaryDevelopmentOs
to linux
, windows
or mac
so that the gradle builds JVM and JS targets on your platform. The reason for this switch is that most of the test are run on JVM by comparing results to Java BigInteger/Decimal so they should be run on your main development OS to verify proper results, and can be skipped on other operating systems where you are developing that platform specific features.
And thank you for contributing!