Euclid's GCD Algorithm

Before turning our head to Euclid's algorithm for calculating GCD, let's cover the more fundamental approach to calculate GCD.

GCD (Greatest Common Divisor)

GCD of two integers A and B is the largest integer that divides them both without a remainder. It is also known as GCF(Greatest Common Factor), HCF(Highest Common Factor) and GCM(Greatest Common Measure).

So GCD(A, B) will be between 1 and min(A, B), both inclusive. So it can be implemented as shown below:

 public int gcd(int a, int b) {

   for (int i = Math.min(a, b); i > 1; i--) {

     if (a % i == 0 && b % i == 0) {

       return i;

     }

   }

   return 1;

 }

Euclid's Algorithm

Above algorithm is not very efficient, as in worst case it can end up doing min(a,b) modulo operations. Euclid's or Euclidian algorithm is an efficient algorithm for calculating GCD of two numbers. And due to its efficiency and simplicity, it is one of the oldest numerical algorithms which is still in use. This algorithm iterates over the two numbers until the remainder is 0. 

To calculate GCD,

Express first in terms of the second number i.e. A = B*K + C

Now repeat the operation for K and C (until C is 0)

The last non-zero remainder is GCD. 

GCD(18,12) => 18 = 12*1 + 6

GCD(6,1)    =>  6 = 1*6 + 0

GCD = 6

Recurrence relation would be:

GCD(A,0) = A

GCD(A,B) = GCD(B, A mod B), for B>0

Implementation

Recursive implementation is quite trivial:

public int euclidGcd(int a, int b){

  if(b ==0 ) return a;

  return euclidGcd(b, a%b);

}

--
keep coding !!!

Lambda Expression in Java 8

Let's go functional!

Lambda Expression (Closure or Anonymous method) is one of the most important additions to Java 8.  In fact, it's the most incredible additions to language in its history; it is going to change the way we write programs in Java.  With this new feature, Java adds one of the modern programming technique, Functional Programming.

This is useful for Functional Interfaces (the interface that requires exactly one method to be implemented). Runnable, Callable, Comparable and other interfaces which just have a single method are called functional interfaces. You can even define your own interface with a single method to unleash the power of Lambdas.

Syntax of Lambda

Lambda consists of 3 parts :

1. Parenthesized set of parameters
2. Arrow sign ( -> )
3. Body in form of single expression or a block 

i.e. (Parameter1 p1, Parameter2 p2)            ->                           { }
       (parameters)                                   (arrow sign)          (method body)

Properties:

• It doesn't have an explicit name for the method, so it's called an anonymous method as well
• It can throw Exceptions
• It's more like a method (and not a class), it has a list of parameter, body and return type
• It can be passed as an argument to a method and can be stored as a value in a variable

Runnable Implementation without Lambdas

Before going all out on Lambda. Let's see how these interfaces get implemented without it.

Approach 1: Implement the interface

public class MyRunnableImpl implements Runnable{
     @override
     public void run(){
         //TODO: Implementation
     }
}

Approach 2: Using anonymous (inner) class
   

Runnable task = new Runnable(){

    public void run(){

       //TODO: Implementation

   }

};

Approach 2 is better than first but still, it's quite verbose and there is hardly any scope of reusability.

Implementing functional interfaces through Lambda

The compiler knows beforehand that the Runnable interface has only one method to be implemented. So this lack of ambiguity around which method needs to be implemented helps in making the Runnable implementation more compact and efficient using lambdas. 

So using Lambda; above code can be replaced as :

Runnable task = () -> System.out.println("inside run method");
or 
Runnable task = () -> { System.out.println("inside run method"); };

And on similar lines you can implement Callable as well :

Callable<Integer> task = () -> {

       Random r = new Random(101);

       return r.nextInt(101);

};

If the method takes some argument, then they get passed inside parentheses. Let's take case of Comparator interface:

Comparator<String> c = (String a, String b) -> { return a.compareTo(b); };

Before version 8, the lowest level of abstraction in Java was classes. Functions were not treated as the first-class citizen as you need to have an object handle to use functions (functions don't exist without object). But functions are as valuable and important as objects and classes. Programming languages with first-class functions let you find more opportunities for abstraction which means your code is smaller, lighter, more reusable and scalable.

Related Post: Functional Interfaces

---
keep coding !!!