CODEWITHSUNDEEP
cmultiplicationbigintegerbigint
felixoben
felixoben

Reputation: 49

C big number multiplication

Im trying to write an big integer multiplication for my first test its working but if the uint8_t number is more than one than the result is wrong. I tried it 2 days to find a solution and to understand what Im doing wrong...

void main(void){
    uint8_t x[] = {0xFF};
    uint8_t y[] = {0xFF};
    uint8_t z[] = {0x00, 0x00};
    mul(x,1,y,1,z);
    printf("X*Y = Z: ");
    for(int i = 0; i < 2; i++)
        printf("%02X ",z[i]);
    printf("\n");
    //Output: X*Y = Z: FE 01 == FE01 CORRECT!

    uint8_t a[] = {0x0F, 0xFF};
    uint8_t b[] = {0x0F, 0xFF};
    uint8_t c[] = {0x00, 0x00, 0x00, 0x00};
    mul(a,2,b,2,c);

    printf("A*B = C: ");
    for(int i = 0; i < 4; i++)
        printf("%02X ",c[i]);
    printf("\n");
    //Output: A*B = C: 00 FE E0 01 != FFE001 WRONG?!

}

void mul(uint8_t *a, int a_n,uint8_t *b, int b_n,uint8_t *c){
    int i,j;
    uint16_t A;

    for(i = a_n-1; i >= 0; i--){
        A=0;
        for(j = b_n-1; j >= 0; j--){
            A += (uint16_t) a[i] * b[j]; 
            c[i+j+1] += A;
            A >>= 8;
        }
        c[i] = A;;
    }
}

Upvotes: 1

Views: 268

Answers (2)

Bharadwaj Nadiminti
Bharadwaj Nadiminti

Reputation: 21

try using this code

#include <string.h>
 
int main()
{
    int a[100],b[100];
    int ans[200]={0};
    int i,j,tmp;
    char s1[101],s2[101];
    scanf(" %s",s1);
    scanf(" %s",s2);
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(i = l1-1,j=0;i>=0;i--,j++)
    {
        a[j] = s1[i]-'0';
    }
    for(i = l2-1,j=0;i>=0;i--,j++)
    {
        b[j] = s2[i]-'0';
    }
    for(i = 0;i < l2;i++)
    {
        for(j = 0;j < l1;j++)
        {
            ans[i+j] += b[i]*a[j];
        }
    }
    for(i = 0;i < l1+l2;i++)
    {
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    }
    for(i = l1+l2; i>= 0;i--)
    {
        if(ans[i] > 0)
            break;
    }
    printf("Product : ");
    for(;i >= 0;i--)
    {
        printf("%d",ans[i]);
    }
    return 0;
}```

Upvotes: 0

chux
chux

Reputation: 153456

At least 1 problem:

Overflow in c[]

c[i+j+1] += A; may overflow c[]. @Barmar

   // A += (uint16_t) a[i] * b[j]; 
   // c[i+j+1] += A;
   // A >>= 8;
   A = (uint16_t) a[i] * b[j] + A + c[i+j+1];
   c[i+j+1] = A & 0xFFu;  // or A % 256u
   A >>= 8;

Sample fixed code (with other minor improvements)

// Using re-ordered parameters for better static code analysis
// Use const
// Idiomatic to use size_t for array sizing/indexing
// Perhaps return c[] to allow for chained calls.
uint8_t *mul(size_t a_n, const uint8_t a[a_n], size_t b_n, const uint8_t b[b_n],
    uint8_t c[a_n + b_n]) {

  for (size_t i = a_n; i-- > 0;) {
    unsigned A = 0; // Let compiler use the natural unsigned rather than force uint16_t
    for (size_t j = b_n; j-- > 0;) {
      A += 1u * a[i] * b[j] + c[i + j + 1]; // 1u * vs. cast, let compiler optimize
      c[i + j + 1] = A & 0xFFu;
      A >>= 8;
    }
    c[i] = A;
  }

  return c;
}

Upvotes: 3

Related Questions