A faster way to compute H.C.F. (or G.C.D.) and L.C.M.

A program to compute H.C.F. (also called G.C.D.) and L.C.M. of any two numbers is something which most of the programmers write at very early stage of learning a programming language and is considered a trivial programming task. Most of us follow the basic way by iterating through a range of numbers and checking them for a factor or a multiple and hence computing the desired result. This approach is easy to code but results in an extremely slow program, when dealing with big numbers. In this post I am going to mention about an algorithm which is much faster and easy to code too.

First let's start with computation of H.C.F. for any two numbers. The very first step is to divide the larger number by the smaller number, and then if the remainder obtained is a non-zero value, then divide the divisor (the smaller number in this case) with the obtained remainder (remainder will become the new divisor in this second division). Keep repeating this procedure of dividing the divisor of every division with the obtained remainder, until your obtained reminder becomes zero. Then the last divisor in your last division (the one with zero remainder), is the required H.C.F. value.

NOTE: In a/b, 'a' is the dividend (numerator) and  'b' is the divisor (denominator).

For example, if we want to compute H.C.F. for any two numbers, lets say 1651 and 2032,

As 2032 > 1651, so we will start by dividing 2032 by 1651

NOTE: '%' is symbol for modulus i.e. a%b = remainder obtained on dividing a by b (remainder of a/b).

2032 % 1651 = 381 (381 is the remainder obtained in dividing 2032 by 1651)

1651 % 381 = 127 (1651 was our last divisor, 381 was remainder obtained in last division and 127 is our new obtained remainder)

381 % 127 = 0 (Now we have obtained a zero remainder so we will stop here)

Our last obtained divisor is 127, and is the H.C.F. of 1651 and 2032.

Now, for H.C.F. of three numbers (a,b,c) =  HCF(HCF(a,b),c) [here, HCF(a.b) means H.C.F. value of a and b], and in the similar way we can easily obtain H.C.F. of more than three numbers.

Now I am going to state a better way to obtain L.C.M. of any two numbers, although the technique I mentioned above to compute H.C.F. can be used to compute H.C.F. for more than two numbers too, but the technique to compute L.C.M. which I am going to mention is only limited to two numbers ONLY.

In computation of L.C.M. of two numbers we are going to make use of above mentioned H.C.F. of two numbers technique and going to take advantage of the property -

Product of any TWO numbers = Product of their H.C.F. and L.C.M.

i.e. for any TWO numbers a,b
a*b = [H.C.F. of (a,b)] * [L.C.M. of (a,b)]

hence, L.C.M. of (a,b) = (a*b) / [H.C.F of (a,b)]

Hence using this property, now we can easily compute H.C.F. and L.C.M. of any two numbers in a faster and efficient way.

An optimized approach to compute X^n

In this blog post I am writing about a better way to compute Xⁿ, when X and n both are integers. In most common approach a program can obtain the value of Xⁿ by iterating a loop n times and multiplying  X to some variable, in every iteration. This approach calculates the desired results with complexity of O(n), where n is the power of X,  but here I am going to tell you about an optimized way to do the same task with O(log n).

To obtain this boost in processing, we are going to take benefit of simple property that, when n is an even number, then Xⁿ = (X*X)^(n/2). Now we have to deal with power (n/2) instead of n, similarly at every further iteration the power will reduce to half and we can approach to desired result in logarithmic time complexity (the desired result will be when the power to be computed reduces to 1).

Now if the power to be computed is an odd number, we can simply perform the operation, Xⁿ (n is odd) = X * X^(n-1). As n was odd, so (n-1) is going to be an even number, hence performing the previous step has helped us to obtain an even power of X, and now we can make use of approach stated earlier (in previous paragraph) and can easily compute the desired results in O(log n) time.

Here, I am writing a C++ code for computing Xⁿ  with the above mentioned approach-

