BigInt#divRem using O(n²) algorithm?

[janvanoort]

The divRem( final BigInt div) operation is essentially the arithmetic modulo operation. Two suggestions:

1. rename the method to modulo, for more clarity
2. implement the much simpler subtraction-based Euclidean algorithm, as in

function gcd(a, b)
while a ≠ b
if a > b
a := a − b;
else
b := b − a;
return a;

(See image for Euclid's original source, formulated geometrically as Euclid was wont to do.)
If 2. is decided upon, I am willing to provide an implementation plus a unit test for the implementation plus a perf test comparing it side-by-side to the existing implementation.

[janvanoort]

Of course, we'd need a threshold for detecting cases when subtraction-based gcd is undesirable while taking too long, and switch over to division-based gcd.

[bwakell]

So I think the logic behind the naming was to be somewhat consistent with:
https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#remainder-java.math.BigInteger-
https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#mod-java.math.BigInteger-

I.e. mod() is always non-negative, whereas rem() might be negative. Furthermore, divRem() divides the number and returns the remainder (rem() sets the BigInt to the remainder).

And sure, feel free to implement both mod() and gcd() + tests and benchmarks. :)

(I haven't had time to work/look at the code in a long time, and yeah there's much that needs cleaning up... But one day I might make it my 20% project. ^^)

[bwakell]

So I now actually had a real thought about it and a proper read of Euclid's wise words.

A naive implementation of subtraction based GCD, or a subtraction based way of finding the remainder, has complexity O(N * 2^N), since if the dividend A is large compared to the divisor B, then you can keep subtracting as many times as B fits in A which may be O(2^N). N being the number of bits in the number.

The remedy is obviously to then subtract bigger multiples of B from A in each iteration, and the easiest and most efficient way to create large multiples of B is to simply multiply it by 2 as long as it's < A. Then subtract. Then find the next biggest number B * 2^k <= A and subtract, and rinse and repeat. In the worst case you'll now only make N subtractions (you may need to do one or a comparison for each number B * 2^k, i.e. for each bit), so the total complexity ends up being O(N^2).

And now when I write this, I realize that this must be the so called binary GCD algorithm (whose existence I've heard of but never bothered reading up on).
https://en.wikipedia.org/wiki/Binary_GCD_algorithm

So while binary GCD also takes O(N^2) steps, it's probably faster in practice, since the base operations are all simple/fast (subtractions, bit shifts and comparisons). The "normal" division algorithm involves a bunch of divisions (of ints/longs) which while being O(1) executes slower than subtractions, bit shifts, etc.

[janvanoort]

@bwakell You are completely right, of course. While musing about it, I came to the exact same conclusions over the past 2 days.

There is more that I'm missing in BigInt, e.g. a log() or ln() operation. I'm going to re-assess

1. my need for using BigInt
2. the amount of time I can put into further developing BigInt.

Very glad, however, with the constructive dialog!

[bwakell]

Yeah it's been years since I put any effort into BigInt, and at the end of the day, it was initially just meant as a simple big num implementation supporting the basic operations that you could easily copy+paste and modify for fun.

• If you need to use Java and want to be relatively sure of correctness, then BigInteger is probably the way to go.
• If you just need performance, well then C and GMP is the way to go: https://gmplib.org/
• But if you need/want to use pure Java, and want performance + flexibility, then BigInt is probably the best (or a decent) piece of code to start with. The price you pay is obviously that more complex operations like GCD and LOG are not yet there (you would need to implement them yourself) and that the likelihood of bugs is not negligible.

That said, binary GCD seems relatively easy to implement and could probably be added with not too much effort.

(I also had a look again at the division algorithm used, and it doesn't seem to do too many divisions. So for the purposes of calculating rem()/mod() or even gcd(), I don't think it would be too bad. However, binary GCD is probably still faster in some cases, e.g. as outlined by https://gmplib.org/manual/Binary-GCD.html#Binary-GCD)