Calculating Large Powers¶

The Problem¶

suppose you want to calculate \(a^n\)

where \(a\) is an integer

and \(n\) is a very large positive integer

e.g. \(a^{65537}\) is often calculated in RSA cryptosystems

Some Special Cases¶

\(a^0\) is 1 if \(a \neq 0\)

\(0^n\) is 0 if \(n \neq 0\)

\(1^n\) is 1 if \(n \neq 0\)

\(a^1\) is \(a\) if \(a \neq 0\)

\(0^0 = 1\) (although sometimes it is said to be undefined)

The Obvious Approach (Iterative)¶

// Pre-condition:
//    n >= 0
// Post-condition:
//    returns a to the power of n, i.e. a^n
// Note:
//    The bases cases can be compressed somewhat. However, we list them
//    individually to make it easier to see that all the cases have been
//    handled.
int power_iter(int a, int n) {
    assert(n >= 0); // check pre-condition

    if (a == 0 && n == 0) return 1;
    if (a == 0 && n != 0) return 0;
    if (a != 0 && n == 0) return 1;
    if (a == 1) return 1;
    int pow = 1;
    for(int i = 0; i < n; ++i) {
        pow *= a;
    }
    return pow;
}

The Obvious Approach (Recursive)¶

int power_recur(int a, int n) {
    assert(n >= 0); // check pre-condition

    if (a == 0 && n == 0) return 1;
    if (a == 0 && n != 0) return 0;
    if (a != 0 && n == 0) return 1;
    if (a == 1) return 1;
    return a * power_recur(a, n - 1);
}

Performance of the Obvious Approach¶

for both the obvious iterative approach and the obvious recursive approach, the performance is as follows

\(a^2 = a \cdot a\) does 1 multiplication

\(a^3 = a \cdot a \cdot a\) does 2 multiplications

\(a^4 = a \cdot a \cdot a \cdot a\) does 3 multiplications

…

\(a^n = a \cdot a \cdot \ldots a \cdot a\) does \(n-1\) multiplications (for \(n > 1\))

in general, this obvious approach does \(n - 1\) multiplications to calculate \(a^n\)

notice that we count multiplications, since that is the key operation here

the number of multiplications is proportional to the running time of the functions

A Faster Algorithm¶

note the following pattern

\(a \cdot a = a^2\)

\(a^2 \cdot a^2 = a^4\)

only 2 multiplications were needed to get \(a^4\)

that’s one less than the obvious algorithm

\(a^4 \cdot a^4 = a^8\), needs only 1 more multiplication for a total of 3: (instead of 7 for the obvious algorithm)
\(a^8 \cdot a^8 = a^{16}\), needs only 1 more multiplication for a total of 4: (instead of 15 for the obvious algorithm)

A Faster Algorithm¶

this shows that “repeated squaring” can be used to calculate \(a^n\) more efficiently than the obvious algorithm

but this only works when \(n\) is a power of 2

can we find a way to make this trick work with any positive \(n\)?

A Faster Algorithm¶

to calculate \(a^{2k}\), we just square \(a^k\) (and recursively calculate \(a^k\))

but for \(a^{2k+1}\), squaring won’t work (because it’s not a perfect square)

however, we could re-arrange it like this: \(a^{2k+1} = a \cdot a^{2k}\)

then we square \(a^k\) and multiply that by \(a\)

A Faster Algorithm¶

int power_recur_fast(int a, int n) {
    assert(n >= 0); // check pre-condition

    if (a == 0 && n == 0) return 1;
    if (a == 0 && n != 0) return 0;
    if (a != 0 && n == 0) return 1;
    if (a == 1) return 1;

    int half = power_recur_fast(a, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return a * half * half;
    }
}

Counting Multiplications¶

lets count how many multiplications power_recur_fast does by adding a global variable called mult_count

int mult_count = 0;

int power_recur_fast(int a, int n) {
    assert(n >= 0); // check pre-condition

    if (a == 0 && n == 0) return 1;
    if (a == 0 && n != 0) return 0;
    if (a != 0 && n == 0) return 1;
    if (a == 1) return 1;

    if (n % 2 == 0) {
        int half = power_recur_fast(a, n / 2);
        mult_count += 1;
        return half * half;
    } else {
        int half = power_recur_fast(a, (n - 1) / 2);
        mult_count += 2;
        return a * half * half;
    }
}

