Solved

Multiplication of big integers not working C++

Posted on 2007-12-01
8
297 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
VS2015 compilation and missing DLLs 9 119
Problem to save 10 151
How to split this in C++ 4 94
delete-remove 14 65
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…
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org Go to that link and select download selenium in the right hand columnThat will then direct you to their download page.From that page s…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

863 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

22 Experts available now in Live!

Get 1:1 Help Now