Geek Answers Handbook

Long multiply c

I am trying to implement a long multiply method (school method) in C. I need to write my program in a 2 ^ 32 database. I am not sure how to start. I have an algorithm that I want to use here:

for (i = 0; i < n; i++) {
   carry = 0;
   for (j = 0; j < n; j++) {
      product = a[i] * b[j] + result[i + j] + carry;
      result[i + j] = p % base;
      carry = floor(product / base);
   }
   result[i + n] = carry;
}

Any hints are welcome. I just can't come up with a good idea.

+4
source share
3 answers

Imagine that I have 2 numbers with "numbers":

b_2 b_1 b_0

and

a_1 a_0

to multiply them together, we first multiply everything by b by a_0. Then we multiply all 'b by a_1 and move the result one place to the left (this is 32 bits) before adding the two results together.

a_0, a_0 64- , b_0. 32 32 c_0. 32 - .

a_0 b_1 ( 64 ). 32 , 32 : 'c_1'. 32 - . , b. - 32 .

a_1. , , 32 a_1. a_1 1_0 .

+2

"" , 32- 64- , 32- , . - , - ( 2 ^ 32). x86 , , C/++ 64- , , .

+3

, base, , base. , base 2 32 64- , 32- .

, :

/* multiply two n-word numbers, giving a 2n-word result */
void multiply(uint32_t *result, uint32_t *a, uint32_t* b, int n) {
    int i, j;
    for (i = 0; i < 2*n; i++)
        result[i] = 0;
    for (i = 0; i < n; i++) {
        uint32_t carry = 0;
        for (j = 0; j < n; j++) {
            uint64_t product = (uint64_t)a[i] * b[j] + result[i + j] + carry;
            result[i + j] = product & 0xffffffff;
            carry = product >> 32; }
        result[i+n] = carry; }
}

, , , , .

+2
source

More articles:


All Articles