Solved

Multiplication of big integers not working C++

Posted on 2007-12-01
8
310 Views
Last Modified: 2013-12-14
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
0
Comment
Question by:urobins
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
8 Comments
 
LVL 13

Expert Comment

by:josgood
ID: 20388809
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.
0
 

Author Comment

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

-U
0
 
LVL 13

Accepted Solution

by:
josgood earned 500 total points
ID: 20388877
To correct the crash,

     currentPosition = thePosition-1; //SIZE-1;
and
          c.numberArray[currentPosition-(thePosition/*SIZE*/-1-thePosition)] = value + '0';

That doesn't result in the correct value, but it does fix the crash.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 13

Expert Comment

by:josgood
ID: 20388920
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;
}
0
 
LVL 13

Expert Comment

by:josgood
ID: 20388941
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;
}
0
 

Author Comment

by:urobins
ID: 20388947
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 :)
0
 

Author Comment

by:urobins
ID: 20388997
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
0
 

Author Closing Comment

by:urobins
ID: 31412111
went above and beyond and really helped me get this problem fixed.
0

Featured Post

Enroll in June's Course of the Month

June's Course of the Month is now available! Every 10 seconds, a consumer gets hit with ransomware. Refresh your knowledge of ransomware best practices by enrolling in this month's complimentary course for Premium Members, Team Accounts, and Qualified Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

691 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question