Modular Exponentiation

Yesterday i came through a question where , the user was asked to compute  modulus of exponential value of a number raised to power of a big number.  For example let , b =4,e=13, m =497.  we have  to  find c. where   c = (b^e)%m  .  obviously its time taking   to compute   (b^e).  
Here is the question :   question link

Note that b is only one digit in length and that e is only two digits in length, but the value b^e is 8 digits in length. i.e  b^e   =  67,108,864.   but  what happen  when ,, Consider b = 5 × 10⁷⁶ and e = 17, both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is 2 digits in length, but the value b^e is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably. 

 There are three methods  to compute this value :

1.) first one  is  the basic  one . i.e   calculate b^e and then take its modulus with m .

2.) Memory Efficient : this method requires much more operations than the previous method  but  it is much  better  and less time consuming  than  the previous one . The algorithm for the second one is 

if   c can be expressed as ,  c = a.b ,

 then :

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

The algorithm is as follows:

1. Set c = 1, e′ = 0.
2. Increase e′ by 1.
3. Set c = (b ⋅ c) mod m.
4. If e′ < e, go to step 2. Else, c contains the correct solution to c ≡ b^e mod 'm.

Note that in every pass through step 3, the equation c ≡ b^e′ mod m holds true. When step 3 has been executed e times, then, c contains the answer that was sought. In summary, this algorithm basically counts up e′ by ones until e′ reaches e, doing a multiply by b and the modulo operation each time it adds one (to ensure the results stay small).

The example b = 4, e = 13, and m = 497 is presented again. The algorithm passes through step 3 thirteen times:

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
• e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

The final answer for c is therefore 445, as in the first method.

Try  to  visualize the  solution  step by step on  your  own using the above algorithm .

The time taken  to compute this one  is much less as  compared to  the first method.

3.) Right to left binary method :

This method  is more efficient than above given  two methods as well  It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation). and the number of operations is equal to the number of digits in binary representation  of the exponential .

first of all convert  e  in binary form . i.e for e = 13 , its binary equivalent is 1101 . store this in an array . i.e arr[3] = 1 , arr[2] = 1 , arr[1] = 0, arr[0] = 1 .

The implementation of  this method is as  follows :

set, result=1, and base=b,j=0;  

    while(j<=size of array) 

    {

if(arr[j]==1)

    {

      result = (result * base) % m;

    }

j++;

        base = (base*base)% m;;

    }cout<<result<<endl;

Try  to implement  these methods on  your  own ,  because  that is  the only way  you are gonna learn  things . I am doing the same things ,  share  knowledge, it helps you to learn more and more :) keep coding 

GCD (Greatest Common Devisior) Algorithms :

We All know what Gcd of two numbers is . There are many questions in which we require to implement the Gcd algorithm . There  are many ways to  find Gcd between two numbers . But we prefer those methods which are more efficient .

 The most basic and best method or algorithm is that one to which we all  are familiar . i.e. Euclid's gcd algorithm :
suppose  there are two numbers a and b of which we need to find the Gcd . We  can implement this either by making a recursive function or by making 'for' loops in your program. But generally recursion is  better than making loops . The code for  the Ecluid's  Gcd goes here :

#include <stdio.h>

int gcd_algorithm(int x, int y)
{
    if (y == 0) {
        return x;
    } else  {
        return gcd_algorithm(y, (x % y));
    }
}

int main(void)
{
    int num1, num2, gcd;
    printf("\nEnter two numbers to find gcd using Euclidean algorithm: ");
    scanf("%d%d", &num1, &num2);
    gcd = gcd_algorithm(num1, num2);
    if (gcd)
        printf("\nThe GCD of %d and %d is %d\n", num1, num2, gcd);
    else
        printf("\nInvalid input!!!\n");
    return 0;
}

  tr to understand this by going step by step in the recursion.

NOW TRY TO FIND GCD OF TWO NUMBERS WHEN ONE OF THEM IS EXTREMELY LARGE :

Suppose numbers  are A and B ,  where A can be  upto 10^250 and B upto 40000 . obviously long long int  can't store A . for better understanding of  this  problem  try  :      https://www.codechef.com/problems/GCD2

  

THERE IS A VERY MISCHIEVOUS METHOD FOR STORING SUCH BIG NUMBERS . WE DO SO BY STORING THEM IN AN ARRAY OF INTEGERS .

FOR EXAMPLE THE ABOVE QUESTION  CAN BE DONE  AS :

Time complexity

So what do you mean by time complexity ???

Have you ever wondered why sometimes when you sub,it your code and the online judge gives you an error named TLE (Time Limit Error) ? This is what i am going to explain to you .
Its a simple way of measuring how much time your code or algorithm  is taking to output the result as  per the given input . The time complexity of algorithms is most commonly expressed using the big O notation.

Time Complexity is most commonly estimated by counting the number of elementary functions performed by the algorithm. And since the algorithm's performance may vary with different types of input data, hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that is the maximum time taken for any input size. 

How do we measure it ?? 

While measuring the time complexity of a code , we don't consider the time taken by constants , or variable declaration as they very very less time as  compared to the whole program .

suppose part of a code is :

for(i=1 ; i <=n; i++ )

{

      statement ;

}

this statement will run N times . one time for each value of 'i' 

therefore this part of code will have a time complexity of O(n) .

We try to reduce time complexity of our code as much less as possible. For this we try to use better algorithms , alternate methods of input . Whenever stuck try to google alternate methods of the problem where you are stuck