int power(int X, int n)
{
/* This function takes input of X as base and n as its power,
and returns the output value of (X ^ n) */

int result = 1;

while(n)
{
if(n%2 == 1) /* Checking for n to be an odd number */
result *= X;

X *= X; /* Squaring the value of X */
n /= 2; /* Reducing the value of n to half */
}

return result; /* Contains the desired computation */
}

A better Prime number generator

Although to write a code for a basic Prime number generator is considered a trivial task, but still ignoring little properties of prime numbers can result in a slow program, especially when dealing with large numbers. In this post I am not going to tell you about any new extra ordinary super complex algorithm to boost up your program, instead I am just going to remind you about some basic properties of prime numbers which many of you would already be knowing, but still don't take their advantage while programming. Although these properties are basic, but with their use one can attain a significant performance improvement in their prime number generator program.

In the most basic approach to write a Prime number generator code, one generally makes use of the necessary and sufficient condition for a number to be prime. As prime number has only two factors, first is '1' and other is the number itself, so in this kind of approach the program checks for a number (let call this number be N) to be prime by checking for the availability its factors, i.e. for every N the program iterates from 2 to (N-1) and checks if the N is divisible by any of the iterator values (or we can say it checks whether any iterator value is a factor of N). Thus if the program fails to find any factor of N (between 2 and N-1), the number N is declared prime.

Optimization 1: The first optimization at this stage can be applied, when we find factors of N in [2, (N-1)] (In above mentioned approach). Instead of searching for factors of N in whole range of [2, N-1], the program should only check for the potential factors in the prime numbers generated previously, i.e. while searching for the factors of N, the program should iterate in the list of previously generated prime numbers only. This approach can be considered as doing prime factorization of the number N, all the consonants themselves are the product of several smaller primes, so rechecking for them to be a factor is kind of redundant step for our purpose, and hence if no prime number P (P < N) is a factor of N, then the number N is a prime number.

Optimization 2: As we all know that 2 is the only even-prime number, so it help us eliminating half of the potential candidates which were going to be tested for being prime. As after 3 no even number is going to be a prime number, so to generate prime numbers up to N the checking of a number for being prime should be done skipping all the even numbers.

Optimization 3: The further improvement can be to reduce the list of smaller prime numbers to be used for testing N as a prime (as stated above in Optimization 1). The program should use only the prime numbers smaller or equal to the square-root of N, while checking N to be a prime number. This technique would be effective since primes larger than the square root of N will be complementary factors of at least one prime less than the square root of N, by this I am trying to say, consider N = p.q and q >= square-root(N), then p should be less then equal to square root of N (i.e. p <= square root(N)).

Optimization 4: The next optimization which I am going to mention seems small, but can still save a significant computation in long run. As we have applied the optimization 2 (mentioned above), we are not going to check any even number further , so when we check for their factors from the list of previously generated prime numbers, no further value of N is going to have '2' as their factor, so we can avoid checking for '2' as their factor.

Ubuntu auto-mute speakers when headphones are plugged in

I was experiencing a problem with ubuntu after upgrading as it was not muting up the main speakers when I was pluging my earphones in my laptop's jack. Sound was coming out from both main speakers and earphones, but recently I found the solution to this problem with little tweaking in the alsa-base configuration file.

you just need to add a little configuration value in 'alsa-base.conf' file and the problem gets solved. To open this file for editing, type the following command in your terminal and provide your system password.

sudo gedit /etc/modprobe.d/alsa-base.conf

then append the below given string at the end of the file and the reboot your system, after saving this to the file.

options snd-hda-intel model=<your_computers_name>

NOTE: replace "<your_computers_name>" with name of your computer (model), for example I have an HP-dv6 so i used  "options snd-hda-intel model=hp-dv5" (without quotes), although I have a dv6 model but the value hp-dv6 was not working, so I used dv5 instead and it worked for me, So you can also try using value for some sibling models, and also keep in mind that REBOOTING IS REQUIRED for the settings to come in action.

After this adjustment, now my main speakers automatically get down when I connect my earphones.