This week we began to learn the C# language. We learned about a couple of fundamental types (int, bool) and a few control flow statements (if, while, for). We also learned about various operators.
To read about these topics, see ch. 1 "Introducing C#", ch. 2 "Data Types" and ch. 4 "Operators and Flow Control" of our Essential C# textbook.
Here is one of the problems that we solved in the tutorial:
Write a program that computes and prints the last 5 digits of the integer 21000.
To solve this, we must compute (21000 mod 10,000). The number 21000 has hundreds of digits and will certainly not fit in a C# int, which has only 32 bits. But we can compute the answer using modular exponentiation, which we also saw when we discussed hash functions in Introduction to Algorithms last semester.
In general, if we want to compute ab mod N, then we have two choices. If we can hold the value ab in a variable, we can compute ab, then take the result mod N. Otherwise, we can loop b times; on each iteration, we can multiply by 'a' and then take the result mod N. The final result will be the same in either case.
In fact, we can make this more general. Suppose that you are going to perform a series of addition, subtraction and multiplication operations, and you want the result mod N. You can first perform all the operations, then take the result mod N. Alternatively, you can take the result mod N after each individual operation. The final result will be the same in either case. Ultimately this is because of this fact: for integers a, b, c, d, N, if a ≡ b (mod N) and c ≡ d (mod N), then a + c ≡ b + d (mod N) and ac ≡ bd (mod N). (You might prove this in a number theory course.)
Here is a solution to the exercise:
int n = 1;
for (int i = 0 ; i < 1000 ; ++i)
n = (2 * n) % 10_000;
Console.WriteLine(n);