mulitplication of two huge integers

[faiz]

hi,i have to implement multiplication of two huge integers of 40 or more digits.i've made a function in a class for its implementation but its not working.plz help if u find any logical errors in it.

void HugeInteger::multiplyHugeIntegers(HugeInteger H1,HugeInteger H2)
{
  int carry=0;
  int count=0;          // introduced to place the result in proper place in final answer
  int k;             //index of veryhugeint (the array to store the final result)
  for (int i=max-1;i>=0;i--)
  {
    for (int j=max-1,k=(max+max);j>=0;j--)
    {
      temp[j]=H1.intarray[i]*H2.intarray[j];    //temp[j] and intarray are two int arrays

          temp[j]=temp[j]%10;
          carry=temp[j]/10;
                                                 // veryhugeint is initialized in a constructor in the class
        veryhugeint[k-count-1]+=carry;          //result stored in the final array
      veryhugeint[k-count]+=temp[j];            // result stored in the final array
      count++;
      k--;
    }
  }

.

if you know any other logic or algorithm for its implementation plz reply.thanks

[fulyaoner]

hi,i have to implement multiplication of two huge integers of 40 or more digits.i've made a function in a class for its implementation but its not working.plz help if u find any logical errors in it.

void HugeInteger::multiplyHugeIntegers(HugeInteger H1,HugeInteger H2)
{
  int carry=0;
  int count=0;          // introduced to place the result in proper place in final answer
  int k;             //index of veryhugeint (the array to store the final result)
  for (int i=max-1;i>=0;i--)
  {
    for (int j=max-1,k=(max+max);j>=0;j--)
    {
      temp[j]=H1.intarray[i]*H2.intarray[j];    //temp[j] and intarray are two int arrays
 
          temp[j]=temp[j]%10;
          carry=temp[j]/10;
                                                 // veryhugeint is initialized in a constructor in the class
        veryhugeint[k-count-1]+=carry;          //result stored in the final array
      veryhugeint[k-count]+=temp[j];            // result stored in the final array
      count++;
      k--;
    }
  }

.

if you know any other logic or algorithm for its implementation plz reply.thanks

Some day I completed a similar problem by converting the huge integer to a polynomial.

eg. 123456

1.10^5 + 2.10^4 + 3.10^3 + 4.10^2 + 5.10^1 + 6.10^6

you can read the huge integer to a string - or array of chars.
then from right to left, convert them as a polynomial item.

etc. it goes on like that.

This was just an idea for you to complete properly.

[faiz]

Some day I completed a similar problem by converting the huge integer to a polynomial.

eg. 123456

1.10^5 + 2.10^4 + 3.10^3 + 4.10^2 + 5.10^1 + 6.10^6

you can read the huge integer to a string - or array of chars.
then from right to left, convert them as a polynomial item.

etc. it goes on like that.

This was just an idea for you to complete properly.

i did not exactly understand what you mean by converting to polynomial.if you mean't converting to one integer and then multiplying it then plz do tell me that can the int data type hold a number as large as 40 or more. or you are referring to some thing else.plz explain.

[ft3ssgeek]

It might have helped if you had posted the code for the header file...Are max, temp and intarray member variables of the HugeInteger class? Because if they are not, they are not properly defined and initialized in the function...

It might have helped if you had posted the code for the header file...Are max, temp and intarray member variables of the HugeInteger class? Because if they are not, they are not properly defined and initialized in the function...

Yes, parts of his/her code don't look right.

[faiz]

It might have helped if you had posted the code for the header file...Are max, temp and intarray member variables of the HugeInteger class? Because if they are not, they are not properly defined and initialized in the function...

yes, all temp intarray and veryhugeint are declared in the class. while the max is a global constant variable. i've also made functions of addition, subtraction, and vaious others. all are working fine except multiplication.

const int max=4;
class HugeInteger
{
  private:
    char charray[max];                     //input is in form of string
    int intarray[max];
    int temp[max+10];
    int veryhugeint[max*max];
//-----------------------------------------------------------------------------
  public:
  HugeInteger()
  {                                     //initializing
    for (int i=0;i<max+10;i++)
    {
      temp[i]=0;
    }
    for (i=0;i<max*max;i++)
    {
      veryhugeint[i]=0;
    }
    for (i=0;i<max;i++)
    {
      intarray[i]=0;
    }
  }
//--------------------------------------------------------------------------
    void convert_to_integer()  // the string input converted to intarray  
    {
      for (int i=0;i<max;i++)  
      {
        char ch;
        ch=charray[i];
        switch (ch)
        {
         case '0':intarray[i]=0;break;
         case '1':intarray[i]=1;break;
         case '2':intarray[i]=2;break;
         case '3':intarray[i]=3;break;
         case '4':intarray[i]=4;break;
         case '5':intarray[i]=5;break;
         case '6':intarray[i]=6;break;
         case '7':intarray[i]=7;break;
         case '8':intarray[i]=8;break;
         case '9':intarray[i]=9;break;
        }
      }
    }
//---------------------------------------------------------------------------
    void inputHugeInteger()
    {
      cout << "input huge integer: ";
      cin >> charray;
    }
//---------------------------------------------------------------------------
    void outputHugeInteger()
    {
      cout << "\nthe result is: ";
      for (int i=0;i<max;i++)
      {
        cout << intarray[i];
      }
      cout << endl;
    }
//---------------------------------------------------------------------------
    //prototypes...
    void addHugeIntegers(HugeInteger,HugeInteger);
    void subtractHugeIntegers(HugeInteger,HugeInteger);
    bool isEqualTo(HugeInteger,HugeInteger);
    bool isNotEqualTo(HugeInteger,HugeInteger);
    bool isGreaterThan(HugeInteger,HugeInteger);
    bool isLessThan(HugeInteger,HugeInteger);
    bool isGreaterThanOrEqualTo(HugeInteger,HugeInteger);
    bool isLessThanOrEqualTo(HugeInteger,HugeInteger);
    bool isZero(HugeInteger);
    void multiplyHugeIntegers(HugeInteger H1,HugeInteger H2);
 

}; // end of class

the only header files used are <iostream.h> and <conio.h>.

[faiz]

Yes, parts of his/her code don't look right.

i did'nt understand which part. plz also tell how to correct it...

[iMalc]

If using C++, I offer a solution I have already created for using large numbers. Download bigint.h from:
http://homepages.ihug.co.nz/~aurora76/Malc/Useful_Classes.htm

@faiz

read the following, take out what you need.

http://ozark.hendrix.edu/~burch/proj/karat/index.html

All he seems to be doing, if you ignore the complexity of the karatsuba implementation, is returning the string reversed, putting some zeros on the end, and doing grade school multiplication.

Simple stuff.