Beginner-2
Bit Manipulation
All the input data given to us, as we know is stored in its binary form in the system’s memory.
Binary Form implies in its equivalent representation in form of bits. There is a lot of cool stuff
which can be done using bits and their manipulations. Have a look at this tutorial :
Another thing to keep in mind is that by default when we talk about bits, we think of base-2
representation, however, there are a number of problems where we can expand similar
concepts to a base-N representation. We can carry out the bit manipulations by using functions
which work for that particular representation and perform tasks akin to the normal bitwise
operators.
For eg, in this question, one way is to create a function which takes a xor of two numbers
with respect to a ternary representation instead of a trivial binary representation.
Can you think of another approach on the same lines but way simpler?
Can you think of another approach on the same lines but way simpler?
Modular Arithmetic
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
The Modulus operator finds a lot of usage in CP, not only to perform the basic REMAINDER
operations but to resolve the ever so bugging problem of data type overflow.
In an ideal world, there would be infinite storage space and multiplication of numbers wouldn’t
lead to arithmetic overflow.But practically that is not possible and instead we have 64-bit (or 32-bit)
sized numbers with native support in most modern computers.This is majorly the reason why
one may have noticed that competitive programming platforms may ask you to compute a
result (modulo p), where p is usually a prime (commonly 10^9 + 7 or 10^9 + 9 ).
Some simple operations in terms of a Modulus are :
Addition : (a+b)%m = ( (a%m) + (b%m) ) %m
Multiplication : (a*b)%m = ( (a%m) * (b%m) ) %m
Subtraction : (a-b)%m = ( (a%m) - (b%m) + m ) %m
Notice the (+m) here, this is because even though a > b , that does not ensure that
(a%m) > (b%m) ( why? ) hence in order to get an answer within our range of [0,m-1] ,
we add a buffer of +m to get a positive result .
Addition, subtraction, multiplication work as they normally would in normal arithmetic
just with an added modulo operation on the final result.
But why use a prime number?
Before we answer this question let us also look at a peculiar problem that arises if we
wish to perform division in modular arithmetic.
Division : (a/b)%m = ( (a%m) * (b-1 % m) ) %m
Here (b-1) is the Inverse Modulo of b wrt to m .
Say we wish to divide 27 by 9 in modular 13 base.
27 (mod 13) = 1 and 9 (mod 13) = 9.
If we were to perform 1/9 (mod 13), we’d get 0 (mod 13) or 0.1111? (mod 13) depending
on preferred typecasting. None of which would give the correct answer 3 (=27/9) (mod 13).
So how do we get around this?
Let’s delve into a bit of Number Theory to answer these two questions.
One of the most popular theorems from Number Theory that finds usage in Computer Science is the Fermat’s Little Theorem:
ap ~= a(mod p)
The proof of this theorem is beyond the scope of this article but we’d highly recommend
you check it out: https://brilliant.org/wiki/fermats-little-theorem/
Fermat’s Little Theorem is a special of Euler’s theorem and holds true if p is a prime number.
One of the direct results we can see from FLT is that if we multiply both sides by ap-2 we’d get:
ap-2 ~= a-1 (mod p)
This is a very powerful result that comes in handy when performing division.
Let’s get back to the problem of division we left unanswered before.
Division 27/9 is essentially multiplication 27*(9-1).
So we can simply perform multiplication of 27 (mod 13) = 1 and 9-1 (mod 13) = 911 (mod 13)
= 31381059609 (mod 13) = 3 (mod 13) which gives 1*3 (mod 13) = 3.
Is our problem solved? Not quite.
Exponentiation : ( a^b ) % m
As you may have noticed exponentiation is not an easy task. If you were to compute 911 normally
you’d probably run into two problems: you variable holding the exponentiated result would overflow,
giving the wrong answer or you’d exceed the time limit because you used an O(n) algorithm for a
large prime like 10^9+7. This where our knowledge of modular exponentiation from the previous
section comes into place.
Modular exponentiation algorithm in the base p enables us to calculate the result in O(log n) time
and without any integer overflow, ergo giving us the correct result.
So there you have it, modular division, plain and simple.
Please Remember: mod m, where m = 0 will give an error
Parting remarks:
You may have noticed, while addition, subtraction, multiplication are essentially O(1) operations,
division is an O(log n) operation. Usually in a contest environment we pre-compute and
store the values of x-1 (mod p) in an array/map beforehand if the range of x is low enough.
This allows us to lookup the value of x-1 (mod p) in O(1) time during the computation.
Contributed by : Himanshu Mundhra , Arpit Jain
Comments
Post a Comment