I was reading through this: http://www.hpdz.net/TechInfo/Bignum.htm#General and I was also exploring MandelMachine's BigNum_Arb class, which is basically a fixed precision lib. I wanted to find some way to do the multiplication but I am kinda struggling. MM is probably doing the multiplication part on c or asm. It also has some other BigNum hardcoded precision obsolete classes that have multiplication implemented, but their data storing format seems different (If I stored the same number created in the arb class, on the fixed digits, the printed double value is wrong).

The format is an array of 64 bit longs , but only the 60 bits are used (4 bits are there for overflow).
[60bits] .decimal_point. [60bits][60bits][60bits]...
I have tried to make a small example with only 2 decimals in order to try the multiplication as described in http://www.hpdz.net/TechInfo/Bignum.htm#General
but I probably mess up the sub-products because the need twice as much bits to be calculated.

Does anyone have any experience on this?

Linkback: https://fractalforums.org/index.php?topic=4598.0

Well, I managed to get it working, as you said have ints as digits. In order to the multiplication you have to calculate the N^2 sub multiplications and then add each column together. This sum is done into a long, but what happens if this long overflows? This happens if the numbers have many digits, lets say 10.

From the 64 bits, I kept some of the first bits as a carry, for the next digit, but I was first accumulating the sum and then I was masking the carry to the next digit. Should I move the carry to the next digit on every sum to avoid overflow?

here is a snippet:

long old_sum = 0;
long sum = 0;
SHIFT = 30;
MASK = 0x3FFFFFFFL;

 for(int i = fracDigits; i > 0; i--) {

            sum = (old_sum >>> SHIFT); //carry from prev
            for(int j = 0, k = i; j <= i; j++, k--) {
                long bj = bdigits[j];
                long ak = digits[k];

                 sum += bj * ak; //THIS CAN OVERFLOW

            }
            resDigits = (int) ((sum) & MASK);

            old_sum = sum;
   
        }

        sum = (old_sum >>> SHIFT);

        long bj = bdigits[0];
        long ak = digits[0];

        sum += bj * ak;

        resDigits[0] = (int) (sum);

Well there are reserved bits, on every int I use 30 bits, but when you multiply two 30 bit ints you need 60 bits, so thats why I use a long to store the temp product.
The summation for that column is taking place into a long, but this overflows. (The products are large because every digit after the decimal point have digits starting from the 30th bit and downwards)

I switched the code to this and it works for now:

long old_sum = 0; //There is an extra multiplication step before this but for simplicity I leave the final step
long sum = 0;
SHIFT = 30;
MASK = 0x3FFFFFFFL;

for(int i = fracDigits; i > 0; i--) {

            sum = old_sum; //carry from prev
            carry = 0;
            for(int j = 0, k = i; j <= i; j++, k--) {
                long bj = bdigits[j];
                long ak = digits[k];

                sum += bj * ak;
                carry += sum >>> SHIFT;
                sum = sum & MASK;

            }
            resDigits = (int) (sum);

            old_sum = carry;
        }

        sum = old_sum;

        long bj = bdigits[0];
        long ak = digits[0];

        sum += bj * ak;

        resDigits[0] = (int) (sum);

        result.sign = sign * b.sign;


Do you have any other proposal?

Thanks, I will have a look at this. For now I think that using a carry for the high bits of the sum (30+) solved the issue. Hopefully my carry wont overflow
The high 30 bits of the long sum for digit i are basically the low 30 bits for the long sum of digit i + 1
I managed to refactor my karatsuba implementation as well.

I have implemented mult, multKaratsuba, square, squareKaratsuba (square is faster no matter what)

Processors these days usually come with hardware to do 64bit * 64bit = 128 bit multiplication, but programming languages don't usually offer easy access to the result's upper 64 bits. It may be possible, but you might have to dig deep to find out which obstacles you need to overcome.

You could choose to do multiplication in smaller chunks (as it is now) and addition in larger chunks. But that introduces a dependency on byte order of numbers in memory ("endianness"). Not a showstopper, but causes issues with portability.

I have a question regarding Karatsuba. All the wikis that I read basically say that if you have N number of digits, you cut the N in half and perform two multiplications, one of the fist N/2 digits and one with the second N/2 digits and then you combine the results using:

(x1 + x0)*(y1 + y0) - x1*x0 - y1*y0

where x0, y0 the first N/2 digits and x1,y1 the second N/2 digits.

Cant we do it on a different way?

Using the attached example:

c4 (not used as an output) = b3 * a1  + b2 * a2 + b1 * a3
c3 = b3*a0 + b2 * a1 + b1 * a2 + b0 * a3 + carry(c4)
c2 = b2 * a0 + b1 * a1 + b0 * a2 + carry(c3)
c1 = b1 * a0 + b0 * a1 + carry(c2)
c0 = b0 * a0 + carry(c1)

Applying the karatsuba formula internally gives:

c4 (not used as an output) = (b3 + b1) * (a3 + a1) - b3 * a3 - b1 * a1  + b2 * a2
c3 = (b3 + b0) * (a3 + a0) - b3*a3 - b0*a0  + (b2 + b1) * (a2 + a1) - b2*a2 -b1*a1 + carry(c4)
c2 = (b2 + b0) * (a2 + a0) - b2*a2 - b0*a0 + b1 * a1 + carry(c3)
c1 = (b1 + b0) * (a1 + a0) - b1*a1 -b0*a0 + carry(c2)
c0 = b0 * a0 + carry(c1)

We can precalculate all bn*an

Isnt this equivalent ?