Solved

Multiplication of big integers not working C++

Posted on 2007-12-01
8
296 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
  • 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

743 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now