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