Archive for category linux

Recursion

Every passionate programmer through one stage of his career must have tried this out and surely must have loved it. .These are not the best methods to solve problems, yet many complex problems have their natural solution as recursive ones. We have a lots of recursive patterns in nature to be observed. One of the most common is  a tree of which each branch is a tree in itself (though smaller  in size).

  

Even some geometric shapes (fractals) can also be observed to have recursive patterns. You can observe the repeating pattern which is being created recursively.

       

My python function for Koch-Snow flake (fractal) .

def flake(self,length):
if length < 10:
self.move_forward(l)
self.c.update()
return
else:
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)
self.rotate_right(120)
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)

My code for the above is available here

Ackermann function

One of the most interesting recursive problems I’ve encountered.

def A(m,n):
if m == 0:
return n + 1
elif n == 0:
return A ( m - 1 , 1 )
else:
return A ( m - 1,  A ( m, n - 1 ) )

It will be observed the behaviour of the function can not be predicted unless the values of the parameters ‘m’ and ‘n’ are known.

This kind of programming might be simple enough but it has its own drawbacks too. These kind of programs might not be supported at production level as they might eat up the system stack and affect the performance drastically.

The size of process stack(8MB) on a standard linux machine can be easily be manipulated with ‘ulimit’ utility.

ulimit  -a

A simple C code to observe how a recursive program eats up the process stack.


void foo( int i ) {
char temp[ 1024 * 1024 ]; //1Mb of memory will be allocated from the stack-frame
printf (" %d \n", i );
foo ( i + 1 );

}

int main() {
foo( 1 );
}

Each time the ‘foo’ is invoked a new stack frame is created and a character array of 1 MB size is allocated from it  .So after a definite number of recursive calls when their is no more memory left it results in ‘‘segmentation-fault” when the program tries to allocate memory in the new frame( outside of process’s address-space).

Changing the size of the array ‘temp’ and size of stack using

‘ulimit    -s    <value>’

will give interesting results.

Tail-Recursion

Here the recursive procedure call is kept at the bottom of the procedure. This is of significant importance because an optimization technique can be used where no new stack frame is allocated for a recursive procedure call, instead the new frame can be used to replace the current frame.  This kind of optimization is called tail-call-optimization . Many functional Programming languages like to cope with this situation has implemented

I tried out some of both basic & classical recursive problems during my graduation years. Anyone who is interested with recursive patterns I suggest you to try out the below problems.

Eight Queens Problem  ,  Towers of Hanoi.  , Min-Max Algorithm   ,Creating  Fractal shapes SICP Chapter-1 (a lot of mind-bending problems are in there)

Advertisements

Leave a comment

Programming a "PARALLEL PORT" in C using "inb " and "outb()"

   
                           For programming a parallel port in C,the user program is supposed to get the permission for accesing  the I/O port using the call

iopl(permission value)

which changes the previlege of the calling process.
By default the user program has a permission value of 0.So for accessing the parallel port,the user program  is supposed to have a permission value of 3

iopl(3);

  • outb()

For porting a value onto the parallel – port,the function outb() is used .

outb(value,0x378); 


parallel port the out pins are from 2 to 9 pin.


outb(value,portaddr);

will port a byte to the portaddr address.
the port address is to be selected as follows 

for 
/dev/lp0     ——    0x378 
/dev/lp1     ——–   0x3bc

 
a simple program in C to port a value to the parallel port


inb(portaddr)

parallel port register set


there are three main registers for a parallel port

  • status register
  • controll register
  • status  register

so these registers are used to read  the values of specific pins

the address of the status register
/dev/lp0 — >  0x378
/dev/lp1 — >  0x

4 Comments

Internet connection through WLL BSNL in linux

I ‘m using a wireless Internet connection (BSNL WLL connction).This post may be of use to newbies in linux ,trying to connect to internet through a dial up connection.The first step to be done is

  • To install ‘wvdial’ 

In debian distro, the package is available in their distribution cd.For installation try the command

apt-get install wvdial

 the package can be downloaded from the link below

http://packages.ubuntu.com/hardy/i386/wvdial/download

the package can then be installed as

dpkg -i wvdial-xx.deb 

  •  configuring the file /etc/wvdial.conf

 now the file /etc/wvdial.conf has to be configured according to connection requirements ,the overall structure of the /etc/wvdial.conf can be obtained from link
http://ranjeethpt.wordpress.com/2009/08/27/working-with-arm-7/

my wvdial.conf file looks like the one below

[Dialer Defaults]
Init1 = ATZ
Init2 = ATQ0 V1 E1 S0=0 &C1 &D2 +FCLASS=0
Init3 = at+crm=1;+cmux=1;+cps=33;+cta=0
Stupid Mode = yes
ISDN = 0
Modem Type = USB Modem
New PPPD = yes
Phone = #777
Modem = /dev/ttyUSB0
Username = xxxxxxx
Password  = xxxxxxx
Baud = 460800

 here in the file for the users using BSNL – WLL  connection have to replace
username  and password provided to them by the service provider
Username = xxxxxxxx
Password = xxxxxxxx

now to be able to use the connection ,first we have to register the dial-up modem to their kernel.as provided in the link

 http://ranjeethpt.wordpress.com/2009/08/27/working-with-arm-7/

then the user can browse onto internet by just dialing

wvdial

in the terminal.

Leave a comment

Creating commands in linux by a simple C program

Below i’ll try to  give an idea about how bash commands are implemented in linux by illustrating a small example.

        Simple way to create a command( in C ) ‘hello’ which prints hello world.

  • Step1 :  Create a cprogram “test.c” to print the string “hello world” by          first opening the file “test.c” using the text editor “vim”

                    

                                 vim test.c  
                           
                         and then writing into it

                                #include
                                main(){
                                           printf(“hello world\n”); 

                                 }

  • Step 2  : now compile the program by using the compiler gcc

                                gcc test.c

                       to produce an executable file” a.out”.Now this file is the object file which prints the string “hello world” to the monitor.for executing the file we use as

                               ./a.out

  • Step 3 :  Actually, a command like “cp” has it’s executable file in the directory /bin ,so by copying our executable file to that folder we can use it as a command .

                              sudo cp a.out /bin/hello

         which prompts for the root password

             Now we can use the command “hello” in the bash prompt to print “hello world” on the screen.

Leave a comment