0
\$\begingroup\$

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;
        }
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – palacsint Nov 27 '11 at 14:08
  • \$\begingroup\$ @palacsint, thanks, but i want to do it without any libs \$\endgroup\$ – Kamil Hismatullin Nov 27 '11 at 14:11
  • 3
    \$\begingroup\$ @KamilHismatullin, don't. Use libs. The only reason not to use an external library is for learning purposes. \$\endgroup\$ – Winston Ewert Nov 27 '11 at 15:32
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin York Nov 27 '11 at 16:33
  • \$\begingroup\$ Have you considered breaking down the problem into subproblems involving powers of 2, and then using bit-shifting to perform the bit arithmetic? \$\endgroup\$ – user8654 Nov 27 '11 at 23:42
3
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.