## Monday, July 13, 2009

### Extended Euclidean Algorithm

Extended Euclidean Algorithm is an extension of standard Euclidean Algorithm for finding the GCD of two integers a and b. It also calculates the values of two more integers x and y such that: ax + by = gcd(a,b); where typically either x or y is negative. This algorithm is generally used to find multiplicative inverse in a finite field, because, if ax + by = gcd(a,b) = 1, i.e. a and be are co-primes, then x is the modular multiplicative inverse of a modulo b, and similarly, y is the modular multiplicative inverse of b modulo a.

This method computes expressions of the form ri = axi + byi for the remainder in each step i of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

By substitution, this gives:

The first two values are the initial arguments to the algorithm:

r1 = a = a(1) + b(0)
r2 = b = a(0) + b(1)

The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.

Example: Compute the GCD of 120 and 23. Or, more formally, compute: x, y, g for 120x + 23y = g; where x, y are two integers and g is the gcd of 120 and 23...

The computation proceeds as follows:
Initial values:
Step 1: Reminder = 120;
Combine terms: 120 = 120 x 1 + 23 x 0

Step 2: Reminder = 23;
Combine terms: 23 = 120 x 0 + 23 x 1

Iterative steps:
Step 3: Quotient = 120 / 23 = 5; Reminder = 120 % 23 = 5;
5 = 120 - 23 x 5
=> 5 = (120 x 1 + 23 x 0) - (120 x 0 + 23 x 1) x 5 ;[from Step 1 and 2]
=> 5 = 120 x 1 + 23 x -5

Step 4: Quotient = 23 / 5 = 4; Reminder = 23 % 5 = 3;
3 = 23 - 5 x 4
=> 3 = (120 x 0 + 23 x 1) - (120 x 1 + 23 x -5) x 4 ;[from Step 2 and 3]
=> 3 = 120 x -4 + 23 x 21

Step 5: Quotient = 5 / 3 = 1; Reminder = 5 % 3 = 2;
2 = 5 - 3 x 1
=> 2 = (120 x 1 + 23 x -5) - (120 x -4 + 23 x 21) x 1 ;[from Step 3 and 4]
=> 2 = 120 x 5 + 23 x -26

Step 6: Quotient = 3 / 2 = 1; Reminder = 3 % 2 = 1;
1 = 3 - 2 x 1
=> 1 = (120 x -4 + 23 x 21) - (120 x 5 + 23 x -26) x 1 ;[from Step 4 and 5]
=> 1 = 120 x -9 + 23 x 47
End of Algorithm.

The last line reads 1 = −9×120 + 47×23, which is the required solution: x = −9 and y = 47, and obviously g = gcd(120,23) = 1

This also means that −9 is the multiplicative inverse of 120 modulo 23, and that 47 is the multiplicative inverse of 23 modulo 120.

−9 × 120 ≡ 1 mod 23 and also 47 × 23 ≡ 1 mod 120.
Algorithm:
By routine algebra of expanding and grouping like terms (refer to the previous example), the following algorithm for iterative method is obtained:
1. Apply Euclidean algorithm, and let qn(n starts from 1) be a finite list of quotients in the division.
2. Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
3. Then for each i so long as qi is defined,
• Compute xi+1= xi-1- qixi
• Compute yi+1= yi-1- qiyi
• Repeat the above after incrementing i by 1.
4. The answers are the second-to-last of xn and yn.
Sample Program:
Here is a sample program written in C++ which implements the Extended Euclidean Algorithm:
`#include <stdio.h>/*Takes a, b as input.Returns gcd(a, b).Updates x, y via pointer reference.*/int Extended_Euclid(int A, int B, int *X, int *Y){    int x, y, u, v, m, n, a, b, q, r;     /* B = A(0) + B(1) */    x = 0; y = 1;     /* A = A(1) + B(0) */    u = 1; v = 0;     for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n)    {        /* b = aq + r and 0 <= r < a */        q = b / a;        r = b % a;         /* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */        m = x - (u * q);        n = y - (v * q);     }        /* Ax + By = gcd(A, B) */    *X = x; *Y = y;     return b;}int main(){    int a, b, x, y, g;    scanf("%d %d", &a, &b);    g = Extended_Euclid(a, b, &x, &y);    printf("X = %d; Y = %d; G = %d\n", x, y, g);    return 0;}`

Python implementation:
`def Extended_Euclid(a, b):    x, last_x = 0, 1    y, last_y = 1, 0     while b:        quotient = a / b        a, b = b, a % b        x, last_x = last_x - quotient*x, x        y, last_y = last_y - quotient*y, y     return (last_x, last_y, a)`

For complete reading, click here. It is also useful to have a look at the Chinese Remainder Theorem.

Hope this will help...

## Sunday, July 12, 2009

### Largest impossible score

Problem:
If two possible points in a game is p and q, what is the largest impossible score of the game which can't be achieved? Or it can't be determined? In other words, for integers p, q ≥ 0, what is the maximum number m which can't be written as a linear combination of p, q, i.e. px + qy, where, x, y ≥ 0.

Solution:
The score can only be determined when p and q are co-primes, i.e. g = GCD(a,b) = 1. Otherwise, we can only make the multiples of g and the remaining numbers can't be made which means the maximum number can't be determined, or infinite! This also covers the case if exactly one of p or q is 0.

One other required condition is p,q > 1. If anyone of p or q is 1, there is no such score which can't be achieved, i.e. answer will be 0. If p and q both are 0, we can't even make any score...

Now, we can arrange the numbers from 0 to p*q-1 in a rectangular array as follows:
`   0         1        .......       q-1   q        q+1       .......       2q-1  ...       ...       .......       ...  ...       ...       .......       ...(p-1)q   (p-1)(q-1)   .......       pq-1`

For example, if p = 3 and q = 7, we have the following table:
`(0)    1     2   (3)   4     5   (6) 7     8    (9)   10   11   (12)  13 14   (15)   16   17  (18)   19   20`

We have circled the multiples of p in the above table and claim these observations:

• There will be q circled numbers. As we have exactly p numbers in each of q columns, so each column will have exactly one circled number, i.e. multiple of p, which implies, there will be a total of q circled number in this table.

• No two circled numbers are in same same column and there will be only one circled number in any column. For the same reason stated above, exactly one circled number in each column.

• Any circled number is possible. This is trivial, because, the circled numbers are multiple of one of the two given numbers, i.e. in the form p*x + q*0 or p*0 + q*x.

• Any number below the circled one in the same column is possible. We have seen any circled number is possible. A circled number is the first multiple of p in the respective column, i.e. n*p, where n ≥1, so the following numbers in the column will be: n*p + q, n*p + 2*q. n*p + 3*q, ... ... ... which are always possible.

• Any number above the circled one in the same column is impossible. This is also explained in the previous step. As any circled number in a column is the first one which is a multiple of one element, the number above this one will be neither the multiple of any of the two numbers. So it is impossible.

• Any number ≥ p*q is possible. As we complete p rows of the table with q columns, we already have one circled number in each column, so, any number > p*q-1 (i.e. the last element of the table) will be surely following any of the q circled numbers, so any number starting from the p+1th row, starting from p*q will be possible.

Now considering all these observations, we can see that, largest impossible number is the number just above the last circled number. The last circled number is p*q-p, i.e. 21-3 = 18 and number above it is (p*q-p)-q, i.e. 18-7 = 11. So in general, largest impossible number is: p*q - p - q.

Conclusion:
If you are given p, q :: two positive numbers, the largest number, m, which can't be expressed as a linear combination of p, q i.e. in the form px + qy, where x and y are two non-negative numbers, is p * q - p - q, when p, q > 1 and GCD(p, q) is 1 i.e. p, q are co-primes.

## Friday, July 10, 2009

### Binary GCD algorithm

Here is a sample code for calculating GCD bitwise:
`typedef unsigned int ui;ui gcd(ui u, ui v){    ui shift, diff;        if (u == 0 || v == 0)        return u | v;        /* Let shift := lg K,    where K is the greatest power of 2 dividing both u and v. */    for (shift = 0; ((u | v) & 1) == 0; ++shift)    {        u >>= 1;        v >>= 1;    }        while ((u & 1) == 0)        u >>= 1;            /* From here on, u is always odd. */    do {        while ((v & 1) == 0)            v >>= 1;                    /* Now u and v are both odd, so diff(u, v) is even.        Let u = min(u, v), v = diff(u, v)/2. */        if (u < v)            v -= u;        else        {            diff = u - v;            u = v;            v = diff;        }        v >>= 1;        } while (v != 0);        return u << shift;}`

Actually, this algorithm outperforms the basic euclidean algorithm, so their asymptotic performance are same. According to Wikipedia, it is sometimes 60% faster than normal euclidean algorithm [proven].

But who needs it when he can do the following:
`int gcd(int a, int b){    while(b) b ^= a ^= b ^= a %= b;    return a;}`

Stunned? oh that's normal...

## Thursday, July 9, 2009

### Craziest Language Ever !!!

Just have a look at these programming languages... They are really crazy as their names.
These are called esoteric programming languages.

## Wednesday, July 8, 2009

### Factorial of negative number

Is it possible to find factorial of negative numbers?

By definition,
N! = 1 x 2 x .... x N
⇒ N! = 1 x 2 x .... x N x (N+1) / (N+1)
⇒ N! = (N+1)! / (N+!)

Now, let's try some values:
3! = 4! / 4 = 6
2! = 3! / 3 = 2
1! = 2! / 2 = 1
0! = 1! / 1 = 1

So, that's how 0! = 1. Let's not stop at 0!, if we continue this fashion, we get:
(-1)! = 0! / 0 = Undetermined

Many people still keeps arguing about whether x / 0 = +∞ or Undefined, it really doesn't matter though, because it is well established that anything divided by zero is undefined.

However, in this post, we are going to talk about a problem from UVa Online Judge, UVa-10323 (Factorial! You Must be Kidding!!!). This problem actually requires you to calculate even the factorials of negative numbers, which does not really exist in real world.

In this context, we are forced to assume that x / 0 = +∞. There was a mistake on my previous post, this section is updated as per the comment from a fellow reader আহনাফ তাহমিদ:
(-1)! = 0! / 0 = +∞
(-2)! = (-1)! / -1 = -∞
(-3)! = (-2)! / -2 = +∞
(-4)! = (-3)! / -3 = -∞
(-5)! = (-4)! / -4 = +∞
and so on..

Hence, we can see that, if N is odd, then (-N)! = +∞, otherwise (-N)! = -∞. Note that, this specific problem statement calls +∞ as Overflow and -∞ as Underflow.

Hope it helps!

## Tuesday, July 7, 2009

### Easy problems at UVA OJ

Here are some suggestion about some very easy problems on UVA Online Judge

Programming is fun!!! especially for the beginners, and new programmers find a great inspiration on solving easy problems first as these problems are good for learning the ropes. To help some of my new friends i.e. new programmer friends who intend to solve problems on UVA OJ, here is a list of very easy problems.

Some problems among these may not seem so easy at a first glance, but after a little thinking, they will be easily solved. These problems will also help you to understand common programming techniques along with the verdict variations.

136 very easy problems for beginners:

## Monday, July 6, 2009

### Negative Base Number System

Negative-base systems can accommodate all the same numbers as standard place-value systems; but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations. The need to store the "information" normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.

The common names for negative-base positional numeral systems are formed by prefixing nega- to the name of the corresponding positive-base system; for example, negadecimal (base -10) corresponds to decimal (base 10), negaternary (base -3) to ternary (base 3), and negabinary (base -2) to binary (base 2).

Denoting the base as − r, every integer a can be written uniquely as:

where each digit dk is an integer from 0 to r − 1 and the leading digit dn is > 0 (unless n=0). The base r expansion of a is then given by the string dndn-1.....d1d0.

Calculation:

The base r expansion of a number can be found by repeated division by r, recording the non-negative remainders of 0,1,2,.........,r-1; and concatenating those remainders, starting with the last. Note that if a / b = c, remainder d, then bc + d = a. For example, 146 in negaternary:
`146 / -3 = -48; reminder = 2-48 / -3 =  16; reminder = 0 16 / -3 =  -5; reminder = 1 -5 / -3 =   2; reminder = 1  2 / -3 =   0; reminder = 2`

Therefore, the negaternary expansion of 146 is 21102.

Note that in most programming languages, the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder; to get the correct result in such case, computer implementations of the above algorithm should add 1 and r to the quotient and remainder respectively.

The numbers -15 to 15 with their expansions in a number of positive and corresponding negative bases are:

Decimal Negadecimal Binary Negabinary Ternary Negaternary
-15 25 -1111 110001 -120 1220
-14 26 -1110 110110 -112 1221
-13 27 -1101 110111 -111 1222
-12 28 -1100 110100 -110 1210
-11 29 -1011 110101 -102 1211
-10 10 -1010 1010 -101 1212
-9 11 -1001 1011 -100 1200
-8 12 -1000 1000 -22 1201
-7 13 -111 1001 -21 1202
-6 14 -110 1110 -20 20
-5 15 -101 1111 -12 21
-4 16 -100 1100 -11 22
-3 17 -11 1101 -10 10
-2 18 -10 10 -2 11
-1 19 -1 11 -1 12
0 0 0 0 0 0
1 1 1 1 1 1
2 2 10 110 2 2
3 3 11 111 10 120
4 4 100 100 11 121
5 5 101 101 12 122
6 6 110 11010 20 110
7 7 111 11011 21 111
8 8 1000 11000 22 112
9 9 1001 11001 100 100
10 190 1010 11110 101 101
11 191 1011 11111 102 102
12 192 1100 11100 110 220
13 193 1101 11101 111 221
14 194 1110 10010 112 222
15 195 1111 10011 120 210

Note that the base r expansions of negative integers have an even number of digits, while the base r expansions of the non-negative integers have an odd number of digits.

Program for calculating Negabinary

In python:

`def negabinary(i):    digits = []      while i != 0:        i, remainder = divmod(i, -2)        if remainder < 0:            i, remainder = i + 1, remainder + 2        digits.insert(0, str(remainder))    return ''.join(digits)`

In C++:
`string negabinary(int i){    int reminder;    string digits;    while(i != 0)    {        reminder = i % -2;        i /= -2;        if(reminder < 0)        {            i++;            reminder += 2;        }        digits.push_back(reminder+'0');    }    reverse(digits.begin(),digits.end());    return digits;}`

The same procedure it to be followed for calculating other negative number system.

### 0.99999999................... = 1

Wanna see the proof? Check it out.... Let's assume,
```Let, x = 0.99999999999999.......................
=> 10x = 9.99999999999999.......................
=> 10x = 9 + 0.99999999999999...................
=> 10x = 9 + x
=>  9x = 9
=>   x = 1
So, 0.99999999999999............................ = 1
```
Is anything going wrong here?