Latest Entries »

Karatsuba multiplication

The Karatsuba method for fast multiplication is sometimes also called 
Divide-and-Conquer method.It reduces the multiplication of two n digit 
numbers to at most 3n^log3 ~ 3n^1.585 single digit multiplication.

Here's karatsuba algo in detail(check out example 3,Integer Multiplication)
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

c implementation of karatsuba's algorithm ::

//recursively multiplying two big positive numbers 
//using karatsuba's algorithm

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//numbers 'll be stored in array of integers in reverse order
//i.e. array[1] is 10's digit and array[0] is 1's digit
#define MAX_DIGIT 1024

#define CUTOFF 4

void input(int aa[], int *x);
int find1(int a, int b);
void initialize(int xx[], int yy[], int xLen, int yLen, int tLEn);
void karatsuba(int xx[], int yy[], int rr[], int tLen);
void print(int aa[], int x);
void normalMultiplication(int *xx, int *yy, int *rr, int tLen);
void fixCarry(int rr[], int tLen);

int main(int agrc, char *argv[])
{
	int xx[MAX_DIGIT]; //first multiplicand
	int xLen = 0;
	int yy[MAX_DIGIT]; //second multiplicand
	int yLen = 0;
    //result 'll be in first 2d digits...
    //remaining space will be used for various purposes
	int zz[6*MAX_DIGIT];
	
	input(xx, &xLen);	
	assert(xLen >= 0);
	input(yy, &yLen);	
	assert(yLen >= 0);
	//smallest power of 2 greater than both xLen && yLen
	int tLen = find1(xLen, yLen); 
	
	initialize(xx, yy, xLen, yLen, tLen);

	karatsuba(xx, yy, zz, tLen);

//since we didn't checked in karatsuba that digits are b/w 0-9
	fixCarry(zz, 2 * tLen);

	print(zz, tLen);

	return EXIT_SUCCESS;
}

//take input and store it in reverse order in array of integers
void input(int aa[], int *x)
{
	char c;
	if((c=getchar()) != '\n' && *x <= MAX_DIGIT){
		input(aa, x);
		aa[*x] = c - '0';
		(*x)++;
	}else return;
}

//finds smallest power of 2 greater than both a and b
int find1(int a, int b)
{
	int tLen = 1;
	while(tLen <= a || tLen <=b){
		tLen *=2;
	}
	return tLen;
}

//initialize xx and yy to 0 uptil tLen
void initialize(int xx[], int yy[], int xLen, int yLen, int tLen)
{
	int i;
	for(i=xLen; i<tLen; i++) xx[i] = 0;
	for(i=yLen; i<tLen; i++) yy[i] = 0;  
}

void karatsuba(int xx[], int yy[], int rr[], int tLen)
{
	int *a = &xx[tLen/2];
	int *b = &xx[0];
	int *c = &yy[tLen/2];
	int *d = &yy[0];

	//since only 2d space is required for result
	//hence we 'll use remaining space 
	int *wx = &rr[tLen*5]; //sum of xx's halves
	int *wy = &rr[tLen*5 + tLen/2]; //sum of yy's halves

	int *V = &rr[tLen*0];  //location of b*d
	int *U = &rr[tLen*1];  //location of a*c
	int *W = &rr[tLen*2];  //location of (a+b)*(c+d)		

	//for small value of tLen ormal multiplication is faster
	if(tLen <= CUTOFF){
		normalMultiplication(xx, yy, rr, tLen);
		return;
	}
	int i;
	//compute wx and wy
	for(i=0; i<tLen/2; i++){
		wx[i] = a[i] + b[i];
		wy[i] = c[i] + d[i];
	}

	//divide
	karatsuba(b, d, V, tLen/2);
	karatsuba(a, c, U, tLen/2);
	karatsuba(wx, wy, W, tLen/2);

	//conquer and combine
	for(i=0; i<tLen; i++)  W[i]=W[i]-U[i]-V[i];
	for(i=0; i<tLen; i++)  rr[i+tLen/2] += W[i];

}

