Programming knowledge
Contents
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.
Hardware exponentiation
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.
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:
if b = 0:
return 1
if is_even(b):
return a_to_the_b_mod_n((a * a) % n, b / 2, n)
return (a * a_to_the_b_mod_n(a, b - 1, n)) % n