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.
  1. Brainf**k
  2. Intercal
  3. Whitespace
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:



105 119 136 138 145 154 190 200
256 264 272 278 294 332 344 355
362 374 378 382 389 394 401 409
412 412 414 417 422 424 426 438
441 444 445 455 458 460 465 466
468 474 476 477 478 482 483 484
486 489 490 492 494 495 496 498
499 530 535 543 568 573 575 579
583 587 591 621 713 834 900 944
974 10006 10008 10013 10018 10019 10035 10055
10060 10071 10078 10079 10093 10104 10110 10161
10195 10209 10221 10242 10281 10297 10302 10323
10340 10347 10407 10432 10451 10469 10490 10499
10515 10522 10533 10573 10591 10678 10679 10683
10783 10784 10790 10812 10815 10922 10929 10931
10991 11058 11121 11152 11172 11192 11192 11219
11220 11233 11332 11343 11388 11417 11437 11455



Good Luck !!!



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.

Source: Wikipedia


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?