-
-
Notifications
You must be signed in to change notification settings - Fork 2.1k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Bignum operations should be optimized #21479
Comments
I think karatsuba algorithm has been implented ... see https://github.com/vlang/v/blob/master/vlib/math/big/special_array_ops.v#L110 |
Seems to be [at least] correct. No idea where optimization issue is. |
Just cc @hungrybluedev ..i think he mostly prevalent the |
If you want to see what's taking the most time, just run
where |
Ensure that you're using I'm currently busy with work but I would like to revisit the implementations and review performance some day. |
I haven't used that. It changes the result: import time
import math.big
fn main() {
start := time.now()
a := big.integer_from_int(9)
result := a.pow(33420489)
b := result % a
println("b: ${b}")
stop := time.now()
println("time elapsed: ${(stop-start).seconds()}")
} and the second: import time
import math.big
fn main() {
a := big.integer_from_int(9)
first := a.pow(99999)
second := a.pow(88888)
start := time.now()
mut b := big.integer_from_int(0)
for _ in 0..1000 {
result := first * second
b += result % a
}
println("b: ${b}")
stop := time.now()
println("time elapsed: ${(stop-start).seconds()}")
} Correspond programs in Python now (after changes):
Seems to |
import time
import math.big
fn main() {
start := time.now()
a := big.integer_from_int(9)
_ = a.pow(33420489)
stop := time.now()
println("time elapsed: ${(stop-start).seconds()}")
} takes care of the unused variable message. And yes, that is what takes the most time... but that is only called once, which means the actual problem is the routines that it calls. |
[Issue moved from "discussion" here]
Hi, I'm working with some big numbers operations. In other cases v is extremely faster than Python and close enough for me to C. However, with those big number operations Python is faster than v and it is crushing difference. First - powers:
On my computer it took
227.2s
. Python's equivalent:this took only
39.75s
.I've checked
v
'spow
implementation for bigints and I couldn't find place for optimalization. It works as it should (using (x^2)^(n/2) "trick"). So... I checked multiplication big numbers:it took
57.8
s, and equivalent for Python:took only
12
s. Doing the same for+
operation I can conclude that bigints in Python are just "somehow" implemented with better performance.I would like to make some "big computation" in
v
.Relevant implementation for Python: here - one can see that multiplication is implemented with Karatsuba algorithm.
Note
You can use the 👍 reaction to increase the issue's priority for developers.
Please note that only the 👍 reaction to the issue itself counts as a vote.
Other reactions and those to comments will not be taken into account.
The text was updated successfully, but these errors were encountered: