Power function

In C/C++ (and also other languages), we have the built in power function to raise a number to a given power. What if we need to calculate the power of a number to 100, like \(2^{100}\)? This is often the case in competitive programming. Maybe we'll run a loop 100 times and calculate it, but this is so inefficient. So, we need to find a power function which can calculate the power to a given number really fast.

Let's consider the expression \(2^{100}\). We can rewrite this to \((2^{50})^{2}\) and the result will not change. Now, we have a smaller power to calculate, right? We can again, rewrite the previous expression to \(((2^{25})^{2})^{2}\). Note that, it was possible to rewrite the expression by halving the power inside the parenthesis only because the power was even. If we were try and rewrite an odd power, it wouldn't be possible. We cannot divide an odd number to half evenly (e.g 25 cannot be divided by 2 evenly). What can we do then? We can just multiply the number itself to balance the power (increase the power by one, to make it odd). Let's rewrite the last expression:
$$
((2^{24+1}))^{2})^{2}
\\ = ((2*2^{24}))^{2})^{2}
\\ = ((2*(2^{12})^{2})^{2})^{2}
$$ The result is still the same. We can go on like this until the power becomes zero. We can see that this pattern keeps repeating and after each step, its calculating a smaller state, its a recursive problem! Here's a picture taken from http://www.shafaetsplanet.com/planetcoding/?p=936 demonstrating the recurring steps.

Implementation in code:

int POW(int x, int p) {
   // x^0 = 1 where x is any number
   if (p == 0) return 1;
   
   // if the power is not even, then multiply the number
   // itself to balance it as stated in the post
   if (p % 2 != 0) {
    int n = POW(x, p/2);
    return x * n * n;
   } else {
    int n = POW(x, p/2);
    return n * n;
   }
}

LightOJ 1000 - Greetings from LightOJ

In this problem, we're asked to just add two input numbers and print them out accordingly. Here's the code.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T, i=1;
  scanf("%d", &T);
  while (T-- > 0) {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("Case %d: %d\n", i++, a+b);
  }
  
  return 0;
}

Enabling gzip compression in django

GZip compression allows the server to compress data before it is sent (on the fly) and the upon arrival of the data on client side, the browser does the unzipping/decompression of the data and shows it to the user. Enabling gzip compression can help you save about 50% plus bandwidth, thus not only making your site more responsive, but also saving huge amount of cost. Here's how you enable gzip compression in Django:

Open your settings.py file and find the MIDDLEWARE_CLASSES tuple. Add the following at the top:

MIDDLEWARE_CLASSES = (
    'django.middleware.gzip.GZipMiddleware',
    # ...
)

And, that's it! You can also enable gzip compression from your Apache, Ngingx and other servers too, look up their documentation.