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; I'm writing a class that can handle integers up to 40 characters long, I have been able to get add ...

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    Doing multiplication using numbers in arrays

    I'm writing a class that can handle integers up to 40 characters long, I have been able to get add and subtract working fine, but I can't see what is wrong with multiply.

    numList is an array of integers (i know, they could be smaller in size), and it just holds the number, index 0 being the least significant number. Using this code, I get small negative numbers (I'm assuming because numList is signed, for when I set it as unsigned, the numbers are extremely large). hugeSize is a #define set at 40. Does anyone see what is wrong with my code? (please no code posting unless it's a small mistake). thank you. (ps, if you need more code, or prototypes, I can upload).

    Code:
    void hugeInt::multiply(hugeInt n, hugeInt m)	//multiply two hugeInts
    {
    	for (int t=0; t<hugeSize; t++)	//clear current
    		numList[t]=0;
    	int val=0;
    	for (int i=0; i<hugeSize; i++)	//multiply each element in n by
    	{									//every element in m
    		for (int j=0; j<hugeSize; j++)
    		{
    			val = n.numList[i] * m.numList[j];
    			numList[i+j] = val % 10;
    			numList[i+j+1] += val / 10;
    			numList[i+j] += val % 10;
    		}
    	}
    }
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    here's an (untested) idea for you. Too hard to explain in words. Assumes you have += overloaded for hugeInt class.
    Code:
    int t;
    for (t=0; t<hugeSize; t++) 
    numList[t]=0;
    int val;
    hugeInt temp;
     
    for (int i=0; i<hugeSize; i++) 
    {	
      for(t = 0; t < hugeSize; t++)
    	temp[t] = 0;
      for (int j=0; j<hugeSize; j++)
      {	
    	val = n.numList[i] * m.numList[j];
    	temp[i+j] += val % 10;
    	temp[i+j+1] += val / 10;
      }
      numList += temp;
    }

  3. #3
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    I tried it and got different wrong numbers. Hrmph, thanks for the input, gonna try fiddling with it tomorrow.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  4. #4
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by neandrake
    I tried it and got different wrong numbers. Hrmph, thanks for the input, gonna try fiddling with it tomorrow.
    Why doesn't your code give the right answer?

    Well, have you tried to do something simple, like multiplying 1 by 2? I got 4 with your code.

    Look at how you handle the cross products (put cout << inside the loops inside the product() function). What's going on? You tell me.

    I see two ways to handle it: Create each cross product and simply add into each partial sum.

    Then after all multiplications are done, start with the least significant digit. If it's greater than 9 (digit/10 not equal to 0), increment the "next digit" by "this digit"/10, then replace "this digit" by "this digit"%10.

    The other way is to make the correction in place (that is, as each cross product is added into the previous value for that cross product, see if it is greater than 9 and make the correction as I indicated above).


    After you get it to multiply 1*2, try 9*9, 99*99, etc. (Remember that, in general, multiplying two n-digit numbers can give a product with as many as 2n digits.)
    Regards,

    Dave
    Last edited by Dave Evans; 11-04-2004 at 08:48 AM.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Alright, I've worked through some simple examples with my version---see below.
    Code:
    for(i = 0; i < hugeSize; i++)
    {
      for(t = 0; t < hugesize; t++)
    	temp[t] = 0;
      for (int j=0; j<hugeSize; j++)
      { 
    	val = n.numList[i] * m.numList[j];
    	temp[i+j] += val % 10;
    	temp[i+j+1] += val / 10;
      }
      numList += temp;
    }
    and here's my work through of several simple examples.

    let:
    n = 7;
    m = 9;
    i = 0, j = 0
    val = 7 * 9 = 63
    temp[0] = 0 + 3 = 3
    temp[1] = 0 + 6 = 6
    now numlist = numlist + temp = 00 + 36
    or
    numlist[0] = numlist[0] + temp[0] = 0 + 3 = 3
    numlist[1] = numlist[1] + temp[1] = 0 + 3 = 6
    or 7 * 9 = 63 which is correct
    __________________________________________________ _
    let:
    n = 7
    m = 99
    i = 0; j = 0
    val = 7 * 9 = 63
    temp[0] = 0 + 3 = 3
    temp[1] = 0 + 6 = 6
    i = 0, j = 1
    val = 7 * 9 = 63
    temp[1] = 6 + 3 = 9
    temp[2] = 0 + 6 = 6
    now numlist = numlist + temp = 000 + 396
    or
    numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
    numlist[1] = numlist[1] + temp[1] = 6 + 3 = 9
    numlist[2] = numlist[2] + temp[2] = 0 + 6 = 6
    or 7 * 99 = 693 which is correct
    __________________________________________________ _____
    let:
    n = 77
    m = 99
    i = 0; j = 0
    val = 7 * 9 = 63
    temp[0] = 0 + 3 = 3
    temp[1] = 0 + 6 = 6
    i = 0, j = 1
    val = 7 * 9 = 63
    temp[1] = 6 + 3 = 9
    temp[2] = 0 + 6 = 6
    numlist = numlist + temp = 000 + 396
    or:
    numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
    numlist[1] = numlist[1] + temp[1] = 6 + 3 = 9
    numlist[2] = numlist[2] + temp[2] = 0 + 6 = 6
    clear temp to all zero's
    numlist remains as is
    i = 1; j = 0
    val = 7 * 9 = 63
    temp[1] = 0 + 3 = 3;
    temp[2] = 0 + 6 = 6;
    i = 1, j = 1
    val = 7 * 9 = 63
    temp[2] = 6 + 3 = 9;
    temp[3] = 0 + 6 = 6;
    numlist = numlist + temp = 396 + 0396;
    or
    numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
    numlist[1] = numlist[1] + temp[1] = 9 + 3 = 12
    numlist[1] = 2 and carry 1 to numlist[2];
    numlist[2] = numlist[2] + temp[2] + 1 = 6 + 9 + 1 = 17;
    numlist[2] = 7 and carry 1 to numlist[3]
    numlist[3] = numlist[3] + temp[3] + 1 = 0 + 6 + 1 = 7
    or
    numlist[0] = 3;
    numlist[1] = 2;
    numlist[2] = 7;
    numlist[3] = 7;
    or 77 * 99 = 7723 which is correct

    This algorhithm attemps to mimic long multiplication with temp being a line under the uderscore, in reverse of course.
    77
    * 99
    ____
    693
    6930
    _____
    7723

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by elad
    Alright, I've worked through some simple examples with my version---see below.
    Code:
      numList += temp;
    and here's my work through of several simple examples.

    let:
    n = 7;
    m = 9;
    i = 0, j = 0
    val = 7 * 9 = 63
    temp[0] = 0 + 3 = 3
    temp[1] = 0 + 6 = 6
    now numlist = numlist + temp = 00 + 36
    or
    numlist[0] = numlist[0] + temp[0] = 0 + 3 = 3
    numlist[1] = numlist[1] + temp[1] = 0 + 3 = 6
    or 7 * 9 = 63 which is correct

    now numlist = numlist + temp = 00 + 36
    Huh?????

    Have you actually compiled and executed a program?

    What is numlist? What is temp?

    Show me an entire executable snippet that includes data definitions.

    Regards,

    Dave

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Dave Evans--No I have not created an executable program. And no I can't gaurantee my algorhithm or code sample will work. But if I can't get an algorhithm to work on paper, then I won't even try to get it to compile. And since it's not my project, I'm just trying to help Neandrake find a way to finish the task.

    If you go back to Neandrake's original post, Neandrake appears to be attempting to implement a hugeInt class. He/she provides enough information to work out the schematics of the class, even if he/she didn't post it all. Furthermore, Neandrake posted the version of code that they couldn't get to work.

    I found it difficult to explain using words what I thought was wrong with the algorhithm Neandrake posted to multiply two hugeInts together. Therefore I posted an algorhithm of my own. I had worked through my algorhithm on paper before posting so when Neandrake posted that it didn't work I reworked some examples again, and posted them. I thought my paperwork was commented well enough for Neandrake to work through, but then again, who knows. I'll edit my last post to make it even clearer so you can try to walk through it if you want.

    Undoubtedly there are other algorhithms to successfully multiply two hugeInts. If you can help assist Neandrake to successful completion using Neandrake's algorhithm, so be it.

  8. #8
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Code:
    val = n.numList[i] * m.numList[j];
    Assuming 32bit integers, this can easily overflow.
    To overflow "n operator m" you need the result to be 2^32 or greater. In an adition to prevent this the arithemic median of the two numbers must be no greater than 2^32/2, or 2^31, but when multipling you need then the median to be 2^32^0.5 or 2^16.
    Therefore using integer division and remainder will work for adition, but will easily fail when multiplying.

    So to manipulate multiplication you have to separate each of your 32bit int in 16bit pieces and multiply then alone, then add them together.
    Adition overflows at max by one unit, multiplication may overflow to 2^32-2 (using again 32bit ints).

  9. #9
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    ok, so I tried rewriting the whole function with no luck still. This is so aggrevating. I've tried following through the code and I can't see why it doesn't work. This was my original function, which makes more sense to me, but it still doesn't work!

    Code:
    void hugeInt::multiply(hugeInt n, hugeInt m)	//multiply two hugeInts
    {
    	for (int t=0; t<hugeSize; t++)	//clear current
    		numList[t]=0;
    	hugeInt temp;
    	int mult=0;
    	int carry=0;
    	for (int i=0; i<hugeSize; i++)
    	{
    		for (int p=0; p<hugeSize; p++)
    			temp.numList[p] = 0;
    		for (int j=0; j<hugeSize; j++)
    		{
    			mult = n.numList[i] * m.numList[j] + carry;
    			if (mult > 9)
    			{
    				carry = mult / 10;
    				mult -= carry * 10;
    			}
    			else
    			{
    				carry = 0;
    			}
    			temp.numList[j] = mult;
    		}
    		add(*this, temp);
    	}
    }
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  10. #10
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by xErath
    Code:
    val = n.numList[i] * m.numList[j];
    Assuming 32bit integers, this can easily overflow.
    To overflow "n operator m" you need the result to be 2^32 or greater. In an adition to prevent this the arithemic median of the two numbers must be no greater than 2^32/2, or 2^31, but when multipling you need then the median to be 2^32^0.5 or 2^16.
    Therefore using integer division and remainder will work for adition, but will easily fail when multiplying.

    So to manipulate multiplication you have to separate each of your 32bit int in 16bit pieces and multiply then alone, then add them together.
    Adition overflows at max by one unit, multiplication may overflow to 2^32-2 (using again 32bit ints).
    He is multiplying decimal digits at a time: n.numList[i] has a value from 0 to 9; m.numList[i] has a value from 0 to 9.

    Regards,

    Dave

  11. #11
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Is he? Then neandrake let me note that you class for the time being is terribly unifficient. But you'll work on it.
    But why using a int to store something smaller that half char?? 32bit register manipulations are faster?? Yeap maybe, but then that's a waste of memory.

  12. #12
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by neandrake
    ok, so I tried rewriting the whole function with no luck still. This is so aggrevating. I've tried following through the code and I can't see why it doesn't work. This was my original function, which makes more sense to me, but it still doesn't work!
    At the top of this thread you said that you didn't want anyone to furnish you with detailed code, so up until now I have tried to keep things general. I will now get a little more specific, so if you don't to see some code, stop reading now.

    Here's an example in C, using your program as a starting point:

    (Yes, I know this is the C++ board, but the algorithm applies to C and C++ users alike --- so sue me.)

    Now, just because it works for a few examples doesn't mean that you should accept it as perfect. Test, test, test (but remember that you can't prove a program is correct by testing --- make sure it does exactly what you want.)

    Change SIZE to anything you want, and use any numbers you want (Obviously it only works for non-negative integers.)

    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] = {7, 0, 0, 0};
      int b[SIZE] = {9, 9, 0, 0};
    
      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 */
        }
      }
      printf("temp: ");
      for (i = 0; i < 2*size; i++) {
        printf("%d ", temp[i]);
      }
      printf("\n");
    
      free(temp);
    }
    [edit]
    Disclaimer: This is a test case; I have tried to make it correct, but I make no claims as to optimality, efficiency, elegance or anything else. If it helps,, I say, "Good." If not, I say, "Good day."
    [/edit]


    Regards,

    Dave
    Last edited by Dave Evans; 11-04-2004 at 05:27 PM.

  13. #13
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by elad
    Dave Evans--No I have not created an executable program. And no I can't gaurantee my algorhithm or code sample will work.
    I'm sorry if I sounded rude. I don't really mean to be that way. I just got caught up in the dilemma of trying to help by giving general advice that might lead to something that works without actually doing the whole job. I think that's the problem a lot of us have. Just trying to help.

    Regards,

    Dave

  14. #14
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Quote Originally Posted by xErath
    Is he? Then neandrake let me note that you class for the time being is terribly unifficient. But you'll work on it.
    But why using a int to store something smaller that half char?? 32bit register manipulations are faster?? Yeap maybe, but then that's a waste of memory.
    I realize this problem, but at the moment I'm not concerned with it. Originally I had the class using an array of char's to hold the large number, but it got too messy and didn't work a whole lot. I switched over to using ints and have been more succesful with it. Efficiency isn't something I need to worry about at this time. Thanks though.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  15. #15
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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. The limitation of the class is as you've described: the HugeInt(long) constructor won't hold as many ints as I'd like. I suspect you will want to accept input as a string and convert the char to ints before storing them in numlist eventually. But getting the algorhithm down first in a manner you can grasp is important.
    Code:
    #include <iostream>
    using namespace std;
    
    const int MAX = 20;
    
    struct HugeInt
    {
      int numlist[MAX];
      HugeInt();
      HugeInt(long);
      HugeInt(const HugeInt &);
      HugeInt & operator=(const HugeInt &);
      friend ostream & operator <<(ostream & os, const HugeInt &);
      HugeInt operator+(const HugeInt &);
      friend HugeInt operator*(const HugeInt &, const HugeInt &);
    };
    
    HugeInt::HugeInt()
    {
      int i;
      for(i = 0; i < MAX; ++i)
    	numlist[i] = 0;
    }
    
    HugeInt::HugeInt(long num)
    {
      int i = 0;
      for(i = 0; i < MAX; ++i)
    	numlist[i] = 0;
    
      i = 0;
      while(num > 0 && i < MAX)
      {
    	numlist[i++] = num % 10;
    	num /= 10;
      }
    }
    
    HugeInt::HugeInt(const HugeInt & h)
    {
      int i;
      for(i = 0; i < MAX; ++i)
    	numlist[i] = h.numlist[i];
    }
    
    HugeInt & HugeInt::operator=(const HugeInt & rhs)
    {
      int i;
      for(i = 0; i < MAX; ++i)
    	numlist[i] = rhs.numlist[i];
      return *this;
    }
    
    ostream & operator<<(ostream & os, const HugeInt & h)
    {
      int i;
      bool primed = false;
      for(i = MAX - 1; i >= 0; --i)
      {
    	if(h.numlist[i] != 0 && !primed)
    	  primed = true;
    	if(primed)
    	  os << h.numlist[i];
      }
      return os;
    }
    
    HugeInt HugeInt::operator+(const HugeInt & rhs)
    {
      HugeInt r;
    
      int i;
      for(i = 0; i < MAX; ++i)
      {
    	 r.numlist[i] = r.numlist[i] + numlist[i] + rhs.numlist[i];
    	 if(r.numlist[i] > 9)
    	 {
    	   r.numlist[i] = r.numlist[i] % 10;
    	   r.numlist[i + 1] = r.numlist[i + 1] + 1;   
    	 }
      }
      return r;
    }
    
    HugeInt operator *(const HugeInt & n, const HugeInt & m)
    {
      HugeInt r;
      HugeInt temp;
      int i, j, t, val;
      
      for(i = 0; i < MAX; ++i)
      {
    	for(j = 0; j < MAX; ++j)
    	{
    	  val = n.numlist[i] * m.numlist[j];
    	  temp.numlist[i + j] += val % 10;
    	  temp.numlist[i + j + 1] += val/10;
    	}
    
    	r = r + temp;
    
    	for(t = 0; t < MAX; ++t)
    	  temp.numlist[t] = 0; 
      }
      return r;
    }
    
    int main()
    {
      HugeInt a(99999);
      HugeInt b(99999);
      HugeInt c;
      c = a * b;
      cout << c << endl;
      return 0;
    }
    I'll have to try Dave Evans' shortened schema.

Page 1 of 2 12 LastLast
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