Wiki source code of Programming knowledge
Version 1.1 by Alexandru Pentilescu on 2025/05/12 09:05
Hide last authors
| author | version | line-number | content |
|---|---|---|---|
 |
1.1 | 1 | (% class="row" %) |
| 2 | ((( | ||
| 3 | (% class="col-xs-12 col-sm-4 col-sm-push-8" %) | ||
| 4 | |||
| 5 | (% class="box" %) | ||
| 6 | ((( | ||
| 7 | **Contents** | ||
| 8 | |||
| 9 | {{toc /}} | ||
| 10 | |||
| 11 | ))) | ||
| 12 | ))) | ||
| 13 | |||
| 14 | (% class="col-xs-12 col-sm-8 col-sm-pull-4" %) | ||
| 15 | ((( | ||
| 16 | (% class="jumbotron" %) | ||
| 17 | ((( | ||
| 18 | (% class="container" %) | ||
| 19 | ((( | ||
| 20 | This page is where I will write all of my various bits of knowledge with regards to programming and software engineering techniques, as well as some math bits that are tangentially related to software development, in one way or another. | ||
| 21 | ))) | ||
| 22 | ))) | ||
| 23 | |||
| 24 | = Hardware exponentiation = | ||
| 25 | When doing expontiation between two integers modulus n, computer hardware optimizes this operation in a way that's not immediately obvious. Normally, one would simply multiply the base by itself by the number of times of the exponent and then do remainder division on the modulus. | ||
| 26 | |||
| 27 | However, it's important to note that this is extremely inefficient and, often times, it's also impractical since the numbers will quickly grow so large that it's difficult for the hardware to properly represent them accurately. The solution to this is the following optimization: | ||
| 28 | |||
| 29 | {{code language="python"}} | ||
| 30 | def a_to_the_b_mod_n(a, b, n): | ||
| 31 | if b = 0: | ||
| 32 | return 1 | ||
| 33 | if is_even(b): | ||
| 34 | return a_to_the_b_mod_n((a * a) % n, b / 2, n) | ||
| 35 | return (a * a_to_the_b_mod_n(a, b - 1, n)) % n | ||
| 36 | {{/code}} | ||
| 37 | |||
| 38 | ))) | ||
| 39 | ))) |