//print the result 
void print(int aa[], int x)
{
	int i;
	for( i = x-1; i>0; i--)   if(aa[i] != 0)  break;
	for( ; i>=0; i--) 	printf("%d", aa[i]);
	printf("\n");
}

//standard multiplication
void normalMultiplication(int *xx, int *yy, int *rr, int tLen)
{
	int i;
	int j;
	for(i=0; i<2*tLen; i++)  rr[i] = 0;
	for(i=0; i<tLen; i++){
		for(j=0; j<tLen; j++){
			rr[i+j] += xx[i]*yy[j];
		}
	}
}

//to make sure that all numbers are b/w 0-9
void fixCarry(int rr[], int tLen)
{
	int i;
	int carry = 0;
	for(i=0; i<tLen; i++){
		rr[i]+=carry;
		if(rr[i] < 0){
			carry = ( -(rr[i]+1)/10 +1 ); 
		}else{
			carry = rr[i]/10;
		}
		rr[i] = rr[i]- carry*10;
	}
	assert(carry == 0);  //check overflow
}
Advertisements

Vim for lazy people

Inspired by one my friend’s facebook status which says…”Laziness is a virtue which assists U in doing a job in minimum possible time with maximum possible efficiency !!” , I decided to customize my vim editor to implement features like ctrl+c, ctrl+v, autocomplete, autoindent, single key compile and run etc. to get a “true” IDE

First of all install SuperTab , this extension provides a functionality similar to auto-complete, and for my purposes, infact it improves it. Whenever you are typing a word/variable if you hit tab it will find the nearest match and/or display a list of possible completions.

Now create a .vimrc file if it is not present already in home directory. I’m posting my .vimrc file which is properly commented so that you can modify it in accordance to yourself.

Note that the comment tags are created in vimrc files using the ” (quote) character instead of the more usual # or //. Also during mapping of key “+y etc. represents the key mapped and is NOT a comment.

Here’s my .vimrc file ::

"tab size
set ts=4

"indentation width
set sw=4

"c like indentation
set cindent


"autocomplete menu
set wildmenu
set wildmode=list:longest,full
set mouse=a

"compiling using F3
map <F3> : call CompileGcc()<CR>
func! CompileGcc()
  exec "w"
  exec "!gcc % -o %<"
endfunc

"compile and execute using F9
map <F9> :call CompileRunGcc()<CR>
func! CompileRunGcc()
  exec "w"
  exec "!gcc % -o %<"
  exec "! ./%<"
endfunc

