(p^a)^b = p^(a*b) = p^k , where k = a*b and * means, times.

P^x x p^y = p^(x+y) = p^k , where here, k = x+y.

Lesson

Even Number of the Same Base

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

The index, 8 is an even number. There are 7 operations (7 steps) in this mathematical statement (extreme left expression).

Now,

      3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3² x 3² x 3² x 3² = A x A x A x A = A⁴ = (3²)⁴ = 3⁸ = 6561, where A = 3 x 3 = 3² .

but 4 = 2 x 2

∴ 3⁸ = (3²)⁴ = ((3²)²)² = 3⁸ = 6561

i.e. 3⁸ = ((3²)²)² = (3²)⁴ = 3^2x4 with a = 2 and b = 4. Should be programmed recursively, in

((3²)²)² = ((9)²)² = (81)² = 6561 .

There are three operations here, which are the powers: x2x2x2 . So, 7 operations (approximately 8 operations) have been reduced to 3 operations.

So, by dividing 8 (k) by 2 to give 4 and then by 2 to give 2, all the power indexes are obtained, which are the prime number, 2, and for 3 operations.

Here, k = 8.

It is done recursively as follows:

3 x 3 = 9

9 x 9 = 81

81 x 81 = 6561 (three operations, i.e. three steps)

This is because,

      3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3⁸ = 6561

=> 9 x 9 x 9 x 9 = 3⁸ = 6561

=> (9 x 9) x (9 x 9) = 3⁸ = 6561

=> 81 x 81 = 3⁸ = 6561

Odd Number of the Same Base

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁹ = 19683

The index, 9 is an odd number. There are 8 operations (8 steps) in this mathematical statement (extreme left expression).

Now,

      3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁹ = 19683

=> 3 x (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3 x 3² x 3² x 3² x 3² = 3 x A x A x A x A = 3 x A⁴ = 3A⁴ = 3(3²)⁴ = 3 x 3⁸ = 19683, where A = 3 x 3 = 3² .

but 4 = 2 x 2

∴ 3⁹ = 3(3²)⁴ = 3((3²)²)² = 3 x ((3²)²)² = 3 x 3⁸ = 3¹ x 3⁸ = 3¹ x 3^9-1 = 19683

i.e. 3⁹ = 3 x ((3²)²)² = 3¹ x 3⁸ = 3¹ x 3^9-1 with x = 1 and y = 9-1. Should be programmed recursively, in

3 x ((3²)²)² = 3 x ((9)²)² = 3 x (81)² = 19683 .

There are three main operations here, which are 3x and the powers: 2x2x2 . So, 8 operations have been reduced to 3 operations.

Do not forget that, here, k = 9.

Remarks

For an even value of k, choosing a = 2 and b = k/2, thus having p^k = (p^2)^(k/2), will reduce the number of required multiplications considerably. For an odd value of k, choosing x = 1 and y=k-1 will result in y being even, and the same process as for the even case, can then simply be repeated. This allows the definition of a recursive function.

Time complexity

The time complexity for this scheme is O(log₂k), as opposed to the brute-force scheme of O(k).

Code in PHP

The program in PHP uses a recursive function. The program is:

<?php
    function powe($base, $exponent) {
        if ($exponent == 0) {
            return 1;
        } else if ($exponent % 2 == 0) {
            return powe($base * $base, (int)($exponent/2));
        }
        else {
            return $base * powe($base * $base, (int)($exponent/2));
        }
    }

// to call the function
    $k = 8;
    $ret1 = powe(3, $k);
    echo $ret1 . "\n";

    $k2 = 9;
    $ret2 = powe(3, $k2);
    echo $ret2 . "\n";
?>