Answers to: BigInteger Arithmetichttps://discuss.codechef.com/questions/15579/biginteger-arithmetic<p>Performing arithmetic operations on BigInteger/BigDecimal tends to slow down drastically as the value increases</p>
<p>The alternative to using BigInteger/BigDecimal arithmetic comes down to using string type data with self implemented methods for each arithmetic operation !</p>
<p>Will it be faster compared to BigInteger/BigDecimal arithmetic or is it slower ??</p>
<p>Also it'll be helpful if any other alternative is shared</p>
<p>(p.s this is in context with JAVA)</p>enFri, 13 Jan 2017 09:25:18 +0530Answer by rajarshi_basuhttps://discuss.codechef.com/questions/15579/biginteger-arithmetic/90149<p>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.</p>rajarshi_basuFri, 13 Jan 2017 09:25:18 +0530https://discuss.codechef.com/questions/15579/biginteger-arithmetic/90149Answer by gkcshttps://discuss.codechef.com/questions/15579/biginteger-arithmetic/90133<p>Hi <a href="/users/6250/mecodesta">@mecodesta</a>,
To elaborate on what <a href="/users/2057/kuruma">@kuruma</a> mentioned, there are optimisations in the Java BigInteger library for multiplication(Toom Cook) and modulo(Chinese Remainder) operations. </p>
<p>There are only two places where your program using BigIntegers may need optimisation:</p>
<p>1) Multiplication in n*log(n) time. You need to use the FFT algorithm here.</p>
<p>2) The BigInteger objects are immutable. Any operation you make on this object will give you a <strong>new</strong> object with the result. This does take a lot of time, especially if you are performing lots of intermediate operations.</p>
<p>To the rescue comes <a href="http://www.docjar.com/docs/api/java/math/MutableBigInteger.html">MutableBigInteger</a>. It doesn't create too many new objects and hence you can save on time and space using this class.</p>
<p>If you want to know more about BigIntegers, check out this <a href="http://www.youtube.com/watch?v=UD8rCe_QVOE">tutorial</a> or the <a href="https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html">JavaDoc</a>. </p>
<p>Cheers!</p>gkcsThu, 12 Jan 2017 16:04:14 +0530https://discuss.codechef.com/questions/15579/biginteger-arithmetic/90133Answer by kurumahttps://discuss.codechef.com/questions/15579/biginteger-arithmetic/15582<p>Hello,</p>
<p>I believe that the Java implementation does a few tricks that can possibly optimize some calculations versus implementing your own operations...</p>
<p>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... :)</p>
<p>You can read more here: <a href="http://www.docjar.com/html/api/java/math/BigDecimal.java.html">Java BigInteger implementation</a> :)</p>
<p>Also, don't do extra work and implement them on your own in Java when you have better, error-free libraries ready to use :D Or at least, don't do it unless strictly required :)</p>
<p>Best regards,</p>
<p>Bruno</p>kurumaWed, 26 Jun 2013 13:38:14 +0530https://discuss.codechef.com/questions/15579/biginteger-arithmetic/15582