Thread: Doing multiplication using numbers in arrays

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

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

Drat. Good point about the value being zero business. I overlooked that in my effort to ignore leading zeros. Special case time.