There are some other time complexities such as O(log(n)) (in trees ) , O(nlog(n)) , O(n^2) (using 2 nested for loops) e.t.c .

So the main aim of every programmer is to reduce the time complexity so as to give a High performance of your code . 

Getting faster inputs

We generally use cin/scanf/getchar for  inputs. Let us talk about a new way of input.

getchar_unlocked()  :

 
 What is  getchar_unlocked () ?
 A function that gets a character from stdin. It returns the next character from stdin. If stdin is at the end of the file, the end of the file indicator is set then getchar_unlocked() returns EOF.
 In short, it is another version of getcha(). It is used only for high and very large inputs as it is not threaded safe.

What do we mean when we talk about thread safety?
A thread is an execution context i.e it is all about execution of events on a computer. Suppose you are using a book and want to take a break right now, but you want to be able to come back and resume the reading from the exact point where you stopped. One way to do so is by writing down the page number, line number and book number.So your execution context for reading book is these 3 numbers. If you have a friend and he is using the same technique,he can take the book while you are no using it, and resume reading from where he stopped.The you can take it back,and resume it from you were.
Threads work the same way. A CPU gives you the illusion that it's doing multiple computation at the same time. It does that by spending a bit of time on each computation. On a technical level, an execution context(thread) consists values of the CPU's registers.

Windows does not support getchar_unlocked() function. because it's thread unsafe. So if you  aren't  using Linux then the only possible way to use this is on an IDE.

Here  is  an example using getchar_unlocked():


The following function can be used to read both +ve and -ve integers using getchar_unlocked().

#include<iostream>
#include<stdio.h>


long long int get_num(long long int &num)
{
     num = 0;
    char c = getchar_unlocked();
    long long int flag = 0;
    while(!((c>='0' & c<='9') || c == '-'))
        c=getchar_unlocked();
    if(c == '-')
    {
        flag = 1;
        c=getchar_unlocked();
    }
    while(c>='0' && c<='9')
    {
        num = (num<<1)+(num<<3)+c-'0';
        c=getchar_unlocked();
    }
    if(flag==0)
        return num;
    else
        return -1*num;
}

int main()
{
  long long int number;
 number = get_num(number);
 printf("%lld\n",number);
}


The working of the function goes like this:
The first while loop keeps repeating until 'c' is given a value of a digit between 0-9 or '-'(in the case of negative numbers).
If we encounter '-', we initialize flag = 1 to make a note that it is a negative number.
The second while loop keeps repeating until 'c' gets a value between 0-9 and stops when any other character is read(Usually it would be a ' '(space) or '\n').
The statement num = (num<<3)+(num<<1)+c-'0'  turns character digit in c to integer digit and is added to num*10 (Left shift operators i.e num << a = num * (2^a) ).
It can also be written as:

num = num*10 + c-'0'
Finally, we return the value of num depending on the value of t flag(whether the number is -ve or +ve).

You can use the above function to read any data type. Just change the data type of the value you're passing into this function to the data type you want to scan.

 Try this question to see the difference between other input methods and getchar_unlcked():
https://www.codechef.com/problems/INTEST


Why do we use different methods of inputs?

In most of the cases, the answer is related to time complexity or the time taken to take the input. The time  is taken by different input methods increases in the following order:

getchar_unlocked < getchar < scanf < cin

The speed difference in scanf and cin is because iostream I/O functions maintain synchronization with the C library I/O functions. We can turn  this off with a call to
std::ios::sync_with_stdio(false); ( do this if you are going to use C++    I/O only).
So until and unless speed factor is too much necessary, or you see some message like
"Warning: Large I/O data"   try to avoid getchar_unlocked 

Starting...

 Those who tell you that learning a language or programming skill  or web development or any field of computer science  is  like a piece  of  cake or an overnight process, are  those idiots who  walk into  glass doors .  So assume it  that you would have to work hard and  give  max of   your time . Just changing your status   and wallpapers won't make you a star . It requires tremendous hard work and  passion to achieve your goals.

First of all you should know all the  basics  of  a programming  language and have a good practice in topics like handling  a loop , checking a condition , working with strings,pointers , matrices,functions etc.

Pick up any competitive coding site . There are many such  sites like Codeforces , a2oj , Uva ,Codechef, Hackerearth , Hackerrank, Spoj , Projecteuler etc.  I would suggest you to use Codeforces/Codchef/Hackerrank  as the questions  present there are conceptual and help you to enhance your coding skills .

Till now i have good practice in C , C++  and currently  learning Java .
Start from the Beginner level . Attempt those questions  first which  have maximum submissions.
Initially you would find it difficult to solve them . There are certain approach and certain tools  for meeting the required constraints of  problems . ......

1.) Taking an Input :

suppose you  have to check 'T' test   cases .
your code should start like this ..
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
    // your code goes here .........
     ........
     ........
     output the result for each test case here like..
     printf("%d\n",answer);
   }
}

About Me

I am  in 2nd semester of my B.tech course and currently pursuing computer science from Thapar University . It has  been 8-9 months  since i  have  started coding and learning  data structures and Algorithms. I try my  best to  give  my  maximum  time to these fields . I love  to  learn  new things be  it music , science , sports , politics or anything . I love to share whatever knowledge i have gained so far . Its very difficult  for you to get over   your problems  and  find proper solutions for them , when  there is  no one other  than internet, to guide you . That's why i am  writing this blog  to help  those who face the same difficulties in  the initial stage  of  coding ....