[Feature Request] Implement fast multiplication (Karatsuba, Tom-Cook, FFT)

[dlesnoff]

As written in the Readme.md file, we need to implement fast multiplication to improve many different algorithms (at once). I prefer to write a Github issue, as it is easier to gather good implementations and documentation of fast multiplication algorithms and issue enables to track progress with PRs.

The gmp section 15 algorithms describes fast multiplication algorithms : https://gmplib.org/gmp-man-6.2.1.pdf I guess we might want to it differently than gmp and take into account other multi-precision arithmetic library . Especially the tresholds at which we switch from one algorithm to another might be different than GMP (because internal representation is different).

Squaring is faster than generic multiplication. We might want to take this into account for pow and powmod multiplication (e.g. montgomery squaring algorithm).

I am also surprised in-place multiplication is realized with a = a * b. Can we optimize this case as to reduce memory and copy operations ?

[dlesnoff]

I have written a function : func unsignedKaratsubaMultiplication(a: var BigInt, b, c: BigInt) {.inline.} = But I am unsure how to handle certain cases of the algorithm. I have written recursively so far, and we have to handle the base case :

  if bl == 1:
    # base case : multiply the only limb with each limb of second term
    var a: BigInt
    unsignedMultiplication(a, c, b)
    return a
  if cl == 1:
    var a: BigInt
    unsignedMultiplication(a, b, c)
    return a

Here I return using the already programmed function unsignedMultiplication to compute b*c knowing that b (or c) is only one limb (a constant in a polynomial representation). We might first add an unsigned multiplication that takes a uint a and a bigint b and computes a*b.

[dlesnoff]

I have found this reference by Richard P.Brent & P. Zimmerman (arithmetic researchers that helped to develop GMP) which describe a little more precisely karatsuba, the subtractive variant (variant that reduce carry handling).