Archive

Archive for the ‘Technology’ Category

Functional programming and Declarative programming


Imperative programming paradigm contains the description of each step need to be performed to solve a problem. This approach is also referred as an algorithmic approach to solve a given problem. Most well-known languages like c, c++ or java are imperative type programming languages.

Functional programming is implementation of a certain task in the form of composition of different functions.

In a very simple terms, we can understand the difference between the above two as Imperative languages describe “how to” accomplish a goal and functional programming describes “what to” aspect of it. That means imperative programming languages contain loops, conditional statements, methods whereas, functional paradigm contains functions (recursions).

The main difficulty to transition to the functional programming is many are quite familiar with the declarative method of thinking style. Functional programming requires a different set of mind set to describe the problems in the form of functions.

Many imperative languages (such as C++11) are providing ways and means to add the support for the functional programming paradigm to their language tool kit. This allows the developers to easily make use the best of the both worlds.

 

The following are very few language constructs provided by C++ language (C++ 11) to facilitate the functional programming paradigm.

auto key word:

ex: auto a = 10;


#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto n = 10;
	cout << n << endl;
	getchar();
}

Output: 10

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto str = "Hi!";
	cout << str << endl;
	getchar();
}

Output: Hi!

The above code makes declaring a variable much cleaner and much easier.

Lambda functions: (Source from http://en.cppreference.com/w/cpp/language/lambda)

Characteristics:

  1. Unnamed function object
  2. Captures scope in its closures

Syntax:

[ capture-list ] ( params ) mutable(optional) exception attribute -> ret { body }

[ capture-list ] ( params ) -> ret { body }

[ capture-list ] ( params ) { body }

[ capture-list ] { body }

1) Full declaration.

2) Declaration of a const lambda: the objects captured by copy cannot be modified.

3) Omitted trailing-return-type: the return type of the closure’s operator() is determined according to the following rules:

§  if the body consists of nothing but a single return statement with an expression, the return type is the type of the returned expression (after lvalue-to-rvalue, array-to-pointer, or function-to-pointer implicit conversion);

§  otherwise, the return type is void.

(until C++14)
The return type is deduced from return statements as if for a function whose return type is declared auto. (since C++14)

4) Omitted parameter list: function takes no arguments, as if the parameter list was ().

mutable – allows body to modify the parameters captured by copy, and to call their non-const member functions
exception – provides the exception specification or the noexcept clause for operator() of the closure type
attribute – provides the attribute specification for operator() of the closure type

capture-list – a comma-separated list of zero or more captures, optionally beginning with a capture-default.
Capture list can be passed as follows (see below for the detailed description):
 [a,&b] where a is captured by value and b is captured by reference.
 [this] captures the this pointer by value
 [&] captures all automatic variables odr-used in the body of the lambda by reference
 [=] captures all automatic variables odr-used in the body of the lambda by value
 [] captures nothing
params – The list of parameters, as in named functions, except that default arguments are not allowed(until C++14). if auto is used as a type of a parameter, the lambda is a generic lambda (since C++14)
ret – Return type. If not present it’s implied by the function return statements ( or void if it doesn’t return any value)
body – Function body

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto min = [](int a, int b) { return a < b ? a : b; };
	cout<< min(12, 34) << endl;
	getchar();
}

Output: 12

In the above example: the closure is empty that means it is not capturing anything but only two parameters are passed, this function takes a and b and returns the minimum.

Example: Caputure by value


#include
#include
using namespace std;

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [divisor](int a, int b) { return a / divisor + b / divisor; };
	cout<< divideAllSum(30, 40) << endl;
	getchar();
}


In the above example divisor was captured by value hence this value cannot be changed inside the lambda function.
Output: 7
Example: Caputure by reference


#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [&divisor](int a, int b) { divisor = 5;  return a / divisor + b / divisor; };
	
	cout<< divideAllSum(30, 40) << endl;
	cout << "divisor : " << divisor << endl;
	getchar();

}

Output:
14
divisor : 5
In the above example no matter what the value being sent to the function the function is changing it to 5 and returning the value.
Capture all the scope as reference:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [&](int a, int b) { divisor = 5;  return a / divisor + b / divisor; };
	
	cout<< divideAllSum(30, 40) << endl;
	cout << "divisor : " << divisor << endl;
	getchar();

}

In the above case entire the calling function scope has been captured as a reference hence it is possible to modify the divisor variable to 5.
Capture whole scope as a value:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [=](int a, int b) { return a / divisor + b / divisor; };
	cout<< divideAllSum(30, 40) << endl;
	getchar();

}