"autocomplete Parenthesis
"When you type an open brace, this will automatically
"insert a closing brace on the same line, after the cursor.
"If you quickly hit Enter after the open brace, (to begin
"a code block), the closing brace will be inserted on the
"line below the cursor. If you quickly press the open brace
"key again after the open brace, Vim won't insert anything extra,
" you'll just get a single open brace. Finally, if you quickly
"type an open and close brace, Vim will not do anything special.
inoremap {      {}<Left>
inoremap {<CR>  {<CR>}<Esc>O
inoremap {{     {
inoremap {}     {}

inoremap (      ()<Left>
inoremap (<CR>  (<CR>)<Esc>O
inoremap ((     (
inoremap ()     ()

inoremap [      []<Left>
inoremap [<CR>  [<CR>]<Esc>O
inoremap [[     [
inoremap []     []

"mapping some more keys ::

"CTRL-X is cut
vnoremap <C-X> "+x

"CTRL-C is copy
vnoremap <C-C> "+y

"CTRL-V is paste
vnoremap <C-V> "+gP

"to paste blockwise, uses paste.vim autoload script
exe 'inoremap <script> <C-V>' paste#paste_cmd['i']
exe 'vnoremap <script> <C-V>' paste#paste_cmd['v']

" CTRL-A is Select all
noremap <C-A> gggH<C-O>G
inoremap <C-A> <C-O>gg<C-O>gH<C-O>G
cnoremap <C-A> <C-C>gggH<C-O>G
onoremap <C-A> <C-C>gggH<C-O>G
snoremap <C-A> <C-C>gggH<C-O>G
xnoremap <C-A> <C-C>ggVG

" Use CTRL-Q to do what CTRL-V used to do
noremap <C-Q>  <C-V>

Conversion of Infix string to Prefix in c++
Have tested this on only some weak test
cases, do tell me if it goes wrong somewhere

#include<iostream>
#include<string>
#include<stack>
#include<cstdio>

using namespace std;

bool precedence(string a, string b);
void infixToPrefix(string s);

int main()
{
        string s;
        cin>>s;

        infixToPrefix(s);

        return 0;
}
void infixToPrefix(string s)
{
        stack<string> operator1;        //operator stack
        stack<string> op;               //operand stack

        for(int i=0; i<s.size(); i++){
                string s6="";
                s6+=s[i];

                //token is an operand
                if(s[i]!='+' && s[i]!='-' && s[i]!='*' && s[i]!='/' && s[i]!='(' && s[i]!=')' && s[i]!='$'){
                        string s5;
                        s5=s[i];
                        op.push(s5);
                }else if(s[i]==')'){  //if right parentheses 
                 //continue to pop operator nd operand stack
                 //till left parentheses is found 
                        while(operator1.top()!="("){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        //pop the left parentheses
                        operator1.pop();


                }else if(s[i]=='(' || operator1.empty() || (!operator1.empty() && precedence(s6,operator1.top())) ){
                        string s5;
                        s5=s[i];
                        operator1.push(s5);
                }else{
                /*Continue to pop operator and 
                operand stack, building prefix
                expressions until the stack is empty or 
                until an operator at the
                top of the operator stack has a lower precedence
                than that of token */
                        while((!operator1.empty()) && !(precedence(s6, operator1.top()))){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        string s5="";
                        s5+=s[i];
                        operator1.push(s5);
                }

        }
        /*If the stack is not empty,
        continue to pop operator and operand stacks building
        prefix expressions until the operator stack is empty.*/
        while(!operator1.empty()){
                string a=operator1.top();
                operator1.pop();
                string b=op.top();
                op.pop();
                string c=op.top();
                op.pop();
                string s2;
                s2=a+c+b;
                op.push(s2);
        }

        while(!op.empty()){
                cout<<op.top()<<" ";
                op.pop();
        }
        cout<<endl;

}

// returns true if precedence of a is more than b
// else return false     
bool precedence(string a, string b)
{
        int aa=0;
        int bb=0;
        if(a=="("){
                return false;
        }else if(b=="("){
                return true;
        }else if(b==")"){
                return true;
        }else if(a==")"){
                printf("undefined operation\n");
                return 0;
        }

        if(a=="+" || a=="-") aa=1;
        if(a=="*" || a=="/") aa=2;
        if(b=="+" || b=="-") bb=1;
        if(b=="*" || b=="/") bb=2;
        if(a=="$") aa=3;
        if(b=="$") bb=3;
        if(aa > bb) return true;

        return false;
}

ADOBE V/S APPLE

The tension between Apple and Adobe was simmering for quite a while and the new SDK agreement seems like a breakpoint.Adobe, Microsoft, not only can you not have Adobe Flash or Microsoft Silverlight running natively on an iPod Touch,iPhone, or iPad, you can also forget about creating an iWhatever program that can get around that requirement.

According to new licensing agreement  ::   Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs.Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine,and only code written in C, C++, and Objective-C may compile and directly link against  the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

This seems to mean that cross-compilers, which let you develop in the Adobe Flash CS5, the C# and .NET-based Mono Touch, or similar environments and spit out iPhone-compatible binaries at the end, are being prohibited.Apple is being portraited as evil…and adobe is getting a lot of sympathy.

Lets try to answer the question of who is to blame and who is trying to do the right thing.

If we see things from Apple’s perspective Apple has its reasons.Flash on a base level provides a very real threat to Apple’s  lucrative App Store, one of the key things that it uses to differentiate the iPod Touch/iPhone/iPad from its competitors. If Apple adopted Flash, many of its developers could move to Flash which would free them of the restrictions of Apple’s App Store approval process. And that would ultimately ruin the exclusivity of Apple’s app catalog and make Apple vulnerable to handsets with superior hardware.Also, with Flash customers could simply view TV episodes for free rather than buy them from Apple’s iTunes store.

Apple CEO Steven P. Jobs argues that Flash, is simply no good. It crashes Mac and runs too slow for his tastes.He also claims that Flash would reduce the iPad’s battery life from 10 hours to 1.5 hours.

Adobe, the king of Internet video with 95% Web browser market penetration, is not one bit happy about being locked out of Apple’s lucrative mobile device market.The reason Adobe is talking is because that’s all it can do at this point after screwing up its mobile strategy and failing to anticipate years ago where computing was headed and what changes it needed to make. It’s not Apple’s job to keep Adobe in business.Adobe’s CTO Kevin Lynch himself acknowledged that Flash has typically run faster in Microsoft Windows than in Apple’s Macintosh OS, from which the iPhone OS is derived.

Frankly speaking, Once you get used to getting paid to do next to nothing,it’s a brutal shock when somebody stands up and refuses to play along with your ridiculous game and this is what happening with Adobe.The ubiquitousness of Flash is like a cancer, they are even now building it into the heart of all their flagship products.Yes, Adobe is adopting the write once, run anywhere philosophy that even Microsoft abandoned years ago.Flash programmers need to understand that using Flash for everything is poor practice.

Apple don’t want Windows-like share of the mobile market, they want quality( that’s what seems frm their strategy so far).They want to give people a reason to prefer the iPhone. Imagine, a major new features in iPhone OS are released by Apple but the other company’s toolkit is slow to adapt them. At that point, it’s the other company that controls when third party apps can make use of these features. So all this make sense from apple’s point of view.

But the main thing that bugs me is Apple is changing the rules in the middle of the game.Some of developers have significant investments in tool sets that were previously allowed and are now banned.Changing the rules on developers in ways that will cost them $$$ of dollars is extremely frustrating. This erodes developer trust.And the one most important thing i learned from the movie “The Godfather”(undoubtedly my fav. movie ^^)  is  “to be on top u need to have trust and honour”and saying to vendors “It’s  my house if you don’t like it leave” doesn’t help it.

Apple will also lose the users that see Flash is an important content and the users who do not like to lose the ability to view Flash content on the web.Furthermore, Apple will lose Adobe users, developers who seek to build applications on Apple devices forever. Now that Google has a version of their Android OS that’s better than iPhone OS 4 (Android 2.1) developers are finally beginning a gradual move away from Apple over to Android. Many developers feel that Apple knows exactly  “How To Be A Douchebag”. It will be interesting to see how Apple fares with this in its competition against Google longer term.

So if we think of present, this decision is a lose-lose situation for both Apple and Adobe. But considering the future,for Apple it can either prove to be a big asset or their worst decision ever, and for adobe…Sorry, Adobe, you screwed yourself !!

I’m glad Apple brought some dynamic to this market.I think they deserve every credit for pushing the smarthphone industry to the mainstream but i guess they took the right decision at the wrong time.This decision will give a big push to HTML5 revolution but they don’t seem to be replacing each other, certainly not today nor even in foreseeable future.Looking at the iPhone OS 4.0 and Apple’s mentality of keeping the platform closed I think they’ll loose their top spot and perhaps fall behind Google and even Microsoft.

Recursively converting expression into postfix from prefix ::

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 100

void convert(char prefix[], char postfix[]);
int find(char str[]);
char* substr(char src[], int offset, int len, char dest[]);

int main()
{
	char prefix[MAX];
	char postfix[MAX];
	printf("enter the prefix string\n");
	scanf(" %s", prefix);
	convert(prefix, postfix);
	printf("%s\n", postfix);

	return 0;
}

//algo ::
//1.If the prefix string is a single variable, it is its own postfix equivalent
//2.Let op be the first operator of the prefix string
//3.Find the first operand, opnd1 of the string.Convert it to postfix and call it post1.
//4.Find the second operand, opnd2, of the string.Convert it to postfix and cal it post2.
//5.Concatenate post1, post2, and op.
void convert(char prefix[], char postfix[])
{
	char opnd1[MAX];
	char opnd2[MAX];
	char post1[MAX];
	char post2[MAX];
	char temp[MAX];
	char op[2];
	int length;
	int i,j,m,n;

	//prefix string is single variable
	if((length=strlen(prefix))==1){
		if(isalpha(prefix[0])){
			postfix[0]=prefix[0];
			postfix[1]='\0';
			return;
		}

		printf("illegal prefix string\n");
		exit(1);
	}

	//prefix string is longer
	op[0]=prefix[0];
	op[1]='\0';
	substr(prefix,1,length-1,temp);
	m=find(temp);
	substr(prefix, m+1, length-m-1, temp);
	n=find(temp);

	if((op[0]!='+' && op[0]!='-' && op[0]!='*' && op[0]!='/') || (m==0) || (n==0) || (m+n+1!=length)){
		printf("illegal prefix string\n");
		exit(1);
	}
	substr(prefix, 1, m, opnd1);
	substr(prefix, m+1, n, opnd2);

	convert(opnd1, post1);
	convert(opnd2, post2);
	strcat(post1, post2);
	strcat(post1, op);

	substr(post1, 0, length, postfix);
}

int find(char str[])
{
	char temp[MAX];
	int length;
	int i,j,m,n;

	if((length=strlen(str))==0)	return 0;

	//first character is a letter
	if(isalpha(str[0])!=0)		return 1;

	//otherwise find the first operand
	if(strlen(str)<2)	return 0;

	substr(str, 1, length-1, temp);
	m=find(temp);

	//no valid prefi operand or no second operand
	if(m==0 || strlen(str)==m)	return 0;

	substr(str, m+1, length-m-1, temp);
	n=find(temp);

	if(n==0)	return 0;

	return (m+n+1);
}

char* substr(char src[], int offset, int len, char dest[])
{
	int i;
	for(i = 0; i < len && src[offset + i] != '\0'; i++){
		dest[i] = src[i + offset];
	}
	dest[i] = '\0';

	return dest;
}
//P.S.... COPIED FROM MY TEXTBOOK

Conversion of prefix to postfix using stack ::

#include <iostream>
#include <stack>

using namespace std;

#define MAX 100
#define OP1_FLAG '#'

bool isOperator(char ch);

int main()
{
	//prefix input expression and postfix output expression
	char prefix[MAX],postfix[MAX];
	stack<char> stk;

	cout<<"Enter the prefix expression\n";
	cin>>prefix;

	int j=0;
	for (int i=0;prefix[i];i++){
		if(isOperator(prefix[i])){
			stk.push(prefix[i]);
		}else {
			//as sequence of operand in prefix and
            //postfix expressions are same
			postfix[j]=prefix[i];
			j++;
	         /*OP1_FLAG is a flag that indicates the left operand
              for this operator is already converted to postfix.
              After popping out these OP1 operators the next
              operator is marked OP1_FLAG*/
			while(!stk.empty() && stk.top()==OP1_FLAG){
				stk.pop();
				postfix[j]=stk.top();
				j++;
				stk.pop();
			}
			stk.push(OP1_FLAG);
		}
	}

    	postfix[j]=0;

	cout<<"Postfix expression is ::  " << postfix << endl;

	return 0;

}

bool isOperator(char ch){
	if(ch=='+' || ch=='-' || ch == '*' || ch == '/' || ch == '$' || ch == '%')	return true;
	else	return false;
}

Some wise guy has rightly said “You won’t find a more Philosophical talk than the talk between three drunk persons”.

Anyways, one interesting thing about my college is pathway between hostel and malik (a near by place to eat and kill time)…just try talking somthing interesting and you’ll get hell lot of fresh ideas whether it be something innovative like this proposal theory 😉 or something serious like paper presentation which we won in IIT-Roorkee last week which was based on an idea sprouted during the pathway followed by cup of tea + lots of bakchodi…and the contest judge(teacher) was like “in my 40yrs of career i haven’t seen any new idea, how can your’s be new ? ” , … mam, there is always a first time i guess !!!

To start with, if it is a gal reading this blog, time for you to click on the X of this tab of your browser as this one is strictly for guys and btw if i have ever proposed you, i was damn serious that time !!! 😛

Special mention to pandey (Mr. peanut butter ) and sipul (our one and only vipul mittal) coz they were the other two philisophers that night !!! 😀

The topic of discussion was “why guys are hesitant to propose the girl, they like ??”
The whole talk is very seriously summerized in form of a theory “Win Win Theory of Random Proposals” a.k.a  WW-TRaP ^_^
To summarize the theory in one line “if there are n gals u like, then you can propose any ith and jth gal such that i and j don’t know each other…and you can continue to vary(randomize) these i’s and j’s till u get a green light” 😉

Remember girls will be girls. Whenever guys propose them, they show airs and snub the proposals made by the poor creatures. And the dejected dudes never dare to propose any other girl in their life. But come on guys,this is being too pessimistic !! Just think it this way, after all there are only 4 possibilities.The case where she likes u and she is not committed is easiest and best…you’ll immediately get a green signal on proposal, whats better than spending some quality time with your gal rather than wasting time thinkin’ whether she is into you or not !! 😀

Lets move over to worse case scenario … you are interested in a girl which is committed and she was never interested in you (of course u nva knew that).Before proposing such a girl just make sure her bf is not the one with big muscles who saw u staring at his gal the other day 😛  If she doesn’t say NO (as if it is the only word from dictionary she knows) then the most probable outcome of this proposal will be “Let’s just be friends”. No guy likes to hear “lets just be friends” shit from a woman who he is interested in as it deciphers to “u can pay my bills but don’t you dare come close to me”. Its your wish now how to reply to that, i personally prefer to “not just be friends”.
One more probable reply can be “I have never thought you w’d be thinking this about me !!” (Lo and behold, she thinks also :-|) . See, by proposing her, you actually made sure that there is no use wasting your precious time on her.

The other two possible cases are : she likes you and she is committed or she doesn’t like you and shez not committed either…in both of these cases her behaviour towards you will change in positive sense…just make sure you propose her confidently and in the best way she can ever imagine…in this way she will have an entry in her mind’s database that there exist a guy X who might be better than her BF and she’ll start comparing her bf with you every now and then ( believe me, you’ll surely get the benefit of doubt 😉 ) and, if she doesn’t have one then even better chances are there…coz she will compare you to every guy she like…the main thing in this mind scheduling algorithm is that, you are getting in most of her thoughts so chances are : big thumbs up !!! 😉
The worse you can expect in these two situation is “I always took you as a good friend and you…..?” (All dramebaazi…gal with a confused soul) or a copycat gal saying “I don’t believe in such things, you just mind your work”(most boring reply ever). Argh…you sure can get a better and lively girl than that !!!

For all of you with broken heart, make two things crystal clear,firstly “Heart is a muscle not a bone. so it is nva broken, only pulled or strained”  and secondly the best way to mend a broken heart is time and a new girlfriend .

So to summarize WW-TRaP …. propose the gal you like in a smart way at the earliest…and see the magic pouring, always a win-win situation !!! 😀

Don’t take life too seriouslyno one gets out alive anyway

When your VMware Player crashes unexpectedly upon start (i.e. GUI opens up for 1-2 seconds and then disappears), fear not.Fix is very simple  ::

#cd /usr/lib/vmware/lib
#sudo mv libcurl.so.4 libcurl.so.4.old

That’s it !!! 🙂

That worked for me. If that does not work either…try this

#vmware-modconfig --console --install-all
#mv /usr/lib/vmware/resources/mozilla-root-certs.crt 
/usr/lib/vmware/resources/mozilla-root-certs.crt.old


"certificate" crash is due to "curl" package which don't support ssl or c-ares
credits :: http://communities.vmware.com/message/1444574#1444574