Doing multiplication using numbers in arrays

This is a discussion on Doing multiplication using numbers in arrays within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by Dave Evans [edit] Disclaimer: This is a test case; I have tried to make it correct [/edit] ...

  1. #16
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Dave Evans
    [edit]
    Disclaimer: This is a test case; I have tried to make it correct
    [/edit]


    Regards,

    Dave
    I didn't do this on purpose, but if you try the test case for, say 9999*9999, you will see that I didn't apply the correction that is necessary for product digits that were greater than 9 (that is, the carry into the next higher bit. I referred to this in a previous message.

    Here's the complete example:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void product(int *n, int *m, int size);
    #define SIZE 4
    
    int main()
    {
      int i;
      int a[SIZE] = {9, 9, 9, 9};
      int b[SIZE] = {9, 9, 9, 9};
    
      printf("a: ");
      for (i = 0; i < SIZE; i++) {
        printf("%d ", a[i]);
      }
      printf("\n");
    
      printf("b: ");
      for (i = 0; i < SIZE; i++) {
        printf("%d ", b[i]);
      }
      printf("\n");
    
      product(a, b, SIZE); /* calculate and print the product */
      
      return 0;
    }
    
    
    void product(int *n, int *m, int size)
    {
      int i, j, t;
      int val;
    
      int *temp;/* will hold the product then disappear */
    
      temp = malloc(2*size * sizeof(int));
      if (!temp) {
        fprintf(stderr, "Can't allocate storage for temp in product()\n");
        return;
      }
    
      for(t = 0; t < size; t++) {
            temp[t] = 0;
      }
    
      for(i = 0; i < size; i++) {
        for (j=0; j < size; j++) { 
              val = n[i] * m[j]; /* partial product */
              temp[i+j]   += val % 10; /* partial sum this digit */
              temp[i+j+1] += val / 10; /* carry into next digit */
        }
      }
    
      /* 
       * here is the correction for digits that were greater than 9 
      */
      for (i = 0; i < 2*size-1; i++) {
        temp[i+1] += temp[i]/10;
        temp[i]   %= 10;
      }
      /*
        now print the results (remember least significant is first 
     */
      printf("temp: ");
      for (i = 0; i < 2*size; i++) {
        printf("%d ", temp[i]);
      }
      printf("\n");
    
      free(temp);
    }
    Regards,

    Dave

  2. #17
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by elad
    Neandrake: I still can't explain what's happening in a general sense using just english, so I wrote a program using a simple HugeInt class.

    I'll have to try Dave Evans' shortened schema.

    elad: see my corrected code.

    I really like your work, and it shows the power of C++ (using the overloaded + to add in each partial sum). Much more elegant than the old-fashioned C-language approach.

    One very minor point: For your overloaded << operator, if the HugeInt has a value of zero, nothing gets printed. Maybe something like this would be appropriate?

    Code:
      for(i = MAX - 1; i >= 1; --i)
      {
    	if(h.numlist[i] != 0 && !primed)
    	  primed = true;
    	if(primed)
    	  os << h.numlist[i];
      }
      os << h.numlist[0];
    Regards,
    Dave

  3. #18
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Drat. Good point about the value being zero business. I overlooked that in my effort to ignore leading zeros. Special case time.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multiplying Huge numbers in integer arrays
    By invierno in forum C Programming
    Replies: 5
    Last Post: 04-11-2009, 08:40 PM
  2. Question about random numbers
    By Kempelen in forum C Programming
    Replies: 2
    Last Post: 07-02-2008, 06:28 AM
  3. Help with Rational Numbers (C++)
    By cloudjc in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2008, 04:03 PM
  4. pulling numbers from files....
    By Confuzz in forum C++ Programming
    Replies: 3
    Last Post: 09-07-2004, 07:49 PM
  5. using arrays to sort numbers
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 09:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21