CODEWITHSUNDEEP
javamath
M.J. Rayburn
M.J. Rayburn

Reputation: 519

Java's BigInteger class

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?

Upvotes: 2

Views: 723

Answers (3)

President James K. Polk
President James K. Polk

Reputation: 41956

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.

Upvotes: 1

k_g
k_g

Reputation: 4464

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.

Upvotes: 3

Emil Laine
Emil Laine

Reputation: 42828

It uses int.

Reason: It's the fastest for most platforms.

Upvotes: 0

Related Questions