[Circuit_Girl]

I am trying to preform a task of division of two very large numbers. I want to accomplish this using string manipulation. I have no clue where to begin. I have saw many examples of addition of numbers using strings on the internet. But do not know how to use that code to put it in a division algorithm. I would also like to store the quotient and remainder in strings.

I do not want to do any decimal or negative numbers. My program checks and make sure the dividend is bigger than the divisor too. I the dividend is smaller it outputs quotient 0 with remainder equal to dividend.

Please help with this problem.

[KYA]

From the snippet section

[JackOfAllTrades]

You received a reply in your previous topic. Did you not bother to check that out? Here, I'll even direct you right to the page to which KYA is referring.

EDIT: Shakes fist @ ninja KYA...

This post has been edited by JackOfAllTrades: 06 September 2010 - 11:01 AM

[Circuit_Girl]

JackOfAllTrades, on 06 September 2010 - 10:00 AM, said:

You received a reply in your previous topic. Did you not bother to check that out? Here, I'll even direct you right to the page to which KYA is referring.

EDIT: Shakes fist @ ninja KYA...

I could not get back in it.I am sorry for the double posts.

[JackOfAllTrades]

Click on "My Profile" near the top of the page, then click on "My Topics" in the dropdown.

[Circuit_Girl]

KYA's reply was not what I was looking for.

I have a simple program that ask the user for a dividend and divisor. Then stores them as strings because they are going to be big in size and I want to divide them and store quotient and remainder in another string.

How can this be done in a timely fashion?

[JackOfAllTrades]

In what way is the snippet to which KYA linked insufficient?

[Circuit_Girl]

int main (int argc, char **argv)
{
	string dividend, divisor, difference, a, b, s, tempstring = "";	// a and b used to store dividend and divisor.
	int quotient, inta, intb, diff, tempint = 0;
	char d;

	quotient = 0;

	cout << "Enter the dividend?  ";		//larger number (on top)
	cin  >> a;
	cout << "Enter the divisor?  ";			//smaller number (on bottom)
	cin  >> b;
	
	//making the strings the same length by adding 0's to the beggining of string.
	while (a.length() < b.length())  a = '0'+a;			// a has less digits than b add 0's
	while (b.length() < a.length())  b = '0'+b;		    // b has less digits than a add 0's

	inta = a[0]-'0';						// getting first digit in both strings
	intb = b[0]-'0';

	//if a<b print remainder out (a) and return 0
	if (inta < intb)
	{
		cout << "Quotient: 0 " << endl << "Remainder: " << a << endl;
	}
	else
	{
		a = '0'+a;
	    b = '0'+b;
	    diff = intb;
		//s = b;
	// while ( s >= b )
	 //{
		do
		{
			for (int i = a.length()-1; i>=0; i--)			// do subtraction until end of string
	        {
		    inta = a[i]-'0';					// converting ascii to int, used for munipulation
		    intb = b[i]-'0';	
		    if (inta < intb)					// borrow if needed
		    {
			  a[i-1]--;				    		//borrow from next digit 
			  a[i] += 10;
		    }
		    diff = a[i] - b[i];
		  char d = diff+'0';
		   s = d + s;							//this + is appending two strings, not performing addition.

			}
		 quotient++;
		 a = s;
		// strcpy (a, s);
		} while (s >= B)/>; // fails after deviding 3 x's
	   
    cout << "s string: " << s << endl;
	 cout << "a string: " << a << endl;
	 cout << "Quotient:  " << quotient << endl;
	 //cout << "Remainder: " << s << endl;

	}
	
	system ("pause");
	return 0;
}

I am not sure if this is the right approach. I do not understand the snippet I went to so It is pointless to try to use some of it. I have this so far and it is crashing after subtracting 3 times. Also I think this might take too long with the size of inputs I will have.

I just do not know where to go from here or even if I am headed in the right direction

[David W]

Circuit_Girl, on 06 September 2010 - 01:28 PM, said:

KYA's reply was not what I was looking for.

I have a simple program that ask the user for a dividend and divisor. Then stores them as strings because they are going to be big in size and I want to divide them and store quotient and remainder in another string.

How can this be done in a timely fashion?

