Bignum operations should be optimized

[Redysz]

[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 checked v's pow 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.8s, 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 12s. 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.

[blackshirt]

[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 checked v's pow 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.8s, 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 12s. 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.

I think karatsuba algorithm has been implented ... see https://github.com/vlang/v/blob/master/vlib/math/big/special_array_ops.v#L110

[Redysz]

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.

[blackshirt]

Just cc @hungrybluedev ..i think he mostly prevalent the math big author that knowing the detail where its should be optmized

[JalonSolov]

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.

[hungrybluedev]

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.

[Redysz]

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

[JalonSolov]

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.