Integer multiplication in place

Question

I am writing a program (in C) in which I am trying to calculate the power of large numbers in the shortest possible period. The numbers that I represent as vectors of numbers, so all operations must be written manually.

The program will be much faster without all distributions and exemption from intermediate results. Is there any algorithm for integer multiplication in place? For example, the function

void BigInt_Times(BigInt *a, const BigInt *b); 

puts the result of multiplying a and b inside a without using an intermediate value.

Answer 1

Here muln() 2n (indeed, n) using n = 2n multiplication by place for unsigned integers. You can configure it to work with 32-bit or 64-bit digits instead of 8-bit ones. The modulo operator is left for clarity.

muln2() n by n = n multiplication in place (as outlined here ), also working on an 8-bit "digit".

 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> typedef unsigned char uint8; typedef unsigned short uint16; #if UINT_MAX >= 0xFFFFFFFF typedef unsigned uint32; #else typedef unsigned long uint32; #endif typedef unsigned uint; void muln(uint8* dst/* n bytes + n extra bytes for product */, const uint8* src/* n bytes */, uint n) { uint c1, c2; memset(dst + n, 0, n); for (c1 = 0; c1 < n; c1++) { uint8 carry = 0; for (c2 = 0; c2 < n; c2++) { uint16 p = dst[c1] * src[c2] + carry + dst[(c1 + n + c2) % (2 * n)]; dst[(c1 + n + c2) % (2 * n)] = (uint8)(p & 0xFF); carry = (uint8)(p >> 8); } dst[c1] = carry; } for (c1 = 0; c1 < n; c1++) { uint8 t = dst[c1]; dst[c1] = dst[n + c1]; dst[n + c1] = t; } } void muln2(uint8* dst/* n bytes */, const uint8* src/* n bytes */, uint n) { uint c1, c2; if (n >= 0xFFFF) abort(); for (c1 = n - 1; c1 != ~0u; c1--) { uint16 s = 0; uint32 p = 0; // p must be able to store ceil(log2(n))+2*8 bits for (c2 = c1; c2 != ~0u; c2--) { p += dst[c2] * src[c1 - c2]; } dst[c1] = (uint8)(p & 0xFF); for (c2 = c1 + 1; c2 < n; c2++) { p >>= 8; s += dst[c2] + (uint8)(p & 0xFF); dst[c2] = (uint8)(s & 0xFF); s >>= 8; } } } int main(void) { uint8 a[4] = { 0xFF, 0xFF, 0x00, 0x00 }; uint8 b[2] = { 0xFF, 0xFF }; printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]); muln(a, b, 2); printf("0x%02X%02X%02X%02X\n", a[3], a[2], a[1], a[0]); a[0] = -2; a[1] = -1; b[0] = -3; b[1] = -1; printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]); muln2(a, b, 2); printf("0x%02X%02X\n", a[1], a[0]); return 0; } 

Output:

 0xFFFF * 0xFFFF = 0xFFFE0001 0xFFFE * 0xFFFD = 0x0006 

I think this is the best we can do on the spot. The only thing I don't like about muln2() is that it needs to accumulate larger intermediates and then distribute a larger transfer.

Answer 2

Well, the standard algorithm consists of multiplying each digit (word) "a" by each digit "b" and summing them into the appropriate places as a result. Thus, the ith digit of a goes into each digit from i to z + n of the result. Therefore, in order to do this on the spot, you need to calculate the output numbers from the most significant to the smallest. This is a little more complicated than doing it from the smallest to the most, but not much ...

Answer 3

It doesn't seem like you really need an algorithm. Rather, you need to make better use of the language features.

Why not just create this function as indicated in your answer? Use it and enjoy! (The function will most likely return a reference to a as the result.)

Answer 4

Typically, big-int views vary in length depending on the value presented; in general, the result will be longer than any of the operands. In particular, for multiplication, the size of the resulting representation is approximately the sum of the sizes of the arguments.

If you are sure that memory management is indeed a bottleneck for your particular platform, you might consider introducing a multiplication function that updates the third value. In terms of prototype C-style functions above:

 void BigInt_Times_Update(const BigInt* a, const BigInt* b, BigInt* target); 

This way you can handle memory management the same way C ++ std :: vector <> containers do: your update target needs to redistribute its heap data when the existing size is too small.