BigInteger Arithmetic

general
, , ,
1

Performing arithmetic operations on BigInteger/BigDecimal tends to slow down drastically as the value increases

The alternative to using BigInteger/BigDecimal arithmetic comes down to using string type data with self implemented methods for each arithmetic operation !

Will it be faster compared to BigInteger/BigDecimal arithmetic or is it slower ??

Also it’ll be helpful if any other alternative is shared

(p.s this is in context with JAVA)

2

Hello,

I believe that the Java implementation does a few tricks that can possibly optimize some calculations versus implementing your own operations…

There are some fast algorithms based on FFT to do multiplications in supra-linear time I guess, but, other than that, I guess it’s up to what you need… :slight_smile:

You can read more here: Java BigInteger implementation :slight_smile:

Also, don’t do extra work and implement them on your own in Java when you have better, error-free libraries ready to use :smiley: Or at least, don’t do it unless strictly required :slight_smile:

Best regards,

Bruno

1 Like
3

Hi @mecodesta,
To elaborate on what @kuruma mentioned, there are optimisations in the Java BigInteger library for multiplication(Toom Cook) and modulo(Chinese Remainder) operations.

There are only two places where your program using BigIntegers may need optimisation:

  1. Multiplication in n*log(n) time. You need to use the FFT algorithm here.

  2. The BigInteger objects are immutable. Any operation you make on this object will give you a new object with the result. This does take a lot of time, especially if you are performing lots of intermediate operations.

To the rescue comes MutableBigInteger. It doesn’t create too many new objects and hence you can save on time and space using this class.

If you want to know more about BigIntegers, check out this tutorial or the JavaDoc.

Cheers!

4

You should not try using string to store numbers and then using them for your operations.Firstly, it will be a lot of work to debug, and secondly, the BigInteger and BigDecimal have the fastest implementations already and they are error-free. So I think that if you feel that you are needing something more efficient than BigInteger, you should definitely check whether your algorithm is efficient.