1

What is the fastest way for dividing a large natural number by some other natural number?

In the following C++ snippet, I believe that I have implemented a binary-based long division:

Num operator/(const Num& num1,const Num& num2)
{
    Num res = 0;

    Num tmp1 = num1;

    unsigned int tmp1Len = tmp1.BitCount();
    unsigned int num2Len = num2.BitCount();

    while (tmp1Len > num2Len)
    {
        res += (Num)1<<(tmp1Len-num2Len-1);
        tmp1 -= num2<<(tmp1Len-num2Len-1);
        tmp1Len = tmp1.BitCount();
    }

    if (tmp1 >= num2)
        return res+1;

    return res;
}

Class Num supports all the necessary arithmetic operators and logic comparators.

The answer doesn't have to be in C++ (a general method will also be appreciated).

Is there any faster way to do this?

Thanks

barak manos
  • 29,648
  • 10
  • 62
  • 114
  • 1
    [This post](http://stackoverflow.com/questions/17319643/what-is-the-fastest-algorithm-for-division-of-crazy-large-integers) might be somewhat relevant to your question. – Vivek Pradhan Oct 09 '14 at 10:48
  • 1
    Why not use a third-party multi-precision library? – Barmar Oct 09 '14 at 11:00

0 Answers0