Search code examples
godistributed-computingbiginteger

slow int.big calculation and only on one thread

I use the following code in my test:

package main

import "fmt"
import "math/big"

func main() {
    input := "3333333333333333333.......tested with 100'000x3 , tested with 1'000'0000x3, tested with 10'000'000x3"
    bi := big.NewInt(0)
    if _, ok := bi.SetString(input, 10); ok {
        fmt.Printf("number = %v\n", bi)

        testval := new(big.Int)
        testval.SetString("3", 10)

        resultat, isGanzzahl := myDiv(bi, testval)
        fmt.Printf("isGanzzahl = %v, resultat = %v\n", isGanzzahl, resultat)
    } else {
        fmt.Printf("error parsing line %#v\n", input)
    }
}

func myDiv(minuend *big.Int, subtrahend *big.Int) (*big.Int, bool) {
    zerotest := big.NewInt(0)

    modulus := new(big.Int)
    modulus = modulus.Mod(minuend, subtrahend)

    if zerotest.Cmp(modulus) == 0 {
        res := big.NewInt(0)
        res.Quo(minuend, subtrahend)
        return res, true
    } else {
        return big.NewInt(0), false
    }
}
  • 100'000 x 3 / 3 == not even a quater second
  • 1'000'000 x 3 / 3 == 9.45 seconds
  • 10'000'000 x 3 / 3 == 16.1 minute

Im looking for a way to make this happens much much faster. If i would like to do this multithreaded in go how do i do this with go-routines? Is there a faster way to do a division with larger numbers?

As this is just for testing i planned to use Numbers in the range of 100'000'000 - 1'000'000'000 digits (which would then be 1GB of ram usage). But 1 billion digits would not work because it would take years to complete.

What would then happen if it is N / M ? Where N=1billion digit, M=10million digit. Is this even possible on a powerful home computer?

How would it look / or what do i have to change to being able to distribute this work to multiple small computer (for example AWS)?

Solution

  • If your number is more than 100000 digits long, you need to use Fast Fourier Transform for multiplication and division: https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods . The basic idea is to treat numbers as polynomials with x being power of 10 (or power of 2 if you want binary system). Multiply polynomials using Fast Fourier Transform and then propagate carry to get a number from a polynomial. I.e. if we need to multiply 19 by 19 and we use x = 101, we will have (1 * x + 9) * (1 * x + 9) = x2 + 18 * x + 81. Now we propagate carry to convert polynomial back to number: x2 + 18 * x + 81 = x2 + (18 + 8) * x + 1 = x2 + 26 * x + 1 = (1 + 2) * x2 + 6 * x + 1 = 3 * x2 + 6 * x + 1 = 361. The trick is that polynomials can be multiplied efficiently (O(N*log(N) time) using Fast Fourier Transform. The coefficients of the product polynomial are larger than digits, so you need to choose x carefully in order to avoid integer overflow or precision problems.

    There unlikely to be a golang library for that so you will need to write it yourself. Here are a few short FFT implementations you can use as a starting point:

    http://codeforces.com/contest/632/submission/16449753 http://codeforces.com/contest/632/submission/16445979 http://codeforces.com/contest/632/submission/16449040 http://codeforces.com/contest/632/submission/16448169

    If you decide to use FFT modulo prime, see this post for a good choice of the modulo: http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html