https://kotlinlang.org logo
z

Zhelenskiy

04/16/2021, 7:19 PM
Current implementation of BigInteger implementation and power is slow so I provided it with corresponding tests: PR .
👍 2
a

altavir

04/16/2021, 7:55 PM
Thanks a lot. I am looking forward to a father algorithm. I will merge the benchmark as soon as possible.
z

Zhelenskiy

04/16/2021, 9:07 PM
Ok, I may implement the algorithms too but I am completely not sure about the deadline though as I am studying at the moment.
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).
a

altavir

04/17/2021, 5:45 AM
I am not sure if there are use cases for precise ariphmetics with such large numbers. But contributions are welcome in any case.
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
Or not... at least it is similar
Large number multiplication seems to consistent with your tests
In order to make comparison for power valid, one need to implement power in a non-recursive way.
z

Zhelenskiy

04/17/2021, 8:16 AM
Of course, it must. That no recursive algorithm works for all rings.
I was quite surprised by having naive implementation for power in the corresponding file. I'll fix it.
a

altavir

04/17/2021, 8:22 AM
The one you used leaked from one of @breandan projects used for testing. It is not available in kmath-core
I fixed the base in dev, but it is still too slow
z

Zhelenskiy

04/17/2021, 8:24 AM
Oh, ok
a

altavir

04/17/2021, 8:25 AM
🤷‍♂️ had only like 10 minutes before going to a lecture.
b

breandan

04/18/2021, 2:23 AM
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
a

altavir

04/18/2021, 7:26 AM
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.
👍 1
z

Zhelenskiy

05/10/2021, 1:29 PM
What is the better place for power operation? I assume it to be an extension to Ring as fast power uses associativity of multiplication.
Also, I think that power that are outside ULong are practically useless but lead to overhead. Negative, negative powers are now forbidden.
BigInt cannot implement PowerOperations as root cannot be defined and non-natural (or 0) powers are forbidden for it.
a

altavir

05/10/2021, 1:49 PM
I do not have any specific opinion on this since I do not know the use-cases for BigInt.
z

Zhelenskiy

05/10/2021, 2:01 PM
(Java's BigInt allows `int`s as exponent, by the way)
(Added
pow
to my fork)
4 Views