very large A divide at a very large B [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

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;
}

Answer 1

Your whole big number implementation is probably quite slow. As a general rule, instead of working with base-10, you should probably work with base-2¹⁶ (in a 32bit machine), that is, use half of the bits in each word of the machine.

That ensures that multiplications will not overflow the 32bit registers. Start implementing a normalize function that will normalize the big number (i.e. for each stored digit check whether it overflows the 2¹⁶ and if it does apply the remainder to the next digit). Because the digits have a larger range, you will need fewer memory, and fewer modulo and division operations. Additionally, with the base being a power of 2, the modulo and division operations are much faster than with your base-10 approach.

All operations can then be performed basically element-wise. Addition is reserving one digit more than the larger of the two, then adding digit by digit and finally normalizing the result.

In your division function, it will remove a lot of vector copying. Currently you are creating a vector of 3000 int that gets copied and processed in each iteration of the loop, you might want to consider implementing an in place +=(vector,int) operation that will modify the vector rather than creating a new vector with all the copying.

Answer 2

Your problem is that you are repeatedly subtracting, which means you are running through a very large number of iterations for a large number. This will result in very bad performance.

I was faced with this exact problem at the start of the year (in a uni assignment). I estimated that my original division (using repeated subtraction), would have taken ~100 years to complete. I implemented long division (the same way you divide numbers by hand), and the same calculation took ~5 milliseconds. Not a bad improvement :)

Unfortunately, I hadn't used long division for years, so I had forgotten how to do it. I quickly found the most professional website I could in an attempt to relearn and then implement long division. I used this: http://www.coolmath4kids.com/long-division/long-division-lesson-1.html. Yes, that's right hahaha. The site actually helped. I had my algorithm fixed up within a couple of hours.

Obviously you don't have to use that website, but you have to make your algorithm better. There are more efficient ways of doing this than long division, but I found long division to strike a good balance between efficiency and ease of implementation.

Answer 3

You use a slow division algorithm, and there are fast division algorithm http://en.wikipedia.org/wiki/Division_%28digital%29