That snippet was the 4th in a development series ... that featured using the ease and power of C++ STL strings to hold large integers ...


step 1 was to just add and multiply (large) int's that were 0 or greater (i.e. a class to add and multiply int's stored as strings)


step 2 was an upgrade to handle also (large) int's that were < 0 and to allow subtraction also ...


step 3 was to show a 'bit-shifting' algorithm for division ...

http://www.dreaminco...snippet5529.htm


step 4 was to upgrade the class in step2 to use this 'bit-shifting' for division of large int's ( stored as STL strings )

The latest updates to steps 1, 2 and 4 are maintained here ...

http://developers-he...index.php/topic,426.0.html


So ... a 1st step would be to get some working code that takes in positive int's as C++ STL strings and ADDS those strings ... and then reports the correct sum ( string ) that you desire.

Multiplication can be tackled next ...

Then negative numbers ...

Finally ... division ... once you get a handle on the 'bit-shifting' algorithim and how to apply it here

This post has been edited by David W: 06 September 2010 - 02:09 PM

[David W]

Consider the steps in adding 2 strings (that hold positive large integer values) ...

    friend char sumof( const StrInt& a, int len1, const StrInt& b, int len2, int& carry )
    {
        int sum = a.snum[len1]-'0' + b.snum[len2]-'0' + carry;
        if( sum > 9 ) { sum -= 10; carry = 1; }
        else carry = 0;
        return char( '0' + sum );
    }
    friend char sumof( const StrInt& s, int len, int& carry )
    {
        int sum = s.snum[len]-'0' + carry;
        if( sum > 9 ) { sum -= 10; carry = 1; }
        else carry = 0;
        return char( '0' + sum );
    }

    // uses both friend functions above ...
    // this function returns the sum string of 'a' and 'b' strings
    // by overloading the + operator so that ...
    // a + b will then return a new string holding the sum a+b
    friend StrInt operator + ( const StrInt& a, const StrInt& b )
    {
        int len1 = a.snum.size();
        int len2 = b.snum.size();

        // get ml, the max length of string a and string b
        int ml = (len1 > len2 ? len1 : len2);
        StrInt s;
        s.snum.resize( ml ); // get space to hold partial sums

        int carry = 0; // initial carry to zero ...

        // while char's remain to add together (from right to left)
        while( len1 && len2 )
            s.snum[--ml] = sumof( a, --len1, b, --len2, carry );

        // add in any remaining char's ... 
        // using the appropriate overloaded 'sumof' function
        if( len1 )
            while( len1 )
                s.snum[--ml] = sumof( a, --len1, carry );
        else if( len2 )
            while( len2 )
                s.snum[--ml] = sumof( b, --len2, carry );

        if( carry ) // add in carry if it exists ...
            s.snum = "1" + s.snum;

        return s;
    }

This post has been edited by David W: 06 September 2010 - 02:49 PM

[Circuit_Girl]

How can I make this work for divide? I have no experience overloading operators. What are friend functions? Would subtract be more where I need to explore?

[David W]

Circuit_Girl, on 06 September 2010 - 03:41 PM, said:

How can I make this work for divide? I have no experience overloading operators. What are friend functions? Would subtract be more where I need to explore?

C++ allows overloading ... functions ... and operators ...

This makes your code much easier, once you have the 'overloading code' done.



In the main function, firstly ... I created a C++ class object ... a large int ( as a string ) ...

StrInt s1( "0001234567890123456789" );

This line, when executed, calls the appropriate StrInt class constructor to create a new StrInt object.

That class also defines how to add ... using the '+' operator ...

2 StrInt objects are added together ... so as to yield a new StrInt object that holds the desired sum

A friend function of a class ... is a function that has free access to the private data of that class.

I suspect C++ classes are new to you also ?

So ... study up on

1. function and operator overloading ...

2. class

3. the division method you wish to use ...



Using ...

    friend ostream& operator << ( ostream& os, const StrInt& s )
    { return os << s.snum; }

The above overloads the << operator so that now I may code

...

StrInt s1( "1234567890123456789024680" );
cout << s1 << endl;

and the compiler will 'know' to generate the correct code to 'cout' the StrInt object 's1'

This post has been edited by David W: 06 September 2010 - 04:18 PM