FFT in 1 and 3 dimensions written in C++

Hi,
i together with Christopher diggins have written a program which enables one to compute FFT in 1,2 and 3 dimensions in C++.
For this above mentioned program, visit my homepage
www.mpi-hd.mpg.de/personalhomes/kapoor

bit reversing program in C++

Hey all,
Today is a really happy night for me, after alot of searching and learning programming I have developed a bit reversing program written in C++ and directed towards implementation of FFT. The program inputs the data as vectors and then stores all the vectors at even places as real vectors and all vectors at imaginary places as imaginary vectors. This means the real part of the vector occupies position f(0), f(2), f(4) and so on. Similarly for imaginary parts of the vectors.

Once we have input the data I exploit the symmetry called the mirror symetry that the top half portion of the numbers to be bit reversed is the image of the bottom half numbers to be bit reversed or vice versa.

Hence one way to make the algorithm fast is to divide it in top and bottom and do the bit reversing for both in the same step, treating it as the mirror image of the another. One can work out the steps of algorithm by hand first to see that they give the proper answer. I had been searching alot on internet but could not find much help directly and in bits n pieces as a newbie to C++ I developed the first version of my program. There will be improvments in it every day till it is perfect but for the kodak moment that it is for me I could not resist the tempation of helping others out by giving them a handy program just to be copied and run by g++!.
Here is the code
#include < iostream >
#include < fstream >
#include < cmath >
#include < complex >
#include < vector >
#define swap(a,b) {temp=a;a=b;b=temp;}
using std::cout;
using std::cin;
using std::endl;
using std::ofstream;
using std::ifstream;
using std::complex;
using std::vector;
int main()
{
ofstream file ("swap.dat");
//complex < double > I = complex < double >(0,1);
int x,i,j,k,n,m;
const int N=16;
double temp;
vector < float > realdata(N);
vector < float > imagdata(N);

n=N/2;
for(x=0;x < n;x++){
realdata[2*x]=x; imagdata[2*x+1]=x;
}
j=0;
for(i=2;im=n;
while(j>=m){
j-=m;
m>>=1;
}
j+=m;
if(j>i){
swap(realdata[j],realdata[i]);
swap(imagdata[j+1],imagdata[i+1]);
if(j < n)
{
swap(realdata[N-j-2],realdata[N-i-2]);
swap(imagdata[N-j-1],imagdata[N-i-1]);
}
}
}
for(i=0;i< n;i++){
file << realdata[2*i]<< " "<< imagdata[2*i+1] << endl;
}
return 0;
}
Enjoy!!

Kile and latex features

The people who are typing alot will probably know that latex is one of the most powerful text editors available. Using latex we can have the most accurate and desirable typesetting we want and is very good for writing equations and other mathematical stuff.
The latex requires a platform to be written on, like generally people who write word documents use the openoffice software or microsoft office. Conventionally people have been using VIM or Emacs as the text editor, but now some more versatile editors have developed, kile is one of them.
To give a brief introduction to what latex is and can do, for people who are new to this feature, I will summarize it here first. Unlike word documents where we just enter texts and take the help of the in built functions to give the document a customized look, in latex we can actually do anything by including the package files and knowing the commands to modify the way the text is displayed. It is not just about the text but also about the graphics and the drawings that can be added to the document, the most important benefit of latex is in the typesetting of the equations which can be aligned in a proper way and there is more freedom in modification than just the in built functions in word writers. The latex document begins by inclusion of standard packages and fonts which we have to write the document in, there are various options of making a latex file. We can either choose it to have an article format or a letter or a report and also the thesis. Most of the scientific papers and presentations and the thesis are written in latex and then converted to pdf or ps files using the command line. The start of the document looks like


\documentclass[12pt,notitlepage,axodraw]{report}
\usepackage{setspace}
\doublespacing
%\onehalfspacing
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[left=1.8in, right=1.5in, top=1in, bottom=1in, includefoot]{geometry}
%\usepackage{a4wide}

\usepackage[hang, small, bf, margin=20pt, tableposition=top]{caption}
\setlength{\abovecaptionskip}{0pt}
%\usepackage{mathpazo}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage[english]{babel}
\usepackage{slashed}

\usepackage{fancybox}
\usepackage{fancyhdr}
\usepackage{axodraw}

\usepackage{latexsym}

\begin{document}
\begin{titlepage}
The % before \ indicates that they are not used by the latex editor while compiling and are just like the comments and when we want the latex to use them we can remove % and then they will be included while compilation of the latex document. The spacing of the whole document is affected by the choice \doublespacing or \onehalfspacing. If we do not have to have any specific spacing we can just not mention anything and the document will look like a normal pdf file with normal spacing between the various lines. The other packages are the instructions to use the maths symbols, fonts and graphics packages, so that we can include any diagram and include equations in our document. The special package axodraw is a package to include feynman diagrams involving photons, gluon and quarks in the document.
Next we have the content page and the page numbers, this can be automatically included as we keep writing our document by including the command line
\thispagestyle{plain}
\tableofcontents{}
{}
\nextpage
the command of \nextpage will take the text and diagrams to the next page and all we write in various chapters will be automatically shown in the table of contents with page numbers once we compile the document.
Then we come to having special greek symbols which come now and then in science. Such symbols can be included simply by writing them first between the dollar signs, $. For example i want to write lambda, I will write it as $\lambda$ or if I have to make it capital greek letter I will write it simply as $\Lambda$. This holds true for all the other greek symbols. When we have to include something in subscript or superscript we do this as $\lambda_{QCD}$ and $\lambda^{QCD}$ respectively. Crucial is to specify the braces at the beginning and ending of the quantity written as a subscript or a superscript.
Now we come to writing equations in latex, if we want our equations not to have a number, this will be written as $$ $$\int_{0}^{1}Sin[x] dx $$. The double $$ sign puts the equation in the new line, a single dollar sign will not write it as a new line but will include it as a part of the line it was written after and in the same line. If we want to number our equations, we can do this by writing the equations insde the following
\begin{equation}..............\end{equation}
Where ...... indicate the equation that has to be written. Integrals can be easily written as above by $\int$ such basic symbols can be found on the internet where they have long lists of symbols compiled for use in the latex document and we will not go into that aspect here as it is easily available in the google search!
Now we come to some style of writing the equations. If the equations are big and have to be aligned properly, the begin equation command will make it go out of the paper, better is to use $$\begin{eqnarray}&&............&& &&...........&&\end{eqnarray}
where the dots refer to the part of equation you want to fit in the first line, && symbol marks the start and end of the line, rest of the equation comes in second and sucessiding lines, by use of this technique. However this will start assigning equation number to every line and we probably want only one number or none,so the trick is to put \nonumber at the end of each && operator marking the end of the equation line. So that sorts it out.
Another thing is about using proper braces in these equations, if we just use ({[ as they are, they will appear as they are, but sometime we want them to cover the entire body of the start and end of the equation, we can do this by saying \left( and ending it with \right). However this does not works when we are using eqnarray and trying to set braces across the && in two different lines. But thats ok I guess!
Now it brings us to kile, it is a very good equation editor for latex. it can be downloaded in fedora systems by typing in the command line sudo yum install kile and in ubuntu by sudo apt-get install kile. This has several features like automatic completion of latex commands when we just start writing the command. This also tries to make the word users more familiar with the latex environment as it has a similar template as the word editor. Besides it has the option of choosing the kind of document we want to write with latex, whether a report or an article or anything else, including beamer! Beamer is used for presentations and is a substitute of the windows power point presentation.
The commands for compiling a latex document which is saved as .tex document are simple to follow. in the terminal type in
latex documentname.tex
This will compile the latex document and issue errors in the lines where they are in the document. One of the basic error can be that latex could not find the package you included at the start of the document, this can be removed by simply including the relevant .sty file in the folder where you have the latex document as then the latex will automatically locate it while compiling. Other errors are due to forgotten $ signs or due to not putting } at the end or start. Its very easy to get confused in the braces, like you are typing a fraction with alot of subscripts, $$dfrac{p_{g}.p_{q}}{Q}$$. Here we have to be careful in using the braces and this error will stop the compilation of the document and you wont be able to see anything after this.
After the compilation stage we get a .dvi file,this is converted to a ps file first by typing in the terminal :-
dvips -Ppdf documentname.dvi
Then we can convert the ps file we get by
ps2pdf documentname.ps
And then we have created out pdf file!
Infact linux has many good commands to convert one format to another, which can be installed using yum or apt-get. Like if I want to convert eps to ps I will type in the terminal convert documentname.eps documentname.ps and vice versa.
The eps is the encapsulated post script file which is included in the main latex document. This can be a diagram made in Xfig or a mathematica.nb file to be included in the document.
Once we know these basic steps we can start writing documents, dissertations very easily and diligently using latex. After we are above the barrier of using latex properly typing a document perfectly is only about how good your language skills are! Infact one can also check the spelling by typing in the terminal ispell documentname.tex. Just remember to be in the same folder as your document when typing the commands in the terminal!
Have fun with linux and latex ;). Here is a snapshot of it
http://kile.sourceforge.net/showscreenshot.php?id=7

Ubuntu-Revolution Operating System

I came into the UK in the department of physics to do my M.Phil degree in high energy physics. I was under the impression that the computer facility will be state of the art and much better than what we see in the Indian institutions.
However the truth was far from what I imagined. The computers were having outdated hardware and the version of linux required an update and of course better administrators! Hence I thought of asking the department for a laptop but they refused. Armed by my hard earned money from tutions here I thought, I will buy my own laptop.
So then began the search for finding a laptop that will suit my needs, which were just having email programs and a good screen to watch movies. SO I picked up an Acer Aspire 7520 gemstone with 17 inch screen. It came with windows vista home premium preloaded. I wanted to install linux on the system as I am more used to it but windows is more powerful and has better graphics than usual linux operating system.
In this search I go an opportunity to install ubuntu, which I had heard about before. With the help of my friend Sam I installed ubuntu removing windows completely from the hard drive. Then came some problems.
The first problem was concerning the games in ubuntu. There were not many 3-d games to be played or installed in the system and this was a constraint in using this operating system. Then was about the pidgin messenger which did not have voice or video support. Also another important feature missing was the wireless support. But then these were the cons, there were many good things which made people weigh more in favour of ubuntu.
The good things included the ease of installation the operating system which you can get for free and burn an iso image to your cd from the cite : http://www.ubuntu.com/
The problem of wireless has been solved now and we can take our ubuntu wherever we want to take it with us. This is the result of the programmers all around the world participating in the revolution of free software movement. For those people who still are using the versions till 8.04 version of ubuntu there is an easy way to install it if you follow these steps:http://madberry.org/2008/08/how-to-get-atheros-ar242x-wireless-to-work/
They are summarized here :-
First if the computer has a chipset run in terminal:

lspci | grep Atheros

If the result is as follows or something similar then you are able to use this fix.

05:00.0 Ethernet controller: Atheros Communications Inc. AR242x 802.11abg Wireless PCI Express Adapter (rev 01)



In Terminal go to your desktop:

cd ~/Desktop

Then download the Madwifi driver needed for this How to:

wget -c http://madberry.org/wp-content/madwifi-ng-r2756+ar5007.tar.gz

Untar the Image file(don’t worry it will create a new folder):

tar xvf madwifi-ng-r2756+ar5007.tar.gz

Go into the just created dir:

cd madwifi-ng-r2756+ar5007

Because we are going to compile from source code we need to make sure the essentials to do so are installed.

Compile
use a computer program to translate source code written in a particular programming language into computer-readable machine code that can be executed.

Hide

Source Code

The underlying code that makes up a software program. Most commercially available programs come in “binary” form, which is nearly impossible for humans to comprehend. Source code, however, is comprehensible, and if you have it, you can learn how a program does something, change it so it does something else, or otherwise improve it. True geeks swear by source code.

Hide

sudo apt-get update && sudo aptitude install build-essential

Now run:

sudo make install

sudo modprobe ath_pci

sudo modprobe wlan_scan_sta

If you get any errors running the modprobe commands you probably forgot to switch off the modules in the first place go back to this and then try modprobe again.

Now the same as we did before:
Click on the Kubuntu start button go to system and click on the “Hardware Drivers Manager” this is where you will find all proprietary drivers. But we’re looking for everything that has Atheros in it. Tick the box in behind of “Atheros Hardware Access Layer(HAL)” and “Support for Atheros 802.11 wireless LAN cards” and restart the computer.

Now you have wireless.


Keep in mind that every time the Kernel gets updated you have to run these commands again:

sudo apt-get update && sudo aptitude install build-essential

Now run:

sudo make install

sudo modprobe ath_pci

sudo modprobe wlan_scan_sta

Off course in the madwifi folder. You might want to move the folder to your home folder because we’ll need it again after a Kernel update.

To get your wireless back up that is until they fix the problem in the Kernel and wireless works after restarting with the new Kernel.

Ubuntu is a free software and will always remain free, it is even free of cost! Free software does not means free in price but the software which gives you freedom to share among yourself and improve upon it as per your wishes, that is it comes with the source code which people can modify as per their wishes.
There are a vast amount of programs available through the synaptic package manager or through sudo apt-get install from the terminal line.
There are so many programs to play media which you can get from one line commands or just using the package manager. Amarok replaces the apple i-tunes and youtube and bbc videos can be watched in totem media player. And guess what if you can programa nd make good programs, even you can participate in the revolution of free software movement. I am myself trying to make a free mathematica software for ubuntu as my first project and so can anyone contribute and reap the benefits of this free software movement.
The only good thing about Manchester was to give a 1GB pen drive which I use whenever I can for data transfer :).

Linear Hadron Collider----CERN

The Large Hadron Collider (LHC) is a particle accelerator and collider located at CERN, near Geneva, Switzerland (46°14′00″N, 6°03′00″E). Currently under construction, the LHC is scheduled to begin operation (at reduced energies) in November 2010.You can find the clock at the cite of http://www.nikhef.nl/ The LHC is expected to become the world's largest and highest energy particle accelerator in 2011, when commissioning at 7 TeV is completed. The LHC is being funded and built in collaboration with over two thousand physicists from 34 countries, universities and laboratories. Including TIFR,P.U,D.U in india.

The collider is contained in a 27 km circumference tunnel located underground at a depth ranging from 50 to 150 metres [1]. The tunnel was formerly used to house the LEP, an electron-positron collider. The 3 metre diameter, concrete-lined tunnel actually crosses the border between Switzerland and France at four points, although the majority of its length is inside France. The collider itself is located underground, with many surface buildings holding ancillary equipment such as compressors, ventilation equipment, control electronics and refrigeration plants.

The collider tunnel contains two pipes enclosed within superconducting magnets cooled by liquid helium, each pipe containing a proton beam. The two beams travel in opposite directions around the ring. Additional magnets are used to direct the beams to four intersection points where interactions between them will take place.

The protons will each have an energy of 7 TeV, giving a total collision energy of 14 TeV. It will take around 90 microseconds for an individual proton to travel once around the collider. Rather than continuous beams, the protons will be "bunched" together into approximately 2,800 bunches, so that interactions between the two beams will take place at discrete intervals never shorter than 25 nanoseconds apart. When the collider is first commissioned, it will be operated with fewer bunches, to give a bunch crossing interval of 75 nanoseconds. The number of bunches will later be increased to give a final bunch crossing interval of 25 nanoseconds.

Prior to being injected into the main accelerator, the particles are prepared through a series of systems that successively increase the particle energy levels. The first system is the linear accelerator Linac2 generating 50 MeV protons which feeds the Proton Synchrotron Booster (PSB). Protons are then injected at 1.4 GeV into the Proton Synchrotron (PS) at 26 GeV. The Low-Energy Injector Ring (LEIR) will be used as an ion storage and cooler unit. The Antiproton Decelerator (AD) will produce a beam of anti-protons at 2 GeV, after cooling them down from 3.57 GeV. Finally the Super Proton Synchrotron (SPS) can be used to increase the energy of protons up to 450 GeV.

Six detectors are being constructed at the LHC. They are located underground, in large caverns excavated at the LHC's intersection points. Two of them, ATLAS and CMS are large, "general purpose" particle detectors. The other four (LHCb, ALICE, TOTEM, and LHCf) are smaller and more specialized.

The LHC can also be used to collide heavy ions such as lead (Pb) with a collision energy of 1,150 TeV.

The size of the LHC constitutes an exceptional engineering challenge with unique safety issues. While running, the total energy stored in the magnets is 10 GJ, and in the beam, 725 MJ. Loss of only 10−7 of the beam is sufficient to quench a superconducting magnet, while the beam dump must absorb an energy equivalent to a typical air-dropped bomb. For comparison, 725 MJ is equivalent to the detonation energy of approximately 157 kg (347 pounds) of TNT, and 10 GJ is about 2.5 tons of TNT.