In the above example “=” is part of closure signifies that the whole scope has been passed as a value hence can use all the variables part of the calling scope.

Using lambda functions as an argument to functions:


#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(void)
{
	vector<int> l;
	for (auto i = 11; i >= 0; i--)
		l.push_back(i);
	sort(l.begin(), l.end(), [](int a, int b) {
		return a >= 5? (a < b) : a > b;
	});
	auto print = [](vector<int> myl) {for (auto i = myl.begin(); i != myl.end(); i++) cout << *i << " "; };
	print(l);
	getchar();
}

Output:
5 6 7 8 9 10 11 4 3 2 1 0

In the above example:
To sort function the lambda function is passed as our own comparator.

Project euler problem 21: Amicable Number


Amicable Number:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where ab, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Solution:

This problem is also easy. Without any optimization it takes considerable amount of time. Hence, I solved it by caching the intermediate results into an array.

#include <iostream>

#include <stdio.h>

using namespace std;
long ami[100000];
int amicable(int num)
{
    long sum = 0;
    if (ami[num - 1] != 0)
        return ami[num - 1];
    else
    {
        for (int i = 1; i <= num /2; i++)  {
            if (num % i == 0)
                sum += i;
        }
        ami[num - 1] = sum;
        return sum;
    }

}

int main()
{
    long long sum = 0;

    for(int i = 1; i <= 10000; i++ ) {
        ami[i] = 0;
    }
    for(int i = 1; i <= 10000; i++ ) {
//        cout<<amicable(i)<<endl;
        if (amicable(i) != i && i == amicable(amicable(i))) {
//          cout<<i<<endl;
            sum += i;
        }
    }
    cout<<"Sum of all amicable numbers: "<<sum;
    return 0;
}

Time taken for the above implementation:

Sum of all amicable numbers: 31626
real 0m0.185s
user 0m0.140s
sys 0m0.046s

One line awk to find all words with all vowels


Here is a one line awk command to find all the words which contains all the vowels in a given file.

awk '{c=split($0, s); for(n=1; n<=c; ++n) print s[n] }' $1 | awk 'match ($0, /[e]/)' |awk 'match ($0, /[i]/)' | awk 'match ($0, /[a]/)'| awk 'match ($0, /[o]/)' |awk 'match ($0, /[u]/)'

if you have a file with the following contents

education
reduction
allusions
documentation

The above command prints
education
documentation

In the above command we are using awk to extract the word and finding whether the given word contains a, e, i, o, u. If any word which contains all the vowels gets printed in the output.

Here is the command that checks all the .txt files recursively and checks for all the words with a, e, i, o, u.

find -name "*.txt" |xargs awk '{c=split($0, s); for(n=1; n<=c; ++n) print s[n] }'| awk 'match ($0, /[e]/)' |awk 'match ($0, /[i]/)' | awk 'match ($0, /[a]/)'| awk 'match ($0, /[o]/)' |awk 'match ($0, /[u]/)'|sort|uniq -i|awk '!match ($0, /[_,\-\.\/\|\@\:\]\[\)\(\*\&\=\*\#\!\{\}\"\?]/)'