void power_test(int a, int n) {
    mult_count = 0;
    power_recur_fast(a, n);
    cout << a << "^" << n << ", " << mult_count << " multiplications" << endl;
}

Counting Multiplications¶

now run some test code

for(int i = 0; i <= 20; ++i) {
    power_test(2, i);
}

output

2^0, 0 multiplications
2^1, 2 multiplications
2^2, 3 multiplications
2^3, 4 multiplications
2^4, 4 multiplications
2^5, 5 multiplications
2^6, 5 multiplications
2^7, 6 multiplications
2^8, 5 multiplications
2^9, 6 multiplications
2^10, 6 multiplications
2^11, 7 multiplications
2^12, 6 multiplications
2^13, 7 multiplications
2^14, 7 multiplications
2^15, 8 multiplications
2^16, 6 multiplications
2^17, 7 multiplications
2^18, 7 multiplications
2^19, 8 multiplications
2^20, 7 multiplications

the number of multiplications being done is less then for the obvious algorithm (obviously!)

but is there pattern to the number of multiplications?

Counting Multiplications¶

it turns out to be useful to print a message when each part of the if-statement is called

int power_recur_fast(int a, int n) {
    assert(n >= 0); // check pre-condition

    if (a == 0 && n == 0) return 1;
    if (a == 0 && n != 0) return 0;
    if (a != 0 && n == 0) return 1;
    if (a == 1) return 1;

    if (n % 2 == 0) {
        int half = power_recur_fast(a, n / 2);
        mult_count += 1;
        cout << 1;           // print 1
        return half * half;
    } else {
        int half = power_recur_fast(a, (n - 1) / 2);
        mult_count += 2;
        cout << 2;          // print 2
        return a * half * half;
    }
}

void power_test(int a, int n) {
    mult_count = 0;
    power_recur_fast(a, n);
    cout << a << "^" << n << ", " << mult_count << " multiplications"
         << endl;
}

output

can you see a pattern in these values?

Counting Multiplications¶

it is a little easier to see if you change 1s to 0s and 2s to 1s

these are the binary numbers from 1 to 20 (!)

a 0 means 1 multiplication is done

a 1 means two multiplications are done

a number \(n\) has about \(\log_2 n\) bits

at worst, if every bit is a 1, \(2\log_2 n\) multiplications would be done

this is much smaller than the \(n - 1\) multiplications done by the obvious algorithm

Performance¶

so we can say that, in the worst case, the number of comparisons done by the fast recursive power algorithm is proportional to \(\log_2 n\)

multiplication is a key instruction, so that implies that the overall running time is also likely proportional to \(\log_2 n\)

this makes it fast enough in practice to calculate large exponents (such as the RSA cryptosystems example at the beginning)

Note¶

this is an interesting algorithm!

the performance is not at all obvious at first, nor is the connection to binary numbers

you may wonder if this is the fastest way to calculate exponents

the answer is no (!)

for some exponents even fewer multiplications are possible

for example, consider \(2^{15}\)

get \(2^{3}\) in 2 multiplications

then square it to get \(2^{6}\), 1 more multiplication

then square it to get \(2^{12}\), 1 more multiplication

then multiply by \(2^{3}\) to get \(2^{15}\), 1 more multiplication

thus it takes 5 multiplications in total to calculate \(2^{15}\)

but the fast recursive algorithm takes 8 multiplications

Table Of Contents

Previous topic

Next topic

Calculating Large Powers¶

The Problem¶

Some Special Cases¶

The Obvious Approach (Iterative)¶

The Obvious Approach (Recursive)¶

Performance of the Obvious Approach¶

A Faster Algorithm¶

A Faster Algorithm¶

A Faster Algorithm¶

A Faster Algorithm¶

Counting Multiplications¶

Counting Multiplications¶

Counting Multiplications¶

Counting Multiplications¶

Performance¶

Note¶