6

I'm importing a large text file, 17 million digits long and I'm using this code:

BufferedReader reader = new BufferedReader(new FileReader("test2.txt"));
String line = reader.readLine();
System.out.println("Done");
BigInteger num = new BigInteger(line);
System.out.println("Done Again");

It loads the file pretty much instantly and prints out 'Done' but it takes a long time (about an hour) for the String to be converted into a BigInteger, is there anything I can do to speed this up and quickly load the number?

Paulo Mattos
  • 18,845
  • 10
  • 77
  • 85
Samantha Clark
  • 201
  • 2
  • 9
  • 3
    Well, there's not much room to work with the code you posted. If you explain what you're trying to do with the number, maybe we can work on an alternative solution. – shmosel May 16 '17 at 23:34
  • suppose the code you shared is not adequate to find the issue. Have referred this [post](http://stackoverflow.com/questions/15717240/string-to-biginteger-java) on `String` to `BigInteger`. – Rajith Pemabandu May 16 '17 at 23:37
  • 1
    A number with 17 million digits will take a long time to parse... – Óscar López May 16 '17 at 23:38
  • 2
    All I need to do is load a single huge number from a text file, then turn it into a BigInteger. I provided this code because using it I can see that the file itself loads almost instantaneously but turning it into a BigInteger takes a lot of time – Samantha Clark May 16 '17 at 23:39
  • Rajith Pemabandu - I'm already using the BigInteger = new BigInteger(String) method – Samantha Clark May 16 '17 at 23:42
  • 3
    @SamanthaClark The code is very slow because it's a massive number. Does that answer your question? – shmosel May 16 '17 at 23:48
  • Yes, is there a way to make it faster though? I hope there is but since it's something so basic as turning a string to a BigInteger I'm worried there isn't – Samantha Clark May 16 '17 at 23:56
  • What do you do with the BigInteger after you have loaded it? – Samuel May 16 '17 at 23:56
  • I use it in a mod function BigInteger.mod(N). Also I just realized alternatively is there a way that the number could just be saved in eclipse instead of loading it? I thought the only way to save a variable was by exporting it to a file – Samantha Clark May 17 '17 at 00:01
  • Like I said, there's very little you can do with the code provided. There's no magic switch that will speed up the `BigInteger` parse algorithm. But there *may* be some other way of achieving your end goal. But you would need to include more context in your post. – shmosel May 17 '17 at 00:07
  • What else should I include? All I need to do is load a txt file then turn it into a BigInteger. I'll try any other methods anyone can think of – Samantha Clark May 17 '17 at 00:09
  • @SamanthaClark In your mod function BigInteger.mod(N), is N also some huge number that cannot be stored in long? – z m May 17 '17 at 00:11
  • Seems to be an [XY Problem](https://meta.stackexchange.com/q/66377/351454). You're trying to boost loading a 17 miliion digit text string into a `BigDecimal`, which is slow, as you've learning. However, in the overall scheme of things, perhaps you don't need to do that, if you change something else, e.g. store the large number in binary form, not text, or maybe use the large number directly as sequence of character digits. You should edit the question and describe the broader scope of what you're trying to do. – Andreas May 17 '17 at 00:21
  • The BigInteger would probably load MUCH faster if it were stored as binary (i.e. as bytes) or if it were stored as text ,but in hex. – Rudy Velthuis May 17 '17 at 08:04

3 Answers3

7

As an optimization, since BigInteger is Serializable, you could save it to a binary file once and speed up your loading considerably.

Loading a serialized object should be way faster than parsing a huge string everytime.

Use ObjectOutputStream to save your big integer and ObjectInputStream to read it back in.

Paulo Mattos
  • 18,845
  • 10
  • 77
  • 85
  • The InputStream and OutputStream work great, thank you very much – Samantha Clark May 17 '17 at 01:06
  • @SamanthaClark Sweet :) Sometimes you need to take a step back and try another approach... – Paulo Mattos May 17 '17 at 01:08
  • Yeah, the issue is I've only started programming a short while ago and I think I've gotten way too deep into it, right now there's a very steep learning curve (yesterday I didn't know how to use BufferedReader and a week before that I couldn't even save a file xD) Basically this site is a Godsend – Samantha Clark May 17 '17 at 01:10
  • Hmm now I just need to figure out how to get the BigInteger from the OutputStream – Samantha Clark May 17 '17 at 01:25
  • ObjectInputStream stream = new ObjectInputStream(new FileInputStream("test.txt")); BigInteger Big = (BigInteger) stream.readObject(); Using that I get an error saying that java.lang.String cannot be cast to java.math.BigInteger at ReadOutPutStream.main – Samantha Clark May 17 '17 at 01:32
  • @SamanthaClark You have to *write* it as an object, not as a `String`, before you can read it as an object. It isn't magic. – user207421 May 17 '17 at 01:38
  • I've never worked with InputStream before, isn't it already an Object? – Samantha Clark May 17 '17 at 01:51
  • 2
    @SamanthaClark You have to write the `BigInteger` object to the file, with `ObjectOutputStream.writeObject()`. Not the `String`. Which of course means you do have to load it *once* from your text representation, via `new BIgInteger(String)`. But thereafter you can deal with it as an object. NB Serialized streams are not text and should not be saved in .txt files. – user207421 May 17 '17 at 02:25
  • What file extension should I use instead of .txt? – Samantha Clark May 17 '17 at 13:07
4

It is slow because new BigInteger(String) is doing radix conversion from decimal to binary, which is O(N2). Nothing you can do about that.

You could save either the object itself, via Serialization, or the byte array it is stored in, via BigInteger.toByteArray(). Either will load essentially instanteously.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • Out of curiosity, what about a multithreaded solution? Split up the parsing in chunks and then merge back the resulting big integers using multiplications and sums? – Paulo Mattos May 17 '17 at 00:28
  • 1
    @PauloMattos See D.E. Knuth, *The Art of Computer Programming,* Volume 2, #4.4.E(c). Not sure it gets you anywhere in terms of speed. – user207421 May 17 '17 at 00:36
0

As the comments have indicated, your code is slow because you're attempting to load a number with a lot of digits.

If you're unsatisfied with the performance of Java's BigInteger implementation, then I suggest you look elsewhere.

This library claims to have a BigInteger that outperforms Java's implementation (note it may not speed up loading the number, but it should improve multiplication and division performance).

Samuel
  • 16,923
  • 6
  • 62
  • 75