A quick observation from the above script is that the last regular expression (awk ‘!match ($0, /[_,\-\.\/\|\@\:\]\[\)\(\*\&\=\*\#\!\{\}\”\?]/)’) is to remove all the words which contain the special characters. But if could eliminate these characters much before they even come about we could significantly improve the performance.

find -name "*.txt" |xargs awk '{c=split($0, s); for(n=1; n<=c; ++n) print s[n] }'| awk '!match ($0, /[_,\-\.\/\|\@\:\]\[\)\(\*\&\=\*\#\!\{\}\"\?]/)'| awk 'match ($0, /[e]/)' |awk 'match ($0, /[i]/)' | awk 'match ($0, /[a]/)'| awk 'match ($0, /[o]/)' |awk 'match ($0, /[u]/)'|sort|uniq -i

Ran the above two commands with “time” command and results are as follows

Without optimization:

real 0m0.824s
user 0m1.508s
sys 0m0.076s

With optimization the last command

real 0m0.784s
user 0m1.868s
sys 0m0.064s

On a medium sized input directory itself we could clearly find the performance improvement.

X509 certificate parsing useful Links


Here are some of the very useful links available online for parsing X509 certificates in C language. The following links will be handy if you are working on a tight schedule project and don’t have enough time to read the official documentation https://www.openssl.org/docs.

https://zakird.com/2013/10/13/certificate-parsing-with-openssl/

http://www.umich.edu/~x509/ssleay/x509_name.html

http://www.gnutls.org/manual/gnutls.html#X509-certificate-API

Official X509 docs.

https://www.openssl.org/docs/crypto/d2i_X509.html

Quick differences between different types of ROMs


ROM (Read Only Memory)

  • As the name suggests, Once programmed cannot be reprogrammed.
  •  If the data needs to be updated throw away the programmed chip and start over with a new chip.
  • Pros:
  • less costly when produced in huge volumes
  • Robust, power efficient.
  • Cons:
  • slower

PROM (Programmable Read Only Memory)

  • This also can be programmed only once.
  • This is field programmable (ie., can be programmed anywhere).
  • Economical even when produced in small quantities.

EPROM (Electronically Programmable Read Only Memory)

  • Electronically Programmable.
  • Inexpensive per chip.
  • EPROM eraser is not selective, it erases entire chip.
  • To erase it is to be placed under the UV laser for several minutes.
  • Caution: EPROM kept under the UV laser more than required time might over erase the chip making it un-usable.

EEPROM (Electrically erasable programmable read-only memory)

  • The changes for EPROM cannot be made incrementally. For any change it erases whole chip and re-writes.
  • EEPROM can erase the targeted cells through re-writing only required cells. This way it removes this biggest drawback of EPROM.
  • EEPROM can be changed 1 Byte at a time but it is very slow.
  • Flash memory overcomes the the above limitation of slowness.
  • Flash memory erases in terms of blocks of size 512 Bytes thus improving the overall performance.

References:

http://en.wikipedia.org/wiki/EEPROM

http://computer.howstuffworks.com/rom5.htm

http://www.mycomputerscience.net/2010/06/read-only-memory1.html#

Flash and EEPROM programming from Mcirochip

Codechef: Find the largest AND operation result between any two elements of a given array


At first the problem looks very simple and can be solved easily in O(N^2).

#include <iostream>
using namespace std;
 
int main() {
 
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
		
	}
	long max = 0;
	for(int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++)
		if (max < (data[i] & data[j]) )
			max = (data[i] & data[j]);
	}
	cout<<max;
	return 0;
} 

But when it comes to huge data sets the solution for finding the maximum between every pair of elements is too much time consuming. A different approach is needed to find it quickly. Here we are reducing the complexity of the algorithm from O(N^2) to merely O(sizeof(long) * 8 * N). This is a good improvement for this algorithm.


#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
	}
	long res = 0;
	int count = 0;
	for(int i = sizeof(long) * 8; i >= 0; i--) {
		count = 0;
		for (int j = 0; j < n; j++) {
			if ((data[j] & (res | (1 << i))) == (res | (1 << i))) {
				count++;
			}
			if (count >= 2) {
				res |= (1 << i);	
				break;
			}
		}
	}
	cout<<res;
	return 0;
}

The above same code can be found here. http://ideone.com/W1LlV0

Here documents in bash


In my day to day work oftentimes I work with C, Bash scripting and Cross compiling for ARM and other interesting stuff. I feel programming is an art so as bash scripting. There are many things we come across after seeing the scripts written by highly experienced bash programmers. One of such concept was a here document.

In simple terms,

here documents can be treated as multiple line input provided to a command in a shell script.

Let us discuss here documents with simple examples:

Example 1:

wc -l << COUNT_LINES
Vasanth Raja
Chittampally
!!
COUNT_LINES

In the above example the start and end of the here document are specified with “COUNT_LINES“. Input to “wc -l” command is the three lines in between the COUNT_LINES. As expected the output to this is “3“.

Example 2:

Oftentimes I see the here documents used in conjunction with cat. This is because when we want to print set of lines to the terminal, this comes in handy. For example

cat << USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Few important points are

1. In here documents we can substitute command outputs.

In the above example $0 and `dirname $0` are replaced with the command outputs.

2. All the text in the here document will be printed exactly to the standard output. That means leading tabs, spaces are preserved exactly.

Suppose if you wish to remove the leading tabs from the here document, the same can be achieved in the following manner

cat << – USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Just use a ‘-‘ symbol just after the symbol “<<“.

In a nutshell, here documents comes very hand when you want to give multiple line input to a command. Moreover, here documents are simple to use and easy to understand.