base:exponentiation

This shows you the differences between two versions of the page.

Last revision Both sides next revision | |||

base:exponentiation [2020-04-25 21:22] verz created |
base:exponentiation [2020-04-25 21:32] verz |
||
---|---|---|---|

Line 2: | Line 2: | ||

This routine computes the exponentiation of a 16 bit value. It handles only integer values. The largest result is 2^32-1 (32 bits); that makes 31 the largest possible exponent. Results larger than 2^32-1 will overflow. | This routine computes the exponentiation of a 16 bit value. It handles only integer values. The largest result is 2^32-1 (32 bits); that makes 31 the largest possible exponent. Results larger than 2^32-1 will overflow. | ||

+ | |||

The algorithm is recursive and at each iteration breaks the exponentiation in a simpler product: if the exponent is even, it will compute the exponentiation with half the exponent and square it, while if it's odd it will compute the product of the value by the value raised at the exponent minus one. The number of multiplications to be computed varies with the exponent, and the maximum is eight for the exponent 31 (31, 30, 15, 14, 7, 6, 3, 2). | The algorithm is recursive and at each iteration breaks the exponentiation in a simpler product: if the exponent is even, it will compute the exponentiation with half the exponent and square it, while if it's odd it will compute the product of the value by the value raised at the exponent minus one. The number of multiplications to be computed varies with the exponent, and the maximum is eight for the exponent 31 (31, 30, 15, 14, 7, 6, 3, 2). | ||

+ | |||

The multiplication algorithm provided is tailored for this routine: it accepts 32bit values and will produce a 32bit result. | The multiplication algorithm provided is tailored for this routine: it accepts 32bit values and will produce a 32bit result. | ||

base/exponentiation.txt ยท Last modified: 2020-06-04 19:36 by verz