4

I'm new here so please excuse my noob mistakes. I'm currently working on a little project of mine that sees me dealing with digits with a length in the forty thousands and beyond.

I'm currently using BigInteger to handle these values, and I need something that performs faster. I've read that BigInteger uses an array of integers in its implementation, and what I need to know is whether BigInteger is using each index in this array to represent each decimal point, as in 1 - 9, or is it using something more efficient.

I ask this because I already have an implementation in mind that uses bit operations, which makes it more efficient, memory and processing wise.

So the final question is - is BigInteger already efficient enough, and should I just rely on that? It would better to know this rather than putting it to the test unnecessarily, which would take a lot of time.

Thank you.

WTRIX
  • 95
  • 1
  • 8
  • 2
    Hard to tell *efficient enough*... You can write an benchmark and make a comparasion. https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java – xingbin Oct 08 '18 at 14:31
  • 4
    You've stated "I need something that performs faster" - is that conjecture on your part, or have you proved that `BigInteger` *isn't* already efficient enough for you? (I strongly suspect that any optimizations you can easily imagine for `BigInteger` are already present. You can check out the implementation yourself though, e.g. at https://hg.openjdk.java.net/jdk/jdk/file/957de5be48bc/src/java.base/share/classes/java/math/BigInteger.java – Jon Skeet Oct 08 '18 at 14:31
  • soooo many applications use `BigInteger`, I doubt even a tiny fraction of them have potential bottle necks because of that – Eugene Oct 08 '18 at 14:36
  • Thanks for the responses everyone. And no I'm not making any assumptions. I just needed to know. Of course I understand that BigInteger is as refined and as sophisticated as they come, but when I read something about an array, it made me think of an old superint class I had made before finding the BigInteger class. I was working on the same project, and I jumped straight into making my own minimal SuperInt, but it was really slow, and I thought up an improvement, but by then I had also found BigInteger. So that's where my curiosity comes in. – WTRIX Oct 08 '18 at 14:48
  • And for anyone wondering what an app would be doing with such digits; right now I'm basically still developing an algorithm rather than an app, and most of my uses of BigInteger are for tests, so to say. – WTRIX Oct 08 '18 at 15:12
  • 1
    In my limited testing I haven't found any pure Java big int implementations that are faster than Java 8+ BigInteger, including third party classes that claim they are faster. Java 8+ BigInteger incorporates advanced algorithms that perform better than O(n^2) for multiplication and division on sufficiently large operands. – President James K. Polk Oct 08 '18 at 17:39
  • Thanks. That's also quite useful. I'll stick with the fastest then. Haha, now I can imagine why one would want to bite my head off for talking about custom implementations. – WTRIX Oct 09 '18 at 18:09

1 Answers1

3

At least with Oracle's Java 8 and OpenJDK 8, it doesn't store one decimal digit per int. It stores full 32-bit portions per 32-bit int in the int[], which can be seen with its source code.

Bit operations are fast for it, since it's a sign-magnitude value and the magnitude is stored packed just as you'd expect, just make sure that you use the relevant BigInteger bitwise methods rather than implementing your own.

If you still need more speed, try something like GMP, though be aware that it uses a LGPL or GPL license. It would also be better to use it outside of Java.

Chai T. Rex
  • 2,972
  • 1
  • 15
  • 33