Optimizing shifts in Knuth long division algorithm

Question

I'm trying to roll out my own Bignum library. Class Bignum stores values in std::vector<uint32_t> v; encoding full little-endian (words/elements of v little-endian, most significant word in v[0]; for example value of 0x1100000003 would be stored as {0x11, 0x3} in v).

Profiling shows two most time-consuming operations for %= operator in my usage, -= and >>=. I can't do much about the first, it's about as optimally written as possible in given scenario, but I should definitely be able to optimize the right-shift in the modulo.

In particular, if I'm using this for RSA, with the classic public exponent of 0x10001 (binary: 10000000000000001) after first subtraction the number (*this) drops by about 15 bits of magnitude, and next bunch of comparisons if ( *this >= r ) return false, the r >>= 1 doing its laps uselessly.

I'd much rather use something similar to int n = SignificantBits() - rhs.SignificantBits(); I use to guesstimate the initial left shift of rhs, but I can't quite wrap my head around how to calculate the value.

In short, if I replace --n; r >>= 1; with n -= x; r >>= x how would I go about calculating the x ?

uint32_t Bignum::SignificantBits() const
{
    return (v.size() == 0)?0:(32*v.size() - __builtin_clz(v[0]));
}

Bignum& Bignum::operator%=(const Bignum &rhs)
{
// irrelevant edge/degenerate case mitigation code stripped, assume *this > rhs

    int n = SignificantBits() - rhs.SignificantBits();
    Bignum r(rhs);
    r <<= n;

    while( n >= 0)
    {
        if ( *this >= r)
        {
            *this -= r;
        }
        --n;
        r >>= 1;
    }

    return *this;
}

Answer 1

Through trial and error more than logical thinking I came up with:

    x = r.SignificantBits() - SignificantBits();
    if(x < 1) x = 1;
    n -= x;
    r >>= x;

It produces correct results and offers about 20% performance gain in my tests. Times in seconds:

                          operator%= : 13.3654134396 //new %=
                     PowMod_improved : 14.0268638200
                          operator^= : 15.1284481500 //old %=
                        PowMod_worse : 17.0191601600