Link to home
Start Free TrialLog in
Avatar of urobins
urobins

asked on

Multiplication of big integers not working C++

I am working on an assignment for class where I had to create a class to accept an integer of upto 40 places.  I ahve to be able to add subtract and multiply as well as determine if they are equal or not.  I have addition and subtraction working.  I started working on multiplication but I am having problems can someone take a look and let me know what I might be doing wrong?  It is crashing the program.

#include"HugeInteger.h"
#include<iostream>
#include<string>
const int SIZE = 40;

using namespace std;

HugeInteger::HugeInteger()
{
     setHugeInteger();
     errorFlag = false;
}

//read in value from the user to set huge integer
void HugeInteger::enterHugeInteger()
{
     
     char userInput [SIZE+1];
     bool notNumber  = false;
     int i = 0;
       
     cin.getline( userInput, sizeof userInput );

     
     cin.sync();
     cin.clear();

     //see if the string entered is an unsigned integer
     while(i < strlen(userInput)-1)
     {
          if (!isdigit(userInput[i]))
               notNumber = true;
          i++;
     }

     if (!notNumber)
     {
          i = strlen(userInput);

          while(i >= 0)
          {
             numberArray[SIZE-strlen(userInput)+i] = userInput[i];
             i--;
          }
     }
}

void HugeInteger::setHugeInteger()
{
     for (int i = 0; i < SIZE; i++)
          numberArray[i] = '0';
     numberArray[SIZE] = '\0';
}

int HugeInteger::theLength()
{
      int i;
     for ( i = 0; i < sizeof numberArray-2; i++) //the last 0 is significant
     {                                             //so preserve it
          if( numberArray[i] == '0');
          else
               break;
     }
     return i;
}


void HugeInteger::print()
{
     for (int x = theLength();  x < sizeof numberArray; x++)
          cout << numberArray[x];
}

void HugeInteger::addition (HugeInteger a,HugeInteger b)
{
     int currentPosition = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int temporarySum = 0;
     int value = 0;
     int carry = 0;

     currentPosition = SIZE-1;

     while (currentPosition >= 0)
     {
          currentValueB = b.numberArray[currentPosition]-'0';
          currentValueA = a.numberArray[currentPosition]-'0';
          temporarySum = currentValueA + currentValueB + carry;
          carry = temporarySum/10;
          value = temporarySum%10;
          numberArray[currentPosition] = value + '0';
          currentPosition--;
     }

     if (carry > 0)
     {
          setHugeInteger();
         errorFlag = true;
     }
}

void HugeInteger::subtraction (HugeInteger a,HugeInteger b)
{
     int currentPosition = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int value = 0;
     int borrow = 0;

     currentPosition = SIZE-1;

     while (currentPosition >= 0)
     {
          currentValueB = b.numberArray[currentPosition]-'0';
          currentValueA = a.numberArray[currentPosition]-'0';

          value = currentValueA-currentValueB+borrow;
          if (value < 0)
          {
               value += 10;
               borrow = -1;
          }
          else
               borrow = 0;

          numberArray[currentPosition] = value + '0';
          currentPosition--;
     }

     if (borrow < 0) // an underflow has occurred
     {
          setHugeInteger();
         errorFlag = true;
     }
}

void HugeInteger::multiplication (HugeInteger a, HugeInteger b)
{
     int currentPositiona = 0;
     int currentPositionb = 0;
     int theDigit = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int n = 0;
     int value = 0;
     int carry = 0;
     HugeInteger c,d;

     currentPositionb = SIZE-1;
     while (currentPositionb >= 0)
     {
          theDigit = b.numberArray[currentPositionb]-'0';
         c = c.multiplicationHelper(a,theDigit,currentPositionb);
        d.addition(d,c);
          currentPositionb--;
     }

     for (int i = 0; i < sizeof numberArray - 1; i++)
          numberArray[i] = d.numberArray[i] ;
}

