You are not logged in. Please login at www.codechef.com to post your questions!

×

BigInteger Arithmetic

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)

asked 26 Jun '13, 13:21

mecodesta's gravatar image

4★mecodesta
364151827
accept rate: 0%

edited 26 Jun '13, 13:22


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... :)

You can read more here: Java BigInteger implementation :)

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 :)

Best regards,

Bruno

link

answered 26 Jun '13, 13:38

kuruma's gravatar image

2★kuruma
17.1k72143208
accept rate: 8%

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!

link

answered 12 Jan, 16:04

gkcs's gravatar image

5★gkcs
1.6k1922
accept rate: 13%

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.

link

answered 13 Jan, 09:25

rajarshi_basu's gravatar image

4★rajarshi_basu
3095
accept rate: 10%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×838
×56
×52
×2

Asked: 26 Jun '13, 13:21

Seen: 4,231 times

Last updated: 13 Jan, 09:25