1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
vector<int> string_to_digits(const string &numstr);
void pause_prog(bool have_newline);
vector<int> divide(vector<int> dividend, vector<int> divisor, int dividend_int, int divisor_int);
int main()
{
string dividend = "";
string divisor = "";
int dividend_int;
int divisor_int;
cout << "Enter a number in binary that will be your dividend." << endl;
cin >> dividend >> dividend_int;
cout << "Enter another number in binary that will be your divisor." << endl;
cin >> divisor >> divisor_int;
vector<int> dividendvec = string_to_digits(dividend);
vector<int> divisorvec = string_to_digits(divisor);
while(dividendvec.size() != divisorvec.size())
{
if(dividendvec.size() > divisorvec.size())
divisorvec.push_back(0);
if(dividendvec.size() < divisorvec.size())
dividendvec.push_back(0);
}
vector<int> quotient;
vector<int> remainder;
quotient, remainder = divide(dividendvec, divisorvec, dividend_int, divisor_int);
cout << "The quotient is: [";
for(int i = 0; i < quotient.size(); i++)
{
if(i>0)
cout << ", ";
cout << quotient[i];
}
cout << "]." << endl;
cout << "The remainder is: [";
for(int i = 0; i < remainder.size(); i++)
{
if(i>0)
cout << ", ";
cout << remainder[i];
}
cout << "]." << endl;
pause_prog(true);
return 0;
}
//To turn the input string into a vector of its digits, in reverse order.
vector<int> string_to_digits(const string &numstr)
{
vector<int> result;
for (int i = numstr.length() - 1; i >= 0; i--)
{
char ch = numstr[i];
if(!isdigit(ch))
return vector<int>();
int digit = ch - '0';
result.push_back(digit);
}
return result;
}
//To leave the window open so the user may view the results.
void pause_prog(bool have_newline)
{
if (have_newline) {
cin.ignore(200, '\n');
}
cout << endl << "Press ENTER to continue." << endl;
cin.ignore(200, '\n');
}
vector<int> divide(vector<int> dividend, vector<int> divisor, int dividend_int, int divisor_int)
{
//q=0 and r=0
vector<int> quotient;
vector<int> remainder;
//Initialization of the vector that will be used for adding one.
vector<int> add_one;
add_one.push_back(1);
for(int i = 0; i < dividend.size(); i++)
{
//q = 2q and r = 2r
cout << "Making it to this stage." << endl;
quotient.insert(quotient.begin(), 0);
remainder.insert(remainder.begin(), 0);
//If x[i] = 1: r = r + 1
if(dividend[i] == 1)
{
cout << "Making it to this secondary stage." << endl;
//Check to make sure that the vectors are the same size and fix it if not.
while(remainder.size() != add_one.size())
{
if(remainder.size() > add_one.size())
add_one.push_back(0);
if(remainder.size() < add_one.size())
remainder.push_back(0);
}
//Initialize the vector to hold the result until it can be put back in remainder and the sum and carry.
vector<int> add_result;
int sum = 0;
int carry = 0;
//Find the sum of the vector and 1.
for(int j = 0; j < add_one.size(); j++)
{
sum = 0;
if(remainder[j] + add_one[j] + carry == 0){
sum = 0;
carry = 0;
add_result.push_back(sum);
}else if(remainder[j] + add_one[j] + carry == 1){
sum = 1;
carry = 0;
add_result.push_back(sum);
}else if(remainder[j] + add_one[j] + carry == 2){
sum = 0;
carry = 1;
add_result.push_back(sum);
}else if(remainder[j] + add_one[j] + carry == 3){
sum = 1;
carry = 1;
add_result.push_back(sum);
}
}
//Add the extra carry at the end if necessary.
if(carry == 1)
add_result.push_back(1);
//Copy the value back into the remainder vector.
remainder = add_result;
}
//If r >= y.
if(remainder.size() >= divisor.size())
{
//If they are the same, simply make the remainder 0.
if(remainder.size() == divisor.size())
{
vector<int> new_remainder;
remainder = new_remainder;
}
if(remainder.size() > divisor.size()){
//Initialize the difference and the vector that will hold the value of the difference until copied into remainder.
int difference;
vector<int> differencevec;
for(int i = 0; i < divisor.size(); i++)
{
if(remainder[i] > divisor[i]){
difference = remainder[i] - divisor[i];
//This is the case that does not require borrowing.
differencevec.push_back(difference);
}else if(remainder[i] < divisor[i]){
remainder[i] = remainder[i] + 2;
//This is the case that does require borrowing.
remainder[i+1] = remainder[i+1] - 1;
difference = remainder[i] - divisor[i];
differencevec.push_back(difference);
}else if(remainder[i] == remainder[i]){
differencevec.push_back(0);
}
}
remainder = differencevec;
}
//q = q + 1
//Check to make sure the quotient and add_one vectors are the same size and fix it if not.
while(quotient.size() != add_one.size())
{
if(quotient.size() > add_one.size())
add_one.push_back(0);
if(quotient.size() < add_one.size())
quotient.push_back(0);
}
//Initialize a vector to hold the sum until it can be copied into quotient and the sum and carry.
vector<int> add_result_2;
int sum = 0;
int carry = 0;
//Find the sum of quotient and 1.
for(int j = 0; j < add_one.size(); j++)
{
sum = 0;
if(quotient[j] + add_one[j] + carry == 0){
sum = 0;
carry = 0;
add_result_2.push_back(sum);
}else if(quotient[j] + add_one[j] + carry == 1){
sum = 1;
carry = 0;
add_result_2.push_back(sum);
}else if(quotient[j] + add_one[j] + carry == 2){
sum = 0;
carry = 1;
add_result_2.push_back(sum);
}else if(quotient[j] + add_one[j] + carry == 3){
sum = 1;
carry = 1;
add_result_2.push_back(sum);
}
}
//Add the extra carry if necessary.
if(carry == 1)
add_result_2.push_back(1);
//Copy the value back into the quotient vector.
quotient = add_result_2;
}
}
return quotient, remainder;
}
|
