Comments (7)
[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:
import time import math.big fn main() { start := time.now() a := big.integer_from_int(9) result := a.pow(33420489) stop := time.now() println("time elapsed: ${(stop-start).seconds()}") }On my computer it took
227.2s
. Python's equivalent:from time import perf_counter def main(): start = perf_counter() result = 9**33420489 stop = perf_counter() print(f"time elapsed: {(stop-start):.2f}")this took only
39.75s
. I've checkedv
'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:import time import math.big fn main() { a := big.integer_from_int(9) first := a.pow(99999) second := a.pow(88888) start := time.now() for _ in 0..1000 { result := first * second } stop := time.now() println("time elapsed: ${(stop-start).seconds()}") }it took
57.8
s, and equivalent for Python:from time import perf_counter def main(): first = 9**99999 second = 9**88888 start = perf_counter() for _ in range(1000): result = first * second stop = perf_counter() print(f"time elapsed: {(stop-start):.2f}")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" inv
.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.
I think karatsuba algorithm has been implented ... see https://github.com/vlang/v/blob/master/vlib/math/big/special_array_ops.v#L110
from v.
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.
from v.
Just cc @hungrybluedev ..i think he mostly prevalent the math big
author that knowing the detail where its should be optmized
from v.
If you want to see what's taking the most time, just run
v -profile - run bignum.v
where bignum.v
is the first example given.
from v.
Ensure that you're using v -prod .
to get the optimised binaries for speed.
I'm currently busy with work but I would like to revisit the implementations and review performance some day.
from v.
Ensure that you're using
v -prod .
to get the optimised binaries for speed.
I haven't used that. It changes the result: 59s
for the first program and 16s
for the latter - still slower than Python.
I needed to add some code to use "unused variables". So updated first program is:
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): ~43s
and ~13s
v -profile - run bignum.v
Seems to math__big__multiply_digit_array
be a bottleneck:
-run.txt
from v.
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.
from v.
Related Issues (20)
- flag.FlagParser bug with certain combination of flags
- Binary crashes when compiled with tcc on OpenBSD HOT 5
- C compilation error when compiling simple Generic Interface test case
- cgen error for using a `default := p or { T{} }` construct in a generic function HOT 6
- type OneD = []Thing causes unexpected behaviour HOT 1
- FlagParser single letter options dependent on order of flags.
- C error when trying to use a &Struct value where Struct is required instead
- toml: Provide a way to set default values when decoding TOML
- C error when implementing two interfaces, one of them generic
- Show where bad union code is located HOT 2
- if ternary: failing to compile HOT 1
- vfmt removes selective import of interface when used only in implements clause HOT 3
- cgen error for `for mut ccc in aaa { match ccc {` where `aaa` is `[]string{}`
- tcc compiler not detected without path HOT 4
- random big.Integer function HOT 3
- Support KDL HOT 3
- Unknown type for json.decode with nested generics
- Allow same enum value HOT 2
- Running `v fmt -w gemv_test.v` formats a file in an oscillating manner, when run several times, without stabilisation.
- v template small bug something.${name}, will not work (because of . in front)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from v.