# very large A divide at a very large B

I have already made a function of multiplication of long numbers, addition of long numbers, subtraction of long numbers and division of long numbers. But division takes a very long time, how it could be improved? Here is my code:

        /// removes unnecessary zeros
vector<int> zero(vector<int> a)
{
bool f=false;
int size=0;
for(int i=a.size()-1;i>=0;i--)
{
if(a[i]!=0)
{
f=true;
size=i;
break;
}
}

if(f)
{
vector<int> b(size+1);
for(int i=0;i<size+1;i++)
b[i]=a[size-i];

return b;
}
else
return a;

}
/// a+b
vector<int> sum(vector<int> a,vector<int> b)
{

if(a.size()>b.size())
{
vector<int> rez(3000);
int a_end=a.size()-1;
int remainder=0,k=0,ans;
for(int i=b.size()-1;i>=0;i--)
{
ans=a[a_end]+b[i]+remainder;

if(ans>9)
{
rez[k]=ans%10;
remainder=ans/10;
}
else
{
rez[k]=ans;
remainder=0;
}
k++;
a_end--;
}

int kk=k;
for(int i=a.size();i>kk;i--)
{
ans=a[a_end]+remainder;

if(ans>9)
{
rez[k]=ans%10;
remainder=ans/10;
}
else
{
rez[k]=ans;
remainder=0;
}
k++;
a_end--;
}

if(remainder!=0)
{
rez[k]=remainder;
}

return zero(rez);

}
else
{
vector<int> rez(3000);
int b_end=b.size()-1;
int remainder=0,k=0,ans;
for(int i=a.size()-1;i>=0;i--)
{
ans=b[b_end]+a[i]+remainder;

if(ans>9)
{
rez[k]=ans%10;
remainder=ans/10;
}
else
{
rez[k]=ans;
remainder=0;
}
k++;
b_end--;
}

int kk=k;
for(int i=b.size();i>kk;i--)
{
ans=b[b_end]+remainder;

if(ans>9)
{
rez[k]=ans%10;
remainder=ans/10;
}
else
{
rez[k]=ans;
remainder=0;
}
k++;
b_end--;
}

if(remainder!=0)
{
rez[k]=remainder;
}

return zero(rez);

}

}

/// a & b comparison
int compare(vector<int> a,vector<int> b)
{
if(a.size()>b.size())
return 1;
if(b.size()>a.size())
return 2;

int r=0;

for(int i=0;i<a.size();i++)
{
if(a[i]>b[i])
{
r=1;
break;
}
if(b[i]>a[i])
{
r=2;
break;
}

}

return r;
}

/// a-b
vector<int> subtraction(vector<int> a,vector<int> b)
{

vector<int> rez(1000);
int a_end=a.size()-1;
int k=0,ans;

for(int i=b.size()-1;i>=0;i--)
{
ans=a[a_end]-b[i];

if(ans<0)
{
rez[k]=10+ans;

a[a_end-1]--;
}
else
{
rez[k]=ans;
}
k++;
a_end--;
}

int kk=k;
for(int i=a.size();i>kk;i--)
{
ans=a[a_end];

if(ans<0)
{
rez[k]=10+ans;

a[a_end-1]--;
}
else
{
rez[k]=ans;
}
k++;
a_end--;
}

return zero(rez);

}

/// a div b
vector<int> div(vector<int> a,vector<int> b)
{
vector<int> rez(a.size());
rez=a;
int comp=-1;
vector<int> count(1000);
vector<int> one(1);
one[0]=1;

while(comp!=0 || comp!=2)
{
comp=compare(rez,b);
if(comp==0)
break;

rez=subtraction(rez,b);
count=sum(count,one);
}
count=sum(count,one);
return count;
}

• If it's production code I would use a 3rd party BigInt/BigNumeric lib. I suppose there are some good, optimized library on the internet. – palacsint Nov 27 '11 at 14:08
• @palacsint, thanks, but i want to do it without any libs – Kamil Hismatullin Nov 27 '11 at 14:11
• @KamilHismatullin, don't. Use libs. The only reason not to use an external library is for learning purposes. – Winston Ewert Nov 27 '11 at 15:32
• Echo @WinstonEwert assertion. But do you just want comments on the division or do you want us to comment on the state of the rest of the code. – Martin York Nov 27 '11 at 16:33
• Have you considered breaking down the problem into subproblems involving powers of 2, and then using bit-shifting to perform the bit arithmetic? – user8654 Nov 27 '11 at 23:42

You could try implementing long division.

Example: 13587643180765 / 153483

1) Find first dividend:

13587643180765 / 153483 #1358764 > 153483

2) Divide it by divisor (e.g by repeated subtraction, like you are doing

1358764 / 153483 = 8

3) Find the remainder (could be the result of previous computation)

1358764 % 153483 = 130900

4) Bring down the next digit to the end of the remainder.

13587643180765
1309004

Repeat steps 2-4 until you have reached the last digit in the dividend.

Since 13587643180765 / 153483 = 88528652, it would take that many subtractions your way.

With long division, there's going to be at most 9 * digits_in_quotient subtractions (in step 2), in this case at most 8 * 9 = 72 subtractions (and in fact 8+8+5+2+8+6+5+2 = 44 subtractions)

I would do a binary search on the answer. Roughly: you know a/b is between 0 and a. So just pretend you're looking for the answer in that range. For each guess g, compute the product b*g. If it's bigger than a, try something smaller on your next guess; otherwise, try something bigger on your next guess. The number of multiplications you have to make will be logarithmic in a. I don't think this would be much slower than long division, and conceptually it's much easier (less error-prone).