2

What algorithms does Java's BigInteger class employ for multiplication and division, and what are their respective time complexities?

What primitive type does Java's BigInteger class use - byte, short, int, etc. - and why?

How does Java's BigInteger class handle the fact that its primitive type is signed? If the answer is it just does it and it's really messy, that's all I need/want to know. What I'm really getting at is does it cheat in the same way some python libraries cheat in that they're not written in python?

3

3 Answers 3

3

I looked at the source code to BigInteger here. Here's what I found.

BigInteger does not "cheat". In Java "cheating" is accomplished through the use of what are known as "native" functions. See java.lang.Math for a rather extensive list of these.

BigInteger uses int to represent its data.

private transient int[] words;

And yes, it is pretty messy. Lot's of bit crunching at the like.

1

Oracle's java.math.BigInteger class has undergone some extensive improvements from Java 7 to Java 8. See for yourself by examining the source on grepcode.com. It doesn't cheat, it's all pure java.

Internally, it uses a sign-magnitude representation of the integer, using an array of int values to store the magnitude. Recall that a java int is a 32-bit value. All 32-bits are used without regard to the sign. This size is also convenient since the product of two ints fits into a java long.

Beginning in Java 8 the BigInteger class added some advanced algorithms such as Karatsuba and Toom-Cook multiplication to improve the performance for integers of thousands of bits.

7
  • "used without regard to the sign" - How? By using bit-wise operators instead of arithmetic operators? Mar 2, 2015 at 5:07
  • The operands are converted to long before arithmetic is per performed. You should examine the code to learn more, for example the add method. Mar 2, 2015 at 13:34
  • Thanks ... in retrospect that should have been easily deducible from your answer. Mar 2, 2015 at 17:08
  • "The operands are converted to long before arithmetic is per performed." and "This size is also convenient since the product of two ints fits into a java long." The product of two numbers in the range [0, 2^32) doesn't fit into a long. May 7, 2015 at 1:34
  • @M.J.Rayburn: A java long is 64-bits. The product of two 32-bit integers is an integer whose magnitude is < 2*64, therefore it fits in a long. May 7, 2015 at 1:43
0

It uses int.

Reason: It's the fastest for most platforms.

7
  • If two ints are faster than a long why do longs exist? Mar 1, 2015 at 20:02
  • @M.J.Rayburn A long is essentially just two ints (double the size in bits). Of course a single variable is faster than two variables. 32 bits is the natural size for many PC architectures, that's why Java uses that size for it's ints.
    – Emil Laine
    Mar 1, 2015 at 20:07
  • When I said "why do longs exist" I meant "why do processors have built in support for longs". Are you saying I'm wrong about that, and ints are the biggest integral types with native support? Mar 2, 2015 at 0:37
  • Longs exist to allow representation of 64-bit wide integers with a single variable. Most systems have good native support for them, and it's a good feature, there are many cases when 32 bits just aren't enough.
    – Emil Laine
    Mar 2, 2015 at 1:10
  • You misunderstand. If it's more time efficient to represent a 64 bit BigInt as two ints instead of one long, why do most processors have built in support for longs - it would be faster to implement them in software. Mar 2, 2015 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.