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
  • 28,602
  • 9
  • 56
  • 111

0 Answers0