# Dividing Large Numbers using Strings

Page 1 of 1

## 11 Replies - 15998 Views - Last Post: 06 September 2010 - 03:23 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=189261&amp;s=ce09b14976ca2437e7c01911d012af4d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Circuit_Girl

Reputation: 1
• Posts: 34
• Joined: 25-February 09

# Dividing Large Numbers using Strings

Posted 06 September 2010 - 10:53 AM

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.

Is This A Good Question/Topic? 0

## Replies To: Dividing Large Numbers using Strings

### #2 KYA

• g++ jameson.cpp -o beverage

Reputation: 3145
• Posts: 19,185
• Joined: 14-September 07

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 10:59 AM

From the snippet section

• Saucy!

Reputation: 6180
• Posts: 23,882
• Joined: 23-August 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 11:00 AM

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

### #4 Circuit_Girl

Reputation: 1
• Posts: 34
• Joined: 25-February 09

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 11:05 AM

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.

• Saucy!

Reputation: 6180
• Posts: 23,882
• Joined: 23-August 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 11:17 AM

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

### #6 Circuit_Girl

Reputation: 1
• Posts: 34
• Joined: 25-February 09

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 12:28 PM

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?

• Saucy!

Reputation: 6180
• Posts: 23,882
• Joined: 23-August 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 01:22 PM

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

### #8 Circuit_Girl

Reputation: 1
• Posts: 34
• Joined: 25-February 09

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 01:39 PM

```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

### #9 David W

• DIC supporter

Reputation: 281
• Posts: 1,791
• Joined: 20-September 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 01:47 PM

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

### #10 David W

• DIC supporter

Reputation: 281
• Posts: 1,791
• Joined: 20-September 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 02:21 PM

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
// 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

### #11 Circuit_Girl

Reputation: 1
• Posts: 34
• Joined: 25-February 09

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 02:41 PM

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?

### #12 David W

• DIC supporter

Reputation: 281
• Posts: 1,791
• Joined: 20-September 08

## Re: Dividing Large Numbers using Strings

Posted 06 September 2010 - 03:23 PM

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?

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

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