Thursday 21 March 2013

4 bit Binary Decrementer


Basic Theory:
The binary decrementer decreases the value stored in a register by ‘1’. For this, we can simply add ‘1’ to the each bit of the existing value stored in a register. This is basically the concept of two's complement used for subtraction of '1' from given data. It is made by cascading ‘n’ full adders for ‘n’ number of bits i.e. the storage capacity of the register to be decremented. Hence, a 4-bit binary decrementer requires 4 cascaded full adder circuits. As stated above we add '1111' to 4 bit data in order to subtract '1' from it. 

Circuit Diagram:


Observed Values:

Following set of values were obtained in observation.
1.      0011 => 0010
2.      1010 => 1001
3.      1101 => 1100
4.      0010 => 0001
5.      0000 =>1111

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

4 bit Binary Incrementer


Basic Theory:

The binary incrementer increases the value stored in a register by ‘1’. For this, it simply adds ‘1’ to the existing value stored in a register. It is made by cascading ‘n’ half adders for ‘n’ number of bits i.e. the storage capacity of the register to be incremented. Hence, a 4-bit binary incrementer requires 4 cascaded half adder circuits.

Circuit Diagram:


Observed Values:

Following set of values were obtained in observation.
1.      0011 => 0100
2.      1010 => 1011
3.      1101 => 1110
4.      0010 => 0011
5.      1111 => 0000; Cout = 1

Reference:
Gamezero.com (n.d.), Designing and Building our 4-bit Addition Engine, Processor Design, Accessed: February 15, 2013, Retrieved from: http://www.gamezero.com/team-0/articles/math_magic/micro/stage1.html

Wednesday 20 March 2013

4 bit Adder/Subtractor Circuit


Basic Theory:

It is possible to make a logical circuit that can do both addition and subtraction based on the mode selection concept. In case of a four bit adder-subtractor, two four bit binary numbers are added or subtracted on the basis of the operation mode. The main principle behind it is subtraction using the two’s complement method. 

The expression for this is:
Dn = A - B = A + B’ +1.

This kind of circuit is a ripple-carry adder circuit along with some additional XOR gates to add the subtraction functionality. It works as a full adder if the selected mode is 0 “zero”, and works as a full subtractor if the mode is selected as 1 “one”. The logic diagram can be seen below.

Circuit Diagram:


Observed Values:
Following set of values were obtained in observation.
For addition,
1.      0011 + 0100 = 0111
2.      1101 + 0001 = 1110
3.      1101 + 0010 = 1111
4.      0010 + 0010 = 0100
5.      1000 + 1000 = 0000; Cout = 1

For subtraction,
1.      1011 – 1100 = 1111
2.      1010 – 0101 = 0101
3.      1111 – 1101 = 0010
4.      0011 – 0011 = 0000
5.      1000 – 0100 = 0100

Reference:
Wikipedia (2013), Adder-subtractor, Accessed: February 12, 2013, Retrieved from: http://en.wikipedia.org/wiki/Adder%E2%80%93subtractor

4 bit Adder Circuit


Basic Theory:
It is possible to make a logical circuit using numerous full adders to add n-bit numbers. In case of a four bit adder, the number of bits is four; hence it is a 4-bit adder. The main principle behind it is that, “each full adder inputs a Cin, which is the Cout of the previous adder”. This kind of adder is called a ripple-carry adder or a parallel adder, since each carry bit "ripples" to the next full adder in parallel. We must note that the first (and only the first) full adder may be replaced by a half adder. The layout of a ripple-carry adder is simple, which allows for fast design time; however, the ripple-carry adder is relatively slow, since each full adder must wait for the carry bit to be calculated from the previous full adder.

Boolean Expressions (for Full Adder):
Sn = ABC
Cn = BC + (BC) A

Circuit Diagram:













Observed Values:
Following set of values were obtained in observation.
1.      0011 + 0100 = 0111
2.      1101 + 0001 = 1110
3.      1101 + 0010 = 1111
4.      0010 + 0010 = 0100
5.      1000 + 1000 = 0000; Cout = 1

Reference:
Wikipedia (2013), Adder (electronics), Ripple-carry Adder, Accessed: February 8, 2013, Retrieved from: http://en.wikipedia.org/wiki/Adder_%28electronics%29#Ripple-carry_adder

Sunday 17 March 2013

C Program for Lagrange's Interpolation



#include<stdio.h>
#include<conio.h>
#define MAX 10
void main(){
clrscr();
float x[MAX+1], fx[MAX+1], num, den, val, y=0;
int i, j, n;
printf("\t\tLAGRANGE'S INTERPOLATION");
printf("\n\nEnter the degree of interpolation(n): ");
scanf("%d", &n);
for(i=0; i<=n; i++){
printf("\n x%d: ",i);
scanf("%f", &x[i]);
printf("\n fx%d: ",i);
scanf("%f", &fx[i]);
}
printf("\nEnter x to estimate fx: ");
scanf("%f", &val);

for (i=0; i<=n; i++){
num=1;
den=1;
for (j=0; j<=n; j++)
if(j!=i){
num *= val-x[j];
den *= x[i]-x[j];
}
y+=(num/den)*fx[i];
}

printf("\nApproximate value at %.3f: %.3f",val,y);
getch();
}

Sample Output:

LAGRANGE’S INTERPOLATION
Enter the degree of interpolation(n): 2
x0: 1
fx0: 1
x1: 2
fx1: 1.4142
x2: 3
fx2: 1.7321

Enter x to estimate fx: 2.5
Approximate value at 2.500: 1.585



©Dixit Bhatta 2013

C Program for Horner's Method


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

float p[6], ply[6], q[6];

float synth(int m, float r){
                int i;
                q[0] = p[0];
                for(i=1;i<=m;i++){
                                q[i] = (q[i-1]*r)+p[i];
                }
                return(q[m]);
}

void main(){
                clrscr();
                int m,i,flag=0;
                float r, x,x1, b0, c1;
                printf("\t\tHORNER'S METHOD");
                printf("\n Enter the highest degree of the equation (max 5): ");
                scanf("%d",&m);
                                for(i=0;i<=m;i++){
                                printf("\n Coefficient x[%d] = ",m-i);
                                scanf("%f",&p[i]);
                                ply[i] = p[i];
                                }
                printf("\n Enter the initial value x0 : ");
                scanf("%f",&r);
                x = r;
                do{
                   printf("\n%f\n",x);
                   b0 = synth(m,x);

                                for(i=0;i<=5;i++){
                                                p[i]=q[i];
                                }

                   c1 = synth(m-1,x);
                   printf("\n");
                   printf("\tb0 = %f\tc1= %f",b0,c1);
                   x1 = x - (b0/c1);
                   if(fabs(x1-x) <= 0.0009){
                                flag = 1;
                   }
                   x = x1;

                                for(i=0;i<=5;i++){
                                                p[i]=ply[i];
                                }

                   getch();
                }while(flag!=1);

                printf("\nApproximate root = %f", x1);
getch();

}

Sample Output:

                          HORNER’S METHOD
Enter the highest degree of the equation (max 5): 3
Coefficient X[3] : 1
Coefficient X[2] : 9
Coefficient X[1] : 0
Coefficient X[0] : -18
Enter the initial value X0 : 1.5
1.500000
              b0 = 5.625000   c1= 33.750000
1.333333
              b0 = 0.370371   c1= 29.333332
1.328787
              b0 =  0.002071   c1= 29.005529
Approximate root = 1.320636


©Dixit Bhatta 2013

C Program for Birge-Vieta Method

Basic Theory:
The Birge-Vieta method investigates the real root of a polynomial, say xr, by assuming that (x-xr) is a factor of that polynomial. Starting with an initial value or approximation x0 to xr, we use some iterative method to improve the value of the approximation such that R(xr)®0. It makes the use of the Newton-Raphson method for iteration in order to improve the value of xr.
xn+1=xn – [f(xn)/f ’(xn)]

We deploy the Synthetic Division method in order to find out R(xr) in this method. The remainder of first division gives the functional value while the remainder second division gives the value of derivative. We continue the iteration until the result of desired precision is obtained.

Example:  Solve the equation x3+x2-3x-3 using Birge-Vieta Method where x0 = 2.
Using the synthetic division,
2|1         1              -3            -3
  |           2              6              6
  |1         3              3              3¬f(x0)
  |           2              10
  |1         5              13¬f ’(x0)

Now, x1 = 2 – 3/13 = 1.7692
1.7692|1              1              -3            -3
           |                 1.7692   4.8992   3.3602
           |1              2.7692   1.8992   0.3602¬f(x1)
           |                 1.7692   8.0292
           |1              4.5384   9.9285¬f ’(x1)
Now, x2 = 1.7692 – 0.3602/9.9285 = 1.7329
1.7329|1              1              -3            -3
           |                 1.7329   4.7358   3.0079
           |1              2.7329   1.7358   0.0079¬f(x2)
           |                 1.7329   7.7387
           |1              4.4658   9.4745¬f ’(x2)
Now, x3 = 1.7329 – 0.0079/9.4745 = 1.7320
Therefore, Approximate Root = 1.732 correct to 3 decimal places.

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

float p[6], ply[6],q[6];

float synth(int m, float r){
                int i;
                q[0] = p[0];
                for(i=1;i<=m;i++){
                                q[i] = (q[i-1]*r)+p[i];
                }

                printf("\n");
                for(i=0;i<m;i++){
                                printf("\t%f",q[i]);
                }
                printf("\t%f",q[m]);
                return(q[m]);
}

void main(){
                clrscr();
                int m,i,flag=0;
                float r, x,x1, fx, fdx;
                printf("\t\tBIRGE-VIETA METHOD");
                printf("\n Enter the highest degree of the equation (max 5): ");
                scanf("%d",&m);
                                for(i=0;i<=m;i++){
                                printf("\n Coefficient x[%d] = ",m-i);
                                scanf("%f",&p[i]);
                                ply[i] = p[i];
                                }
                printf("\n Enter the initial value x0 : ");
                scanf("%f",&r);
                x = r;

                do{
                   printf("\n%f\n",x);
                   fx = synth(m,x);
                                for(i=0;i<=m;i++){
                                                p[i]=q[i];
                                }
                   fdx = synth(m-1,x);
                   x1 = x - (fx/fdx);

                                if(fabs(x1-x) <= 0.0009){
                                                flag = 1;
                                 }
                   x = x1;

                                for(i=0;i<=5;i++){
                                                p[i]=ply[i];
                                }

                }while(flag!=1);

                printf("\nApproximate root = %f", x1);
getch();

}


Sample Output:

                        BIRGE-VIETA METHOD
Enter the highest degree of the equation (max 5): 3
Coefficient x[3] = 1
Coefficient x[2] = 1
Coefficient x[1] = -3
Coefficient x[0] = -3
Enter the initial value x0 : 2
2.000000
              1.000000   3.000000   3.000000   3.000000
              1.000000   5.000000   13.000000
1.769231
              1.000000   2.769231   1.899408   0.360492
              1.000000   4.538462   9.928994
1.732924
              1.000000   2.732924   1.735948   0.008266
              1.000000   4.465847   9.474921
Approximate root = 1.732051



©Dixit Bhatta 2013

C Program for Synthetic Division with algorithm and example

Algorithm of Synthetic Division:
Given a polynomial of form p(x) = anxn + an-1xn-1+…+ a1x+ a0, we can divide it by a linear factor x-r, where ‘r’ is a constant, using following steps.
a.       Write the r on the left side of a vertical bar and the coefficients in decreasing degree.
r| an               an-1         …….        a1            a0
b.      Pass the coefficient of the highest degree below the horizontal line as it is
 r| an              an-1         …….        a1            a0
  |.                                                                   .
  | an             

c.       Multiply the passed coefficient with ‘r’ and add to the next  coefficient
 r| an              an-1         …….        a1            a0
  |.                 an                                                  .
  | an          an-1+ an
d.      Continue the step ‘c’ until all coefficients are covered.

e.      The numbers below an ……. a1 give the coefficients of the quotient whose degree is 1 less than the polynomial, the number below a0 is the remainder.

Example of Synthetic Division:  x2 + 5x+ 6 by x – 1
Writing the coefficients of the polynomial and dividing by the linear factor.
1|1         5              6
  |           1              6
  |1         6              12


Therefore, the quotient Q(x) = x + 6 and remainder R(x) = 12.
Program:
#include<stdio.h>
#include<conio.h>

void main(){
                clrscr();
                int poly[6], m, r, i, q[6];
                printf("\t\tSYNTHETIC DIVISION");
                printf("\n Enter the highest degree of the equation (max 5): ");
                scanf("%d",&m);

                for(i=0;i<=m;i++){
                                printf("\n Coefficient x[%d] = ", m-i);
                                scanf("%d",&poly[i]);
                }

                printf("\n Enter the value of constant in (x-r) : ");
                scanf("%d",&r);
                q[0] = poly[0];
                for(i=1;i<=m;i++){
                                q[i] = (q[i-1]*r)+poly[i];
                }

                printf("\n Coefficients of quotient are: \n");
                for(i=0;i<m;i++){
                                printf("\t%d",q[i]);
                }
                printf("\n Remainder is: %d", q[m]);
getch();

}

Sample Output:

SYNTHETIC DIVISION
Enter the highest degree of the equation (max 5): 2

Coefficient x[0] = 1

Coefficient x[1] = 5

Coefficient x[2] = 6

Enter the value of constant in (x—r) : 1

Coefficients of quotient are:
1        6
Remainder is: 12

©Dixit Bhatta 2013

C Program for Secant Method


#include<stdio.h>
#include<conio.h>
#include<math.h>
#define E 0.0001
#define F(x) x*x - 4*x - 10
void main(){
  float x1,x2,x3,f1,f2,t;
  clrscr();
  printf("\nEnter the value of x1: ");
  scanf("%f",&x1);
  printf("\nEnter the value of x2: ");
  scanf("%f",&x2);
  printf("\n______________________________________________\n");
  printf("\n    x1\t  x2\t  x3\t     f(x1)\t f(x2)");
  printf("\n______________________________________________\n");
  do{
                f1=F(x1);
                f2=F(x2);
                x3=x2-((f2*(x2-x1))/(f2-f1));
                printf("\n%f   %f   %f   %f   %f",x1,x2,x3,f1,f2);
                x1=x2;
                x2=x3;
                                if(f2<0)
                                                t=fabs(f2);
                                else
                                                t=f2;
  }while(t > E);

printf("\n______________________________________________\n");
printf("\n\nApp.root = %f",x3);
getch();
}

Sample Output:

Enter the value of x1: 4
Enter the value of x2: 2
-----------------------------------------------
x0            x1        x2           f(x0)           f(x1)
-----------------------------------------------
4.000   2.000   9.0000   -10.000    -14.000
2.000   9.000   4.0000   -14.000    35.000
9.000   4.000   5.1111   35.000     -10.000
4.000   5.111   5.9565   -10.000    -4.321
5.111   5.957   5.7225   -4.321      1.654
5.957   5.722   5.7411   1.654       -0.143
5.722   5.741   5.7417   -0.143     -0.004
5.741   5.742   5.7417   -0.004      0.000
-----------------------------------------------

App.root = 5.741657

©Dixit Bhatta 2013

C Program for Newton-Raphson Method

Basic Theory:
The Newton-Raphson method is a powerful technique for solving equations numerically. It is based on the simple idea of linear approximation. The Newton Method, when properly used, usually comes out with a root with great efficiency. It converges, if it does, faster than other techniques. The single initial value used in this approximation is called x0. The Newton Method is usually very good if x0 is close to r, and can be horrid if it is not.

It uses the following formula for estimating next values and iterates the process until required precision is achieved.
xn+1 = xn - f(xn) / f '(xn)
It can be further explained by the following example:
We have following values,
f(x) = x^2 - 4
f '(x) = 2x
x0 = 6

We will assume that the process has worked accurately enough when our delta-x becomes less than 0.1. This value of precision is specific to each situation. A much more, or a much less, precise value may be assumed when using the Newton-Raphson method in other contexts. The table below shows the execution of the process.

n
xn
f(xn)
f '(xn)
xn+1
dx
0
x0 = 6
f(x0) = 32
f '(x0) = 12
x1 = 3.33

1
x1 = 3.33
f(x1) = 7.09
f '(x1) = 6.66
x2 = 2.27
dx = 1.06
2
x2 = 2.27
f(x2) = 1.15
f '(x2) = 4.54
x3 = 2.01
dx = .26
3
x3 = 2.01
f(x3) = 0.04
f '(x3) = 4.02
x4 = 2.00
dx = 0.01


Thus, using an initial x-value of six (6) we find one root of the equation f(x) = x2-4 is x=2. If we were to pick a different inital x-value, we may find the same root, or we may find the other one, x=-2.

Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define f(x) x*x-4*x-10
#define fd(x) 2*x-4
#define E 0.0005
void main(){

clrscr();

float x0, x1, f0, fd0, e;

printf("\t\t\t-----NEWTON-RAPHSON METHOD-----");
printf("\n\n FINDING ROOT OF X^2-4X-10");

printf("\n Enter the initial value: ");
scanf("%f", &x0);

printf("\n f(x0)\t\tfd(x0)\t\tx1\t\tError");
printf("\n -----------------------------------------------------");

begin:
f0 = f(x0);
fd0 = fd(x0);
x1 = x0 - (f0/fd0);
e =fabs((x1-x0)/x1);

                if( e < E){
                                printf("\n\n Approximate Root = %.5f", x1);
                }
                else{
                                printf("\n %.2f\t\t%.3f\t\t%.3f\t\t%.4f",f(x0),fd(x0),x1,e);
                                x0 = x1;
                                goto begin;
                }

getch();

}

Sample Output:

    -----NEWTON-RAPHSON METHOD-----
FINDING ROOT OF X^2-4X-10
Enter the initial value: 0

f(x0)         fd(x0)      x1     Error
---------------------------------
-10.00  -4.000   -2.500  1.0000
6.25     -9.000   -1.806   0.3846
0.48     -7.611   -1.742   0.0364
0.00     -7.484   -1.742   0.0003


Approximate Root = -1.74166