Calculate nth fibonacci number in O(log(n))

I wrote this function that calculates nth fibonacci number in O(log(n)) time complexity and O(log(n)) space complexity. This is helpful when n is very large. You can't calculate nth fib iteratively when n is say 2^31. You need O(log(n)) or better algorithm for that. However the below function can't calculate 2^31th fib because it won't fit into long long. But my point now is to just present the implementation of O(log(n)) algo for small integers. It can be easily adapted to any integer(however large) if you have a BigInt library. I will try to write the BigInt version later when I get time.

The logic behind this algo is explained here. Note that this algo does not use any approximation. Its 100% accurate. The O(1) alogs available for this use approximation and MAY give wrong answers for some value of n.
Note that F(0)=0 and F(1)=1.

/*
* This function computes the nth fibonacci number in log(n) time and log(n) space complexity.
* This is helpful when we need to calculate fibonacci number where n is very large.
* Note that when n is large, fib(n) won't fit in integer.
* So essentially this function will have to be adapted for bigint.
*
* We assume F(0)=0 and F(1)=1.
*
* Note that this function does not use any approximation. Its 100% accurate.
*/
#include
#include
#include
#include
#include
using namespace std;
int Fibonacci(int n)
{
if(n<=1)return n;
int *nums=NULL,*values=NULL,ret,ctr,a,b,i;
nums = new int[int(ceil(4*log(n)))+4];
ctr=0;
nums[ctr++]=n;
for(i=0;i if(nums[i]>1)
{
if(nums[i]&1) // if odd
{
if(find(nums+i+1,nums+ctr,(nums[i]+1)/2)==nums+ctr)
nums[ctr++]=(nums[i]+1)/2;
if(find(nums+i+1,nums+ctr,(nums[i]+1)/2-1)==nums+ctr)
nums[ctr++]=(nums[i]+1)/2-1;
}
else // if even
{
if(find(nums+i+1,nums+ctr,nums[i]/2)==nums+ctr)
nums[ctr++]=nums[i]/2;
if(find(nums+i+1,nums+ctr,nums[i]/2-1)==nums+ctr)
nums[ctr++]=nums[i]/2-1;
}
}
values = new int[ctr];
for(i=ctr-1;i>=0;i--)
{
if(nums[i]<=1)values[i]=nums[i];
else if(nums[i]&1) // if odd
{
a=values[find(nums+i+1,nums+ctr,(nums[i]+1)/2)-nums];
b=values[find(nums+i+1,nums+ctr,(nums[i]+1)/2-1)-nums];
values[i]=a*a+b*b;
}
else // if even
{
a=values[find(nums+i+1,nums+ctr,nums[i]/2)-nums];
b=values[find(nums+i+1,nums+ctr,nums[i]/2-1)-nums];
values[i]=(2*b+a)*a;
}
}
ret = values[0];
delete nums;
delete values;
return ret;
}
int main()
{
int n;
while(scanf(" %d",&n)!=EOF)
printf("%d\n",Fibonacci(n));
return 0;
}

How about a projector without a canvas and on the battered corner of your room?

How about a projector which does not need a white canvas or a flat surface to project on?

I was reading about my BTP(Smart Camera - Projector Systems), and then found this cool application of it. No need to roll down a big white canvas anymore for a theater experience. Just select any part of your wall, or just a curtain, a table cloth or just anything. The surface need not be even flat..., you can even choose corners of your room as a screen..... To know what I am talking about see the pics below:-

A scruffy corner(yes a corner of a wall!):-

Output of a normal projector(notice the effect of choosing a corner as your viewing screen):-

Geometry-Corrected output by the smart camera-projector system:

Geo+color corrected output by smart camera-projector system:


For more read this or this research paper(pdf).
Here a few more cool pics:-
Projection on a natural stone wall inside a castle vault (click to get a larger view):-

Projection on a checkered curtain:-


Its cool!!

Dynamic Shadow Elimination with Occluder light suppression

I read one more paper today by the same author. This paper is an advancement of his earlier paper on shadow elimination. The new technique not only eliminates shadows but also removes the light falling on the occluder i.e. the person presenting the slides. This prevents the presenter of the annoying bright light falling on his/her face.

The logic is an advanced version of the one used in simple shadow elimination, explained in my earlier post. The shadow elimination part is same. But now we need to identify which projector's light is being blocked by the presenter and turn off the blocked pixels of that projector. For that the author uses a cyclic check. The author defines a new alpha this time, which is not the same for the corresponding pixels of all the projectors. Its different for each of the projectors.
da_jt = (da_jt)_SE + (da_jt)_LS,
where d stands for the triangle - symbol for delta and a stands for alpha. SE is shadow elimination and LS is light suppression. Delta alpha jt SE is the same old alpha of last post.
(da_jt)_SE = - y(Z_t - Z_o),
where y stands for gamma which was choosen as 0.25 by the author. This shadow elimination alpha is same as before. The new thing is:-
(da_jt)_LS = - B(da²_j(t-N))/(dZ²_(t-N)+e),
where B stands for a beta(a constant) and e for epsilon just added to prevent the denominator from being 0. Now if changing the alpha valus of projector j does not change Z i.e. dZ is 0, then that projector is being occluded and its alpha should go to 0. so when dZ goes 0, denominator becomes very low, so the overall fraction becomes very high and the minus sign leads to subtractiion which makes the alpha near to 0. So thats how Light suppression works. LS has to be done in a cyclic way. Changing alpha LS for the projectors one at a time. For 2 projectors its pretty easy.
Now the author clips da_jt = (da_jt)_SE + (da_jt)_LS, to between 1 and 0 to prevent it from going out of bound.

Dynamic Shadow Elimination for Multi-Projector Displays

Yes I am posting very frequently nowadays. The reason is I am reading a lot of papers for my BTP. I have to give a presentation soon on Applications of Smart Camera-Projector Systems. A lot of cool things could be developed by combining a camera and a projector. I have already blogged about Keystone Correction and Presentaion Control using Laser Pointer. Today I am writing my notes on what I understood about Shadow Elimination using 2 or more projectors by reading this paper:-
Dynamic Shadow Elimination for Multi-Projector Displays - Compaq Tech Report CRLTR 2001/4.
This video(courtesy this site) explains the concept nicely:-

A major problem with interactive displays based on front-projection is that users cast undesirable shadows on the display surface. This situation is only partially-addressed by mounting a single projector at an extreme angle and pre-warping the projected image to undo keystoning distortions. But shadows can be muted by redundantly illuminating the display surface using multiple projectors, all mounted at different locations, and with the aid of a low resolution camera. The camera could be mounted at extreme angle to the screen.

This task is done in three steps:-
1. Automatic Multi-Projector alignment: First of all, all the projectors need to be aligned accurately so that they don't form multiple images on the screen (note that 2 projectors are enough for dynamic shadow elimination). For this, the transform for each projector to camera has to be determined. A few reference images are first displayed and their images are taken by camera. Using these, the transforms for each projector is determined by the method described in my earlier post on keystone correction. Note that, in keystone correction, there was only 1 projector. But here we have to align more than 1. For this the scaling+translation matrix S is choosen appropriately.

2. Occlusion detection: Note that we can only remove penumbral shadows. Umbral shadows i.e. the shadows formed when light from no projector is reaching at a spot could not be removed. Also note that a single occlusion can cause multiple shadows because we have multiple source of lights(projectors).

The technique used is very simple - negative feedback.
First a reference image is created for each slide. For this, each slide is presented and camera takes a few images of it. This is done as an intialization step and no occlusion should be present during this process. Note that this is kind of bad. Before each presentation, the system will create reference images of all the slides, which may take around may be 1 mintue. Also this technique will work only for static slides. Won't work for slides containing animations or videos. I think this concept of reference image is the only glitch in this whole technique of shadow elimination.
So after the initialization step is over, user can start the presentation any time. The camera takes images and calculates the pixel by pixel difference of the current image and its corresponding reference image taken earlier i.e. I_t(x,y) - I₀(x,y). The difference come out to be negative for pixels correspondig to shadow regions and almost 0 for normal regions. The system then adjust the intensities for the new time step as:-
Alpha is the intensity multiplication factor(0-255). Intially it is set at 256/(no. of projectors). For a 2 projector system, this is 128. Then this alpha is adjusted everytime based on the difference image - negative feedback. Note that this alpha is calculated for all the pixels. For a 2 projector system the value of alpha will change gradually from 128 to 256 for the pixles corresponding to the shadow regions. This perfectly eliminates the shadows. Note that the same alpha is valid for all the projectors and need not be calculated separately for each one. This is because the increase in alpha of the projector being occluded has no effect on the slide, because that projector is already occluded! The paper author used a value of 0.25 for gamma. He claims this leads to stabilization in around 3 steps for his experiments.

3. Shadow elimination: Now this alpha mask i.e the set of pixel differences calculated above needs to be applied to all the projectors. But we calculated this mask in camera frame/domain. We transform this in the original domain using the inverse of T, calculation of which I explained in my Keystone correction post. Now apply this mask and bingo! shadow is eliminated!

Next I am reading a paper from the same author on Dynamic Shadow Elimination with Occluder light suppression. Note that when a presenter comes in front of a projector, not only he casts a shadow but he/she is also annoyed with the bright light falling on his/her eyes. Occluder light suppression algorithm identifies which projector is being occluded and its corresponding pixels are turned off. So no light falls on the presentor and the shadow is still eliminated using the help of other projector(s). Note that the projector as a whole is not turned off but only the pixels that are under the shadow are turned off.
Watch this video to see it in action(courtesy this site):

I am not quite impressed with the results in above video. I would prefer simple shadow elimination without the occluded light suppression because the annoying to the presenter is not that important as compared to the artifacts that we see in the above video.

Vision-based Presentation Control

Vision-based Presentation Control is another small application for smart camera - projector systems.

Vision-based presentation control frees the speaker from standing beside the computer while delivering a talk. The speaker uses a pointing device (typically a laser pointer) to activate virtual buttons on the projected slide to drive the presentation.

This one actually uses the same concept being used by the keystone correction that I talked about in my earlier post. In fact, its much simpler. Just detect the position of the laser pointer in the camera Image CamImg and map it to the original image OrgImg using the inverse of transformation T (discussed in my earlier post). Thats it. Once you know the position of laser pointer in the original image, check if its on some button or not and do appropriate actions. The vision part is this much only. Rest is software, provide different kind of buttons and all.
The author of the paper from where I read this has provided a few extra buttons that makes it easier to go to next and previous slide.

Vision based automatic keystone correction for projectors

As said in my earlier post, I love my BTP and have started working on it. I read a paper today:-
Automatic Keystone Correction for Camera-assisted Presentation Interfaces - Proceedings of International Conference on Multimodal Interfaces, 2000.
Its on keystone correction using camera-projector system.

----------------------
UPDATE : The same author wrote a new version of the above paper 1 year later to be presented in another conference. The new paper explains things better:-
Smarter Presentations: Exploiting Homography in Camera-Projector Systems - Proceedings of International Conference on Computer Vision, 2001.
----------------------

Below are notes on my understanding of the paper.

Unless the projector is precisely aligned to the presentation screen, the resulting image suffers from perspective (keystone) distortions requiring manual optical or digital correction. For todays mobile LCD projectors, adjusting them manually every time is a tedious task. This method automates this task using the projector - camera combination.

The following three images (courtesy this site) explains this nicely:-


PS: The notes below are for my personal reference. It may not make sense to you.

Vision Based Keystone Correction
Correcting keystone by pre-warping the image. Uses normal LCD projectors. And low quality(yes very low quality) camera.

Let OrgImg be the orginal Image. ProjImg be the projected image that audience sees and let CamImg is the image seen/recorded by camera.
Now we develop techniques to find the OrgImg -> CamImg transformation (T) and ProjImg -> CamImg Transformation (C). Using these two we determine the OrgImg -> ProjImg transformation (P):-
CamImg = T x OrgImg
CamImg = C x ProjImg
=> C x ProjImg = T x OrgImg
=> ProjImg = C^-1 x T x OrgImg
i.e P = C^-1T

So to correct the image we just have to apply P^-1 to the original image, and apply little scaling and translation (S) to make the image form at proper place and inside the projection keystone.
So W = P^-1S needs to be applied.

Calculating T:
We know that OrgImg to ProjImg (P) is a perspective transform and so is ProjImg to CamImg (C). But the combination of them, that is OrgImg to CamImg (T) is not. We can represent the transformation from OrgImg to CamImg (T) as:-

|        (p1X + p2Y + p3)   (p4X + p5Y + p6)
|(x,y) = ---------------- , ----------------
|        (p7X + p8Y + p9)   (p7X + p8Y + p9)

where (x,y) is a point in OrgImg and (X,Y) is a point in CamImg. ( By the way, reverse mapping can also be represented in the same way. ) There are 9 unknowns. But actually only 8 since p1²+p2²+...+p9²=1. I don't know how that constraint came. I understand that since we are dealing with homogeneous co-ordinates, so there are only 8 unknowns. But how did the author of the paper came with that constraint, I don't know(please comment if you know). So 4 points are enough.(Each point provides 2 equations.)
This transformation can be represented as a matrix (T) (using 2-D homogeneous co-ordinates):

|  -          -
|T=| p1 p2 p3 |
|  | p4 p5 p6 |
|  | p7 p8 p9 |
|  -          -

These unknowns are found using 4 points on the screen during the setup of projector(using some predefined image).
Calculating C:
The four corners of screen is used to calculate this in a similar manner as done above.

The picture below explains the result:-
I will be posting more on this as I read more. Got to give a presentation on applications of camera - projector systems.

Got my BTP

Yesterday I got my BTP under Prof. X inspite of doing absolutely nothing on the hons. project under him for the whole of 5th semester. There were reasons for not working. The combination of me and my partner was not right. Moreover, neither of us was actually interested in the project that we got - SBD. So we ended up doing nothing for the whole sem. But I am very grateful to Prof. X that inspite of all this he believed in us and alloted us BTPs. And yes we have now taken BTPs separately. Hope this concept of single would work out right.

And yes the BTP that I have got is really cool. It is to explore the various possible applications of Smart Camera - Projector systems and build and demonstrate a few of them. One of the possible cool applications could be:
Project the image of a piano on a table. And press those virtual 'projected keys'. The attached camera will track your hand movements and instruct the computer to produce the corresponding sounds and tones.

Cool... isn't it? No need to take a 2 m long 50 Kg bulky piano with you. Just take a 6x3x2 inch camera+projector system, attach it to ur laptop and releash the pianist inside you.... at home, on train, on flight, at picnic!!. And yes todays LCD projector + camera systems are of such small dimensions. And mind you THEY ARE POWERFUL.

I really like this project and won't disappoint Prof. X again.

FuckProxy project now has a comment page

I added this beautiful comment page for the FuckProxy Project. Please feel free to post your comments, suggestions, bugs there. Your comments are valuable to me.

Technorati: FuckProxy

FuckProxy fucking my exam...

Well.. my endsems are getting fucked coz of this FuckProxy project. I am wasting all my time on it instead of reading for the exams. Or may be its the other way around, I am working on it coz I don't want to read the stupid books. Whatever... the point is that my endsems are getting fucked.

Technorati: FuckProxy

TODO list for the FuckProxy Project

This is my current TODO list for the FuckProxy project:-

1. relative urls starting with / in css scripts not working correctly. e.g. google image . Needs to be corrected.
2. Need to put FP button in url hbox. Define size etc. for it. make a good image. make a transparent image.
3. Give options for whether user want the FP button on tool bar.
4. Add "view this page without fp" and "view link target without fp" to right click context menu.
5. squirrel mail not working. Don't know why. something has to be done.

Exams are on. No time...

Technorati: FuckProxy

Bad News for the FuckProxy Project

Well... it seems like IIIT Network is coming back to normal. That means my whole week effort on this FuckProxy Project is going to be waste. No users for this project now :(

Anyways, its good that network will be back. Slow speed is making our lives hell. I learned quite a lot while working on this project. Will continue this project if network is not back in time.

Technorati: FuckProxy, iiit, network

Now FuckProxy comes with a cool toolbar button!

Yes. I added a "FuckProxy Go" toolbar button just after the go button. This button will take you to the typed url through FuckProxy.
Had to spend 6 hours on it. Wasted my whole night. I am saying wasted because, just in 3 hours I have my endsem exam. And I haven't even started reading. Spent all time for a stupid FuckProxy Button.

Technorati: FuckProxy, iiit, internet

FuckProxy 0.1 Beta is released again!!

Yeah... This time FuckProxy is a firefox extension and not a greasemonkey script. So easier installation and easy to use!
So what are you waiting for? Get FuckProxy.
For those who don't know what is FuckProxy project, here is a brief description:-
Most of the time IIIT's proxy(204) goes down even when the ISP link is perfect. In such cases internet can be accessed using 200. FuckProxy firefox extension lets you do that by using 200 as a CGI Proxy.
Adds a "View this page with FuckProxy" or "Open Link Target with FuckProxy" option to your Firefox right-click menu, depending on where you click. Also adds a "View with FuckProxy" Button for the address bar.

There is one more good news:-
I have succeeded in my search for a IIIT system that connects to net without proxy. I am testing it for speed and then I will include it in my project.
Enjoy!!

Technorati: cgi, FuckProxy, iiit, internet

Finally FuckProxy 0.1 Beta is released!

I have been saying in the last 3-4 posts that FuckProxy is almost complete. Well now it is fully complete and I have formally released FuckProxy 0.1 Beta.
For more on "why and what of FuckProxy?", visit my previous post.

I found that most of the time IIIT's proxy(204) goes down even when the ISP link is perfect. In such cases internet can be accessed using 200. This Greasemonkey(what is Greasemonkey) script lets u do that by using 200 as a CGI Proxy.

How to install?

1. Install Firefox (If you don't have it)
2. Install Greasemonkey Firefox Extension (If you don't have it, and restart Firefox)
3. Install FuckProxy

Thats it. Now whenever 204 is down, click on Tools->Greasemonkey->User Script Commands->Enable FuckProxy. And start browsing!
[Note : When you install FuckProxy for the first time, remember to refresh any one of the page. Or open a new tab and type some url.]

If you want to stop using FuckProxy then click on Tools->Greasemonkey->User Script Commands->Disable FuckProxy.

Have Fun!!

PS: Then name FuckProxy was coined by my friend Bharat Joshi. Thanks to him for providing me with such a creative name.

Technorati: cgi, FuckProxy, iiit, internet

Trim, ltrim, rtrim / strip, lstrip, rstrip fucntions for javascript

In programming, trim or strip is a string manipulation function or algorithm which removes leading and trailing whitespace from a string. ltrim removes only leading trailing whitespaces and rtrim removes only trailing whitespaces and trim removes both leading and trailing whitespaces.
Trim, ltrim and rtrim are also known as strip, lstrip and rstrip, respectively.

Javascript does not have its own trim or strip function. But you can define your own. Write the codes given below in your source code and you can use them as you do in other languages. Take care, that these codes should be written in your code before they are called.

trim:

String.prototype.trim = function() {
return this.replace(/^\s*|\s*$/g, "")
}

ltrim:

String.prototype.trim = function() {
return this.replace(/^\s*/g, "")
}

rtrim:

String.prototype.trim = function() {
return this.replace(/\s*$/g, "")
}

After writing the above codes you can use the functions normally. A few examples are:-

trimmed_str=str.trim();
trimmed_str=' someString '.trim();
str=str.ltrim();
str=str1.rtrim() + str2.rtrim();

Technorati: javascript, programming, code-snippets

One Alternative down

Out of the two alternatives that I came out with in my last post, the second one is down.
I searched for ways to how to change the url just before it is fetched. But could not find satisfying solutions.
But the first option is still alive. In fact, I got a few promising solutions. This site lists a few http proxy servers that have been made in python that do not need superuser privileges. The one that I downloaded requires python 2.4 and our 200 is still in the old age of 2.3. So I will have to select some other one. Lets see...
And yes FuckProxy is on its way. Its almost complete.

Technorati: bakwas, FuckProxy, http, iiit, internet, python

Technorati Claim - Ignore this post

Wrote this put just to claim my blog on technorati.
Ignore it.

Technorati Profile

Alternatives to FuckProxy

My mind travels faster than speed of light. FuckProxy is not even complete and I have already thought of two more approaches to tackle this same problem. And did I mention that the FuckProxy project is my 6th approach for creating a proxy. Well... none of them was perfect and so I keep trying newer and newer approaches. FuckProxy is a totally new approach that uses greasemonkey. And its almost over. Beta version is just coming.
Well... now the alternatives:-

1. I heard newer versions of python have some built-in library for creating proxy servers. I could run such a proxy server on 200 and bingo nothing else needs to be done. This is not the proxy that I have been making for so long. This one is not like anonymous proxy, but exactly like the 204 proxy using port 8080. The only possible glitch could be the requirement of superuser privileges. I have not seen yet whether it needs super user privileges or not.

2. I could make a firefox extension that changes each url just before it is fetched. This will be very easy if I could find how to do it. No more parsing the page source or DOM.

I have also thought to improve FuckProxy. I could install my proxy cgi scripts, that is presently on 200, on several other iiit systems that have direct access to internet and my greasemonkey script could use all of them at random to balance the load, enhancing the user experience!

Technorati: cgi, FuckProxy, bakwas, iiit, internet

FuckProxy Project is coming out fine

The FuckProxy project is coming out fine. Its almost over.
Its actually a combination of python cgi + greasemonkey script that lets IIITians to browse net even when 204 is down.
What and why?
Recently, IIIT Hyderabad appointed stupid system administrators which are unable to manage IIIT's servers properly. It has been observed that 204 (our proxy), goes down frequently even when the ISP link is perfect. So I thought why not create a proxy on our 200 that would allow users to browse net even when 204 is down. Note that 200 connects without proxy(204). So one could easily browse net using 200!
But there is still a problem. 200 itself is so slow that it delivers mail late by 1-2 days sometimes. So, my FuckProxy script gets extremely slow. So, I am searching for some other system in IIIT that connects without 204 and is not slow. Then I will use that machine for my FuckProxy script.

Another idea that is striking my mind right now is:-
IIITs net connection has gone extremely slow. Again thanks to the stupid sysadmins. I think that if this problem is due to misconfigurations with the proxy server and not due to the ISP link being slow, then I could use my FuckProxy script with some decent IIIT system that connects without proxy to provide better speed!! It would be so good. But first I have to search for such a decent machine. Lets see...

Technorati: FuckProxy, iiit, internet

Server Side 301, 302 HTTP Response Header Redirect in python

Today while working on my FuckProxy project, I got totally frustrated while writing the code for 301 redirect http response header in python.
PHP has this small and easy to use code for it:-

header('HTTP/1.1 301 Moved Permanently');
header('Location: '.$location);

But for python no such function exists. Moreover I spent 2-3 hrs on net searching for it. But there was no exact answer. Finally by several hit-and-trials and using the information collected from net, I could do it:-

print "Status: 301"
print "Location: " + location
print
sys.exit(1)

Of course, you must include sys using "import sys" statement.
For 302 (temporary redirect) just replace 301 to 302 in above code.
Thats it.
Done!!

Technorati: python, cgi, http

Hello World

So this is the customary "Hello World" post.
Well.. I have started this blog to maintain personal notes and reports on whatever little technical *bc* I keep doing now and then. My winds keeps wandering in endless regions and sometimes I take some silly idea seriously and start working on it. I need to record all those things for my future reference. I work in bursts and I need some way to recall exactly what I did before and what I was thinking before.
At first I thought to keep this blog private... as it is for my own reference. But then, on a second thought, may be my little *bc* work may be of some help to some wannable geek sitting in some other corner of the world. Also a little extra money through google adsense program never hurts :D
So guys and gals, wish me luck for all my future technical endeavours.
Bye for now.

Technorati: bakwas, personal