BigInteger: Replace ==ZERO by isZero.

[glureau]

Replacing == ZERO by isZero()

Motivation

Similar of #301 but for BigInteger. Equals are more costly than testing isZero or isNegative.

Special case

BigInteger.pow(BigInteger) uses exponentiationBySquaring which is now using isZero, but I was not able to reach this code path in my tests. JVM was triggering an OutOfMemory (Java heap space) after 90s of running (my exponent was BigInteger.parse(Long.MAX_VALUE + "1")). I took a shortcut by commenting the call to pow(Long), so that it forces the use of exponentiationBySquaring, and allow me to benchmark with "little" values (1 googol being "little").

Benchmark (JVM)

Best of 3 runs, custom iterations (see benchmark code), JVM, M3 Pro with 36GB RAM, duration in seconds

Method	BEFORE	AFTER	% time reduction
subtract	1.13	1.08	4%
ZERO.subtract()	0.581	0.502	14%
subtract(ZERO)	0.683	0.330	52%
pow* (exp by squaring)	1.10	1.08	2%
modInverse	0.586	0.577	2%
times(Char)	2.27	2.16	5%
pow	0.081	0.070	14%

Benchmark code

    @Test
    fun perfSubtractZero() {
        val bd = BigInteger.parseString("123")
        val duration = measureTime {
            repeat(100_000_000) { bd - BigInteger.ZERO }
        }
        println("subtract(ZERO): $duration")
    }

    @Test
    fun perfZeroSubtract() {
        val bd = BigInteger.parseString("123")
        val duration = measureTime {
            repeat(100_000_000) { BigInteger.ZERO - bd }
        }
        println("ZERO.subtract(): $duration")
    }

    @Test
    fun perfSubtract() {
        val a = BigInteger.parseString("123")
        val b = BigInteger.parseString("34")
        val duration = measureTime {
            repeat(100_000_000) { a - b }
        }
        println("subtract: $duration")
    }

    @Test
    fun perfPowWithExponentiationBySquaring() {
        // Warning, this test has biased value, it should use an exponent > Long.MAX_VALUE to go
        // through exponentiationBySquaring. For benchmarking this test I've commented out the usage of pow(Long)
        val a = BigInteger.parseString("10")
        val b = BigInteger.parseString("100")
        val duration = measureTime {
            repeat(1_000_000) { a.pow(b) }
        }
        println("pow*: $duration")
    }

    @Test
    fun perfPow() {
        // Warning, this test has biased value, it should use an exponent > Long.MAX_VALUE to go
        // through exponentiationBySquaring. For benchmarking this test I've commented out the usage of pow(Long)
        val a = BigInteger.parseString("10")
        val b = BigInteger.parseString("100")
        val duration = measureTime {
            repeat(1_000_000) { a.pow(b) }
        }
        println("pow: $duration")
    }

    @Test
    fun perfModInverse() {
        // 3803 and 3329 are both primes
        val a = BigInteger.parseString("3803")
        val b = BigInteger.parseString("3329")
        val duration = measureTime {
            repeat(1_000_000) { a.modInverse(b) }
        }
        println("modInverse: $duration")
    }

    @Test
    fun perfTimes() {
        val a = BigInteger.parseString("38")
        val duration = measureTime {
            repeat(1_000_000) { a.times('b') }
        }
        println("times(Char): $duration")
    }

Raw data

Before

Run 1 subtract: 1.526356041s ZERO.subtract(): 581.206625ms pow: 1.199554083s subtract(ZERO): 682.647833ms modInverse: 586.281166ms times(Char): 2.274098500s pow: 89.229875ms

Run 2 subtract: 1.380918708s ZERO.subtract(): 621.464125ms pow: 1.098721042s subtract(ZERO): 693.304667ms modInverse: 608.127292ms times(Char): 2.287946833s pow: 83.628250ms

Run 3 subtract: 1.133838833s ZERO.subtract(): 645.497916ms pow: 1.234771250s subtract(ZERO): 687.548750ms modInverse: 649.144083ms times(Char): 2.287897334s pow: 80.517ms

After

Run 1 subtract: 1.078803625s ZERO.subtract(): 536.864958ms pow: 1.128199250s subtract(ZERO): 329.929625ms modInverse: 611.962750ms times(Char): 2.214370791s pow: 79.141750ms

Run 2 subtract: 1.137907458s ZERO.subtract(): 525.679166ms pow: 1.083095208s subtract(ZERO): 544.093ms modInverse: 599.358250ms times(Char): 2.156597666s pow: 86.663125ms

Run 3 subtract: 1.449096584s ZERO.subtract(): 502.667083ms pow: 1.076523292s subtract(ZERO): 393.253875ms modInverse: 574.755417ms times(Char): 2.203168959s pow: 69.521125ms

[ionspin]

Hi @glureau thank you for all the pull requests, they are highly appreciated. I won't have time/access to the repo next couple of weeks, so I'll look into the requests once I get back. Thanks once again!

[glureau]

Thank you for all your work! Great library and nice to have such a good support and response time for an open source project. Enjoy your days off!

PS: I've published a 0.3.10-SNAPSHOT2 on my fork https://github.com/users/glureau/packages?repo_name=kotlin-multiplatform-bignum for my own needs with all the improvements if anyone else is interested to test it, but I recommend to wait a bit more if you can ;)