Efficient parsing and serialization of BigInt from/to String of base 10 representation

[eobermuhlner]

Efficient parsing and serialization of BigInt from/to String of base 10 representation

[eobermuhlner]

I have a first version of toBigDecimal(String) committed.

[plokhotnyuk]

And finally, PRs with using of your idea for BigInt and BigDecimal where I got O(n^1.5) complexity for numbers that are greater than 10000.

Thank you, a lot!

[plokhotnyuk]

Ups... JDK 8/11 already use it for toString and the complexity measured by benchmarks looks like O(n*sqrt(n))... So feel free to close the issue if the approach is not applicable for parsing of BigInt which still has O(n^2) complexity for numbers with n=10000 and above.

[eobermuhlner]

Thanks for the hint.

My measurements show that at least the BigDecimal(String) constructor is O(n^2) so I will implement a split recursive version.
First experiments have been promising but I will need to get all the parsing details right.

[plokhotnyuk]

Eric, what a great work!

Will you grant to adopt key part of your solution in jsoniter-scala parser for BigDecimal?

[eobermuhlner]

Sure - go ahead an use the code. The big-math library is published with MIT license and it allows this. I am still fiddling with the code to see whether I can make it cleaner/faster but in a few days it should be stable.

…

On Thu, Mar 14, 2019 at 10:11 AM Andriy Plokhotnyuk < ***@***.***> wrote: Eric, what a great work! Will you grant to adopt key part of your solution in jsoniter-scala parser for BigDecimal <https://github.com/plokhotnyuk/jsoniter-scala/blob/master/jsoniter-scala-core/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/core/JsonReader.scala#L1388-L1466> ? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#30 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADAyMX0pazPAJBaONfgEkzauMsinCe0Xks5vWhI3gaJpZM4bqCM1> .

[plokhotnyuk]

Another idea for optimization of parsing of java.math.BigDecimal values would be taking into account a math context to avoid calculation of the lower part which will be rounded off.

Yeah, for general case it is a crazy idea, but it would worth for the most used HALF_EVEN rounding mode.

[eobermuhlner]

I agree.

…

On Thu, Mar 14, 2019 at 6:55 PM Andriy Plokhotnyuk ***@***.***> wrote: Another idea for optimization of parsing of java.math.BigDecimal would be taking in account math context to avoid calculation of lower part which will be rounded off. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#30 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADAyMZgI0rB2_f2h-YE4YWfDKhg1IkBDks5vWo0ggaJpZM4bqCM1> .

[plokhotnyuk]

Here is a PR with ~2x times faster parsing of BigInteger values. The algorithm still has O(n^2) complexity, just a redundant nested loop for the addition was removed.

[plokhotnyuk]

But we still have a chance to move closer to the theoretical limit using one of proposed method for the integer multiplication in time O(n log n) [pdf] https://t.co/IltaboOoUq

[plokhotnyuk]

Also, using of BigDecimal.valueOf gives more than 25% increase for parsing speed of small (up to 128 bits) BigInteger values