Notes for lectures
Lectures in next two weeks: 1. Computations modulo P 2. Binary Expo 3. Matrix Expo 4. Gaussian Elimination 5. EV in a chain 6. Berlekamp-Massey (linear rec)
Computations modulo P¶
- How to compute 2^N for huge N? It's slow and some languages don't support so big numbers.
- What about just asking about the last digit of the answer? 2345125235+2394592135*23411111 actually, looking at last digits is enough 517*28 = ....6
- How to compute 10^18 * 10^18 modulo P=10^9 + 7 (maybe mention a need for long long?)
- Today, we will work only with prime modulo, usually, it's P = 10^9 + 7.
- Show code for factorial, including an incorrect one (modulo only at the end)
- Why not 2^32?
- Introduce modulo operator and define it with the remainder (for example 17 mod 5 = 2)
- Say how easy it is to do all operations BUT subtraction is harder.
- Mention CPH https://cses.fi/book/book.pdf
- Mention https://cp-algorithms.com/ and say which topics are easy-medium, the first (binary expo) will be covered in the next lecture, related: modular inverse
- Say about division and probabilities, maybe mention binomial coefficients
- at the end, mention CSES problem set: 2^N https://cses.fi/problemset/task/1617 and trailing zeros in N! https://cses.fi/problemset/task/1618 (the latter requires thinking instead of computing things modulo P)
- idea: maybe make a second video about modular inverse
Gaussian Elimination¶
- pronounce with 's', not 'sh'
- solve a system of two equations
- solve a system of three equations
- talk about matrix representation
- show a general algorithm
- simulate on the same system of three equations
- precision issues, pivot
- usually computed modulo P, same but with modular inverse
- binary version
- example explained here https://en.wikipedia.org/wiki/Gaussian_elimination
- practical programming use https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
- think: does the answer always exist modulo P?
- x * 1000000007 = 5 has a solution for real values, doesn't for P=1e9+7