HugeInteger HugeInteger::multiplicationHelper (HugeInteger a, int theDigit, int thePosition)
{
     int currentPosition = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int temporaryMultipliedValue = 0;
     int value = 0;
     int carry = 0;
     HugeInteger c;

     currentPosition = SIZE-1;
     while (currentPosition >= 0)
     {
          currentValueB = theDigit;
          currentValueA = a.numberArray[currentPosition]-'0';
          temporaryMultipliedValue = currentValueA * currentValueB + carry;
          carry = temporaryMultipliedValue/10;
          value = temporaryMultipliedValue%10;
          c.numberArray[currentPosition-(SIZE-1-thePosition)] = value + '0';
          currentPosition--;
     }
     if (carry > 0) // an overflow has occurred
     {
          c.setHugeInteger();
          c.errorFlag = true;
     }    
     return c;
}

----------------------
#pragma once

#ifndef HugeInteger_H
#define HugeInteger_H

class HugeInteger
{
public:
     HugeInteger();
     int theLength();
       void enterHugeInteger();
     void print();
     void addition (HugeInteger,HugeInteger);
     void subtraction (HugeInteger,HugeInteger);
     void multiplication (HugeInteger,HugeInteger);
     HugeInteger multiplicationHelper (HugeInteger a, int theDigit, int thePosition);
     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);

 private:
       void setHugeInteger();
     char numberArray[41];
     bool errorFlag;
     
};

#endif
Avatar of josgood
josgood
Flag of United States of America image

On the second entry to HugeInteger::multiplicationHelper, thePosition==38, but the loop runs from 39 to 0.  On the last iteration
   currentPosition-(SIZE-1-thePosition)  evaluates to -1
so
   c.numberArray[currentPosition-(SIZE-1-thePosition)] is out of range and thus you get the exception.
Avatar of urobins
urobins

ASKER

so I shouldn't be subtracting the position or shouldn't be using size -1?  Sorry the math worked out in my head :)

-U
ASKER CERTIFIED SOLUTION
Avatar of josgood
josgood
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
This version of multiplicationHelper works for the one's place digit.

I believe that in

HugeInteger HugeInteger::multiplicationHelper (HugeInteger a, int theDigit, int thePosition)
{
     int currentPosition = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int temporaryMultipliedValue = 0;
     int value = 0;
     int carry = 0;
     HugeInteger c;

     currentPosition = thePosition; //SIZE-1;
     while (currentPosition >= 0)
     {
          currentValueB = theDigit;
          currentValueA = a.numberArray[currentPosition]-'0';
          temporaryMultipliedValue = currentValueA * currentValueB + carry;
          carry = temporaryMultipliedValue/10;
          value = temporaryMultipliedValue%10;
          c.numberArray[currentPosition/*-(SIZE-1-thePosition)*/] = value + '0';
          currentPosition--;
     }
     if (carry > 0) // an overflow has occurred
     {
          c.setHugeInteger();
          c.errorFlag = true;
     }    
     return c;
}
This version of multiplicationHelper seems to work for small numbers.  Note the
     for (int i = thePosition; i < SIZE-1; i++) theDigit *= 10;
This approach only works for small numbers, but illustrates what you need to do for large numbers -- shift the value left the right number of decimal places.

HugeInteger HugeInteger::multiplicationHelper (HugeInteger a, int theDigit, int thePosition)
{
     int currentPosition = 0;
     int currentValueA = 0;
     int currentValueB = 0;
     int temporaryMultipliedValue = 0;
     int value = 0;
     int carry = 0;
     HugeInteger c;

     currentPosition = SIZE-1;
     for (int i = thePosition; i < SIZE-1; i++) theDigit *= 10;
     while (currentPosition >= 0)
     {
          currentValueB = theDigit;
          currentValueA = a.numberArray[currentPosition]-'0';
          temporaryMultipliedValue = currentValueA * currentValueB + carry;
          carry = temporaryMultipliedValue/10;
          value = temporaryMultipliedValue%10;
          c.numberArray[currentPosition/*-(SIZE-1-thePosition)*/] = value + '0';
          currentPosition--;
     }
     if (carry > 0) // an overflow has occurred
     {
          c.setHugeInteger();
          c.errorFlag = true;
     }    
     return c;
}
Avatar of urobins

ASKER

Thanks, I'll take a look at this and see if I can figure it out thanks!  Math has always been my weak point.  Good thing I don't plan on doing this for a living :)
Avatar of urobins

ASKER

Okay I think I understand that, I am going to keep working on it, it seems to be behaving right now.  I really appreciate your helP
Avatar of urobins

ASKER

went above and beyond and really helped me get this problem fixed.