Current implementation of BigInteger implementatio...

# mathematics

[Zhelenskiy]

Current implementation of BigInteger implementation and power is slow so I provided it with corresponding tests: PR .

[altavir]

Thanks a lot. I am looking forward to a father algorithm. I will merge the benchmark as soon as possible.

[Zhelenskiy]

Ok, I may implement the algorithms too but I am completely not sure about the deadline though as I am studying at the moment.

[Zhelenskiy]

In the messages I said that I increased number a bit and the result became even worse. That is consequence of bad asymptotic, so further increasing leads to further increasing of difference. But the goo implementation must be a lot faster than java's as it uses Karatsuba algorithm that is faster than the current KMath's naive one but is a lot slower than FFT based ones (like in haskell).

[altavir]

I am not sure if there are use cases for precise ariphmetics with such large numbers. But contributions are welcome in any case.

[altavir]

I've merged benchmark with some not quite correct changes. The problem is that KM BigInt does not support pow operation, so I am not sure that any measurements with it are correct. By the way, on GraalVM, basic add and multiply seems to be much faster on KM than on JVM

[altavir]

Or not... at least it is similar

[altavir]

Large number multiplication seems to consistent with your tests

[altavir]

In order to make comparison for power valid, one need to implement power in a non-recursive way.

[Zhelenskiy]

Of course, it must. That no recursive algorithm works for all rings.

[Zhelenskiy]

I was quite surprised by having naive implementation for power in the corresponding file. I'll fix it.

[altavir]

The one you used leaked from one of @breandan projects used for testing. It is not available in kmath-core

[altavir]

I fixed the base in dev, but it is still too slow

[Zhelenskiy]

Oh, ok

[altavir]

🤷‍♂️ had only like 10 minutes before going to a lecture.

[breandan]

Happy to replace it with KMath when it's ready or another alternative you have in mind, I was also in a rush at the time and kotlin-big-math was the only implementation I could find that supported trigonometric functions on BigDecimal

[altavir]

Indeed. I personally do not have use cases for big math. The current code was a contribution. We planned to replace it with Erics solution, but we found that KMath implementation by Robert is much faster.

[Zhelenskiy]

What is the better place for power operation? I assume it to be an extension to Ring as fast power uses associativity of multiplication.

[Zhelenskiy]

Also, I think that power that are outside ULong are practically useless but lead to overhead. Negative, negative powers are now forbidden.

[Zhelenskiy]

BigInt cannot implement PowerOperations as root cannot be defined and non-natural (or 0) powers are forbidden for it.

[altavir]

I do not have any specific opinion on this since I do not know the use-cases for BigInt.

[Zhelenskiy]

(Java's BigInt allows `int`s as exponent, by the way)

[Zhelenskiy]

(Added pow to my fork)

[Zhelenskiy]

Added Karatsuba: https://github.com/mipt-npm/kmath/pull/328