4 bit Arithmetic Circuit

Basic Theory:

An arithmetic circuit is a logic circuit that performs basic arithmetic operations like addition, subtraction, increment, decrement and transfer operations using a single combinational circuit. It uses multiplexers and full adders to do so. The selection bits, along with an additional input at 2 and 3 input positions of the multiplexer, determine the type of operation to be done on the input data. This is further clarified by the function table below. As usual, a 4-bit arithmetic circuit works with 4-bit data.

Function Table for Arithmetic Circuit:

Circuit Diagram:

Reference:

Mano, M. (n.d), Register Transfer and Micro-operations: Arithmetic Circuit, Computer System Architecture (3^rd Edition), pp. 106-108

8085 program to convert 8-bit binary to BCD

LXI H, 8D02
MOV A, M
MVI C, D
MVI B, 0

HUN:
SUI 64H
JC TENS
INRC
JMP HUN

TENS:
ADI 64H

LOOP:
SUI 0AH
JC UNITS
INR B
JMP LOOP

UNITS:
ADI 0AH

INX H
MOV M,C
INX H
MOV M,B
INX H
MOV M,A
HLT

Observation:

	Memory	Content
Input	8D02H	8D
Output	8D21H	01
	8D22H	04
	8D23H	01

©Dixit Bhatta 2013

C program for Round Robin Scheduling Policy

#include<stdio.h>

#include<conio.h>

#define MAX 5

void main (){

                clrscr();

                int pname[MAX],brtime[MAX];

                int end[MAX+1],start[MAX];

                int qtm,total=0,rem =0;

                int num = 0, i;

                for(i=0;i<MAX;i++){

                                brtime[i] = 0;

                }

                printf("\t\tRound-Robin SCHEDULING");

                printf("\nEnter the number of processes  (max. 5): ");

                scanf("%d",&num);

                printf("\nEnter the quantum size: ");

                scanf("%d",&qtm);

                for(i=0;i<num;i++){

                                printf("\nEnter process name, burst time: ");

                                scanf("%d %d",&pname[i],&brtime[i]);

                                total= total + brtime[i];

                }

                rem = total;

                printf("\n");

                while(rem!=0){

                                for(i=0;i<num;i++){

                                                if(brtime[i]==0){

                                                                //do nothing

                                                }

                                                else if(brtime[i]>=qtm){

                                                                brtime[i] = brtime[i] - qtm;

                                                                printf("\n%d ->%d",pname[i],qtm);

                                                                rem = rem- qtm;

                                                }

                                                else{

                                                                printf("\n%d ->%d",pname[i],brtime[i]);

                                                                rem= rem - brtime[i];

                                                                brtime[i]=0;

                                                }

                                }

                }

                printf("\n\nTotal Time = %d",total);

                getch();

 }

Sample Output:

                       Round-Robin SCHEDULING

Enter the number of processes (max. 5): 3

Enter the quantum size: 3

Enter process name, burst time: 1     6

Enter process name, burst time: 2     2

Enter process name, burst time: 3     7

1 ->3

2 ->2

3 ->3

1 ->3

3 ->3

3 ->1

Total Time = 15_

©Dixit Bhatta 2013

C program for Cubic Spline Interpolation

#include<stdio.h>
#include<conio.h>
#include<math.h>

void main(){
clrscr();
char choice='y';
int n,i,j,k;
float h[10],a,b,c,d,sum,s[10]={0},x[10],F[10],f[10],p,m[10][10]={0},temp;

printf("No of samples? ");
scanf("%d",&n);
printf("\nEnter all sample points: ");
for(i=0;i<n;i++)
scanf("%f%f",&x[i],&f[i]);
for(i=n-1;i>0;i--){
F[i]=(f[i]-f[i-1])/(x[i]-x[i-1]);
h[i-1]=x[i]-x[i-1];
}
//*********** formation of h, s , f matrix **************//
for(i=1;i<n-1;i++){
m[i][i]=2*(h[i-1]+h[i]);
if(i!=1){
m[i][i-1]=h[i-1];
m[i-1][i]=h[i-1];
}
m[i][n-1]=6*(F[i+1]-F[i]);
}
//*********** forward elimination **************//
for(i=1;i<n-2;i++){
temp=(m[i+1][i]/m[i][i]);
for(j=1;j<=n-1;j++)
m[i+1][j]-=temp*m[i][j];
}
//*********** backward substitution *********//
for(i=n-2;i>0;i--){
sum=0;
for(j=i;j<=n-2;j++)
sum+=m[i][j]*s[j];
s[i]=(m[i][n-1]-sum)/m[i][i];
}
while(choice=='y'){
printf("\nEnter x : ");
scanf("%f",&p);
for(i=0;i<n-1;i++)
if(x[i]<=p&&p<=x[i+1]){
a=(s[i+1]-s[i])/(6*h[i]);
b=s[i]/2;
c=(f[i+1]-f[i])/h[i]-(2*h[i]*s[i]+s[i+1]*h[i])/6;
d=f[i];
sum=a*pow((p-x[i]),3)+b*pow((p-x[i]),2)+c*(p-x[i])+d;
}
printf("\nCoefficients of sub intervals are : %f\n%f\n%f\n%f",a,b,c,d);
printf("\nFunctional value is: %f",sum);
printf("\nContinue (y/n) ? ");
scanf("%c",&choice);
}
getch();
}

Sample Output:

No of samples? 5

Enter all sample points: 1     2

2     3

3     4

4     5

5     6

Enter x : 3.5

Coefficients of sub intervals are : 0.000000

0.000000

1.000000

4.000000

Functional value is: 4.500000

Continue (y/n) ?

©Dixit Bhatta 2013

C++ program for Newton-Raphson Method

#include<iostream.h>
#include<conio.h>
#include<math.h>
#define EPS 0.000001
#define MAXIT 20
#define F(x) (x)*(x)*(x)+(x)*(x)-3*(x)-3
#define FD(x) 3*(x)*(x)+2*(x)-3

void main(){
clrscr();
int count;
float x0, xn, fx, fdx, fxn;
cout<<"             NEWTON RAPHSON'S METHOD";
   cout<<endl<<"x^3+x^2-3x-3";
cout<<endl<<"Enter the initial value of x:";
cin>>x0;
count=1;

begin:
fx=F(x0);
fdx=FD(x0);
xn=x0-fx/fdx;
if (fabs((xn-x0)/xn) < EPS){
cout<<"Approximate Root: "<<xn<<endl;
fxn =F(xn);
cout<<"Functional Value: "<<fxn<<endl;
cout<<"No. of Iterations: "<<count<<endl;
}
else{
x0=xn;
count=count+1;
if(count<MAXIT){
goto begin;
}
else{
cout<<"SOLUTION DOES NOT CONVERGE!!"<<endl;
cout<<"Iterations: "<<MAXIT<<endl;
}
}
getch();
}

Sample Output:

                    NEWTON RAPHSON’S METHOD

x^3+x^2-3x-3

Enter the initial value of x:2

Approximate Root: 1.73205

Functional Value: -2.94213e-07

No. of Iterations: 4

©Dixit Bhatta 2013

Flowchart Vs Pseudocode

A flowchart is a diagram showing an overview of the problem. It is a pictorial representation of how the program will work, and it follows a standard format. It uses different kinds of shapes to signify different processes involved in the problem. It is capable of showing:

-tasks to be carried out, manually or automatically

-the type of task being carried out

-the flow of instructions or steps

-the devices used for input, output, and storage

-the files used in the process

Similarly, a pseudocode is a means of expressing the stepwise instructions for solving a problem without worrying about the syntax of a particular programming language. Unlike a flowchart, it uses a written format which requires no absolute rules for writing. It can be written in ordinary English, and we can use some keywords in it too. For instance, to assign the value 5 to a variable y, we can write the pseudocode in any of the ways shown below.

Assign 5 to y

y ← 5  

y = 5

put 5 in y

The advantage of pseudocode over flowchart is that it is very much similar to the final program code. It requires less time and space to develop, and we can write it in our own way as there are no fixed rules.

However, flowchart is capable of showing the overall flow of instructions from one process to another and even files and devices involved in the process. We can see the individual processes just at a glance (like the number of decision making operations). In terms of a conceptual model, it is easier to show iteration (loops) and conditional statements using flowchart, which in case of pseudocode, can easily be as complex as the program code. Furthermore, flowcharts follow a standard format which makes it easy to explain to other programmers. Therefore, I prefer flowcharts to pseudocode.   

Reference:

Heathcote, P.M. (2000), More on Selection and Iteration, Systems Design, Development, ‘A’ Level Computing (4th Edition), pp. 42, 43, 305 and 306.

Advantages and Disadvantages of Recursion (Recursive Algorithm)

A procedure or subroutine is recursive if it calls itself, and this process is known as recursion. Commonly, a non-recursive solution to a programming problem is more efficient in both runtime and memory space basis than a recursive one. It is due to the need of making multiple function calls. The function is called each time of the recursive step until the stopping condition is satisfied. Also, every time it goes through a recursive step, it has to store the return addresses and copies of local variables, all of which makes it consume a lot of time as well as memory.

Another fact we need to consider is that if the number of recursive steps is very large, we can actually run out of memory space causing the memory stack overflow, and the program to crash. Say if we want to recursively display the Fibonacci series up to 2000^th number, the program would have to handle 2000 return addresses, and a lots of local variables, which is very inefficient than a simple iteration using a for-loop.

However, recursive functions are relatively shorter, and hence easier to write and debug. For some complex problems, they could present a very easy and straightforward solution, like Binary Search and Quick Sort. Basically, if recursive algorithm is not much shorter than the non-recursive one, we should always go for the non-recursive one. A well written iteration can be far more effective and efficient in such cases.

Reference:

Heathcote, P. M. (2000), Recursion, ‘A’ Level Computing (pp. 235- 237), Ipswich, UK: Payne-Gallway Publishers 

C Program for Bisection Method

Basic Theory:

The bisection method is a method to find the real root of an equation in which the interval is always divided into half for every new iterative step. If a function changes sign over an interval, the functional value at the mid-point is evaluated. The location of the root is then determined to be within the sub-interval where the sign change occurs. The sub-interval thus becomes the interval for next iteration. The process is repeated until the root is known to the required precision.

Following is a numerical example of Bisection method.

Consider finding the root of f(x) = x² - 3. Let Error = 0.01 and start with the interval [1, 2].

Table 1: Bisection method applied to f(x) = x² - 3.

a	b	f(a)	f(b)	c = (a + b)/2	f(c)	Exchange	Error
1.0	2.0	-2.0	1.0	1.5	-0.75	a = c	0.5
1.5	2.0	-0.75	1.0	1.75	0.062	b = c	0.25
1.5	1.75	-0.75	0.0625	1.625	-0.359	a = c	0.125
1.625	1.75	-0.3594	0.0625	1.6875	-0.1523	a = c	0.0625
1.6875	1.75	-0.1523	0.0625	1.7188	-0.0457	a = c	0.0313
1.7188	1.75	-0.0457	0.0625	1.7344	0.0081	b = c	0.0156
1.7188	1.7344	-0.0457	0.0081	1.7266	-0.0189	a = c	0.0078

Thus, with the seventh iteration, we note that the final interval, [1.7266, 1.7344], has a width less than the value of Error and |f(1.7344)| < 0.01, and therefore we chose b = 1.7344 to be our approximation of the root.

Program:
#include<stdio.h>

#include<conio.h>

#include<math.h>

#define f(x) x*x*x-2*x-5 //define the function here

void main(){

clrscr();

float x1 = 2, x2 =3, E=0.0005, x0; //define initial values and errors here

float f1 = f(x1), f2 = f(x2), f0;

float root;

                if(f1*f2>0){

                                goto last;

                }

printf("\n\t\t\tBISECTION METHOD");

printf("\n\n  FINDING ROOT OF x^3-2x-5");

printf("\n\n  X1\t  X2\t  X0\tf(X0)\t  Error");

printf("\n  -------------------------------------");

back:

x0 = (x1+x2)/2;

f0 = f(x0);

printf("\n  %.3f\t%.3f\t%.3f\t%.3f\t%.5f",x1,x2,x0,f(x0),fabs((x2-x1)/x2));

//print in tabular form

                if(f1*f0<0){

                                x2= x0;

                }

                else{

                                x1=x0;

                                f1=f0;

                }

                if(fabs((x2-x1)/x2)<E){

                                root = (x1+x2)/2; //display root if required precision is met

                                printf("\n\n  Approximate Root = %.5f", root);

                                goto last;

                }

                else{

                                goto back;

                }

last:

getch();

}

Sample Output:

     BISECTION METHOD
FINDING ROOT OF x^3-2x-5

X1          X2       X0      f(X0)      Error
------------------------------------------------
2.000   3.000   2.500   5.625    0.33333
2.000   2.500   2.250   1.891    0.20000
2.000   2.250   2.125   0.346    0.11111
2.000   2.125   2.062   -0.351   0.05882
2.062   2.125   2.094   -0.009   0.02941
2.094   2.125   2.109   0.167    0.01471
2.094   2.109   2.102   0.079    0.00741
2.094   2.102   2.098   0.035    0.00372
2.094   2.098   2.096   0.013    0.00186
2.094   2.096   2.095   0.002    0.00093
2.094   2.095   2.095   0.002    0.00047


Approximate Root = 2.09424 

©Dixit Bhatta 2013