Example 2
Calculate f(x) = m256
Using the normal method
f(x) = m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m
m×m×m×m×m×m×m×m×m×m×m×m×m×m×m×m = m256.
Notice that each row has 16 operands of m and we have a total of 16 rows
therefore we have a total of
16×16 = 256 operands of m. We also have 255 (256-1) multiplication
operations. To get the number of multiplication operations, subtract one
from the total number of operands. 255 multiplication operations is
unacceptably large and a more efficient method ought to be used instead.
Let us use the ngazi method to calculate the function f(x) =
m256
The ngazi method
Calculate f(x) = m256
f(x)= m×m = m2.
m2×m2 = m4
m4×m4 = m8
m8 ×m8 = m16
m16×m16 = m32
m32×m32 = m64
m64×m64 = m128
m128×m128 = m256
Thus we have used only eight multiplication operations instead of the
255 multiplication operations that we used in the normal calculation.
Therefore, this new method of exponential function calculation is
extremely efficient. Let us calculate how efficient the calculation of
the second example was. We used only 8 multiplication operations instead
of 255 multiplication operations and the difference between the two is
255-8 = 247. Therefore, we have reduced the number of multiplication
operations by 247. Therefore, in percentage terms we have reduced
inefficient multiplication operations by 247÷255×100= 96.86%. This is
an extremely impressive level of improvement in efficiency. This
improvement can be increased up to 99% for very large exponent values.
I will give an example of such a large exponent value with the following
function f(x) = m65536 however due to space
constraints, I will not list the 65,535 multiplication operations
because that will fill several pages of paper. I will jump straight to
the ngazi method.
The ngazi method