I am learning about Karatsuba and was curious how Python actually implements the multiplication operation. Sorry but I couldn't find the documentation for this.

CodePudding user response：

The answer depends on the types of the numbers you are multiplying:

For floating point numbers

The Python objects representing the multiplicands are converted to C doubles and multiplied in C.

static PyObject *
float_mul(PyObject *v, PyObject *w)
{
    double a,b;
    CONVERT_TO_DOUBLE(v, a);
    CONVERT_TO_DOUBLE(w, b);
    a = a * b;
    return PyFloat_FromDouble(a);
}

As far as I know the time complexity here is not relevant since the numbers are fixed precision and multiplying any two floating point numbers together should use the same number of operations.

Of course in the end this is all handled by the CPU, where floating point operations might be more or less optimised depending on your architecture.

For small integers

From the comments in the CPython project

For int multiplication, use the O(N**2) school algorithm unless both operands contain more than KARATSUBA_CUTOFF digits (this being an internal Python int digit, in base BASE)

KARATSUBA_CUTOFF turns out to be 70, so for multiplications where one of the multiplicands has 70 digits or less, your multiplication will be O(N^2) You can find the (lengthy) code for that here.

For big integers

If both integers have more than 70 digits, then the Karatsuba algorithm that you've been learning about is used. You can see the implementation here.

For complex numbers

As you would expect, the real and imaginary parts are split up and the required operations are done as above.

And finally, there are lots of shortcuts for edge cases like multiplication by zero, or single digit multiplicands, that are scattered throughout the codebase.

CodePudding user response：

I found this: https://stackoverflow.com/a/21957447/18578499

In particular this reference: https://hg.python.org/cpython/file/b514339e41ef/Objects/longobject.c#l2694