Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Reload this Page Booth's Multiplication Algorithm

Reply
 
Thread Tools

Booth's Multiplication Algorithm
Old 23.11.2003, 14:05   #1
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 47
Posts: 3,760
Rep Power: 0
Default Booth's Multiplication Algorithm
Code:
// Booth's Multiplication Algorithm
// 1. Depending on the current and previous bits, do one of the following: 
// 00: a. Middle of a string of 0s, so no arithmetic operations. 
// 01: b. End of a string of 1s, so add the multiplicand to the left half of the product. 
// 10: c. Beginning of a string of 1s, so subtract the multiplicand from the left half of the product. 
// 11: d. Middle of a string of 1s, so no arithmetic operation.
// 2. Shift the Product register right (arithmetic) 1 bit. 
//
// Example: 2 x 6 
// m=2,p=6; 
// 
// m = 0010 
// p = 0000 0110  
// 
//     p 
// 0000 0110 0 no-op 
// 0000 0011 0 >> p 
// 1110 0011 0 p = p - m 
// 1111 0001 1 >> p 
// 1111 0001 1 no-op 
// 1111 1000 1 >> p 
// 0001 1000 1 p = p + m 
// 0000 1100 0 >> p 
// 
// =12 
//   
// Example: 2 x -3 
// 
// m = 0010 
// p = 0000 1101  
// 
// 1110 1101 0 p = p - m 
// 1111 0110 1 >> p 
// 0001 0110 1 p = p + m 
// 0000 1011 1 >> p 
// 1110 1011 0 p = p - m 
// 1111 0101 1 >>p 
// 1111 0101 1 no-op 
// 1111 1010 1 >>p 
// 
// =-6 
  


#include <stdio.h>
#include <stdlib.h>

void load(int*, int*, int*);
void display(int*, int*, int*);
bool compute(int*, int*, int*, bool);
void addPLM(int*, int*);
void negate(int*);

void main()
{
	int PLreg [4];
	int PRreg [5];	
	int Mreg [4];
	bool neg=0;
	
	load(PLreg, PRreg, Mreg);				//initialising registers with data
		
	printf("	    PL\t      PR\t\tM\n");	//page title

	display(PLreg, PRreg, Mreg);			//general display
	printf("\t-------------------------------------\n");//page title


	//computation first step
	neg = compute(PLreg, PRreg, Mreg, neg);	//compute 1st bit
	display(PLreg, PRreg, Mreg);			//display


	neg = compute(PLreg, PRreg, Mreg, neg);	//compute 2nd bit
	display(PLreg, PRreg, Mreg);			//display

	neg = compute(PLreg, PRreg, Mreg, neg);	//compute 3rd bit
	display(PLreg, PRreg, Mreg);			//display

	neg = compute(PLreg, PRreg, Mreg, neg);	//compute 4th bit
	display(PLreg, PRreg, Mreg);			//display
}


bool compute(int PL[], int PR[], int M[], bool neg)
{
	int MCopy [4];

	if((PR[3] == 0) && (PR[4] == 0))	// BOOTH - 00 - NO-OP
	{
		printf("\t\t\t\t\t\t 00; Outside. shifting...\n");
		PR[4] = PR[3];
		PR[3] = PR[2];
		PR[2] = PR[1];
		PR[1] = PR[0];
		PR[0] = PL[3];
		PL[3] = PL[2];
		PL[2] = PL[1];
		PL[1] = PL[0];
		if(neg)
		{
			PL[0] = 1;
			neg = 1;
		}
		else 
		{
			PL[0] = 0;
			neg = 0;
		}
		return neg;
	}
	else if ((PR[3] == 1) && (PR[4] == 1))	// BOOTH - 11 - NO-OP
	{
		printf("\t\t\t\t\t\t 11; Inside. shifting...\n");
		PR[4] = PR[3];
		PR[3] = PR[2];
		PR[2] = PR[1];
		PR[1] = PR[0];
		PR[0] = PL[3];
		PL[3] = PL[2];
		PL[2] = PL[1];
		PL[1] = PL[0];
		if(neg)
		{
			PL[0] = 1;
			neg = 1;
		}
		else 
		{
			PL[0] = 0;
			neg = 0;
		}
		return neg;
	}


	else if ((PR[3] == 0) && (PR[4] == 1))	// BOOTH - 01 - Add
	{
		printf("\t\t\t\t\t\t 01; End. Add.\n");
	
		addPLM(PL, M);		// Addition

		PR[4] = PR[3];		// then shifting
		PR[3] = PR[2];
		PR[2] = PR[1];
		PR[1] = PR[0];
		PR[0] = PL[3];
		PL[3] = PL[2];
		PL[2] = PL[1];
		PL[1] = PL[0];
	/*	if(neg)
		{
			PL[0] = 1;   //wrong???
			neg = 1;
		}
		else 
		{*/
			PL[0] = 0;            
		/*	neg = 0;
		}*/
		return neg;
	}


	else if ((PR[3] == 1) && (PR[4] == 0))	 // BOOTH - 10 - Substract
	{
		printf("\t\t\t\t\t\t 10; Begining. Sub.\n");

	///////////////////////// 
	// ISUBSTRACT operation HERE. 
	// PL, M, neg
	//
	// first lets negate MCopy (an image of M)
	//
		MCopy[0] = M[0];
		MCopy[1] = M[1];
		MCopy[2] = M[2];
		MCopy[3] = M[3];
		
		negate(MCopy);
		neg = 1;
	
	// now add up
		addPLM(PL, MCopy);		// Addition (actually substraction)

	///////////////////////// 

		PR[4] = PR[3];			// then shifting
		PR[3] = PR[2];
		PR[2] = PR[1];
		PR[1] = PR[0];
		PR[0] = PL[3];
		PL[3] = PL[2];
		PL[2] = PL[1];
		PL[1] = PL[0];
		if(neg)
		{
			PL[0] = 1;
			neg = 1;
		}
		else 
		{
			PL[0] = 0;
			neg = 0;
		}
		return neg;
	}

}


void negate(int A[])
{
	int i;
	int ONE[4];
	ONE[0] = 0;
	ONE[1] = 0;
	ONE[2] = 0;
	ONE[3] = 1;
	

	for (i=0; i<=3; i++)
	{
		if(A[i] == 1) 
			A[i] = 0;
		else 
			A[i] = 1;
	}

	//ADD 1
	addPLM(A, ONE);	
}




// done.
void addPLM(int A[], int B[])
{
	int next, i, carry=0;
	
	for (i=3; i>=0; i--)
	{
		next = 1;
		if (A[i]==0 && B[i]==0)		//00 case
		{
			A[i]= carry;
			carry = 0;
			next = 0;
		} // good.
		
		if (next)
		if (A[i]==0 && B[i]==1)		//01 case	- transfer
		{
			if (carry == 0)
				A[i] =1;
			else
				A[i]=0;
			next = 0;
		}
			
		if(next)
		if (A[i]==1 && B[i]==0)		//10 case	- transfer
		{
			if (carry == 0)
				A[i] =1;
			else
				A[i]=0;
			next = 0;
		}	

		if(next)
		if (A[i]==1 && B[i]==1)		//11 case - generate
		{	
			if (carry == 0)
			{
				A[i] =0;
				carry = 1;
			}
			else
				A[i]=1;
		next = 0;
		}
	}
}



///////////////////////////////////////////////////////
//displaying {OK}
void display(int PL[], int PR[], int M[])
{
	int i;
	printf("\t");
	for(i=0; i<=3; i++) 
		printf(" %d", PL[i]);
	printf("  ");
//////////////////

	for(i=0; i<=3; i++) 
		printf(" %d", PR[i]);
	printf("  %d", PR[4]);
///////////////////

	printf("\t    ");
		for(i=0; i<=3; i++) 
		printf(" %d", M[i]);
///////////////////

	printf("\n");
}


//function to load registers with data.  {OK}
void load(int PL[], int PR[], int M[])
{
	PL[0] = 0;
	PL[1] = 0;
	PL[2] = 0;
	PL[3] = 0;
	
	PR[0] = 0;
	PR[1] = 1;
	PR[2] = 1;
	PR[3] = 0;
	PR[4] = 0;		//DUMMY BIT

	M[0] = 0;
	M[1] = 1;
	M[2] = 1;
	M[3] = 0;

}

Old 23.11.2003, 14:06   #2
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 47
Posts: 3,760
Rep Power: 0
Default
Output:

Code:
            PL        PR                M
         0 0 0 0   0 1 1 0  0        0 1 1 0
        -------------------------------------
                                                              00; Outside. shifting...
         0 0 0 0   0 0 1 1  0        0 1 1 0
                                                              10; Begining. Sub.
         1 1 0 1   0 0 0 1  1        0 1 1 0
                                                              11; Inside. shifting...
         1 1 1 0   1 0 0 0  1        0 1 1 0
                                                              01; End. Add.
         0 0 1 0   0 1 0 0  0        0 1 1 0
Press any key to continue

Old 23.11.2003, 15:39   #3
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
Default
recepty na budushee, DaNYer:

Code:
		if(neg)
		{
			PL[0] = 1;
			neg = 1;
		}
		else 
		{
			PL[0] = 0;
			neg = 0;
		}
zamenyaetsa na:

Code:
PL[0] = neg & 0x01;
neg = neg & 0x01;
konstrukcii s "IF"-m sil'no zamedlyayut programmu.
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Old 23.11.2003, 15:41   #4
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
Default
to je est' v funkcii NEGATE:

Code:
	for (i=0; i<=3; i++)
	{
		if(A[i] == 1) 
			A[i] = 0;
		else 
			A[i] = 1;
	}
zamenyaetsa na:

Code:
	for (i=0; i<=3; i++)
	{
		A[i] = -A[i]; 
	}
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Old 23.11.2003, 15:45   #5
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
Default
i ne nado poshlit'....

Code:
		PR[4] = PR[3];		// then shifting
		PR[3] = PR[2];
		PR[2] = PR[1];
		PR[1] = PR[0];
		PR[0] = PL[3];
		PL[3] = PL[2];
		PL[2] = PL[1];
		PL[1] = PL[0];
oformi eto v vide funkcii, bud' gumannee k chitayushim tvoy kod
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Old 23.11.2003, 18:26   #6
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 47
Posts: 3,760
Rep Power: 0
Default
Quote:
Originally posted by Greco El
to je est' v funkcii NEGATE:

Code:
	for (i=0; i<=3; i++)
	{
		if(A[i] == 1) 
			A[i] = 0;
		else 
			A[i] = 1;
	}
zamenyaetsa na:

Code:
	for (i=0; i<=3; i++)
	{
		A[i] = -A[i]; 
	}

chegooooo!????

eto binary negate, Greco jan, cavt tanem ya..... minusom tut ne pomojesh

Old 23.11.2003, 19:35   #7
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
Default
sorry, ty prav, konechno...

tut nujna operaciya podobnogo roda:

Code:
for (i=0; i<=3; i++)
	{
		A[i] = A[i] ^ 0x01; 
	}
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Old 24.11.2003, 02:17   #8
Бакалавр
 
Join Date: 03 2002
Location: Detroit, MI, USA
Posts: 482
Rep Power: 0
Default
Вдогонку: вектора с константами лучше вывести из тел функций и сделать глобальными. Иначе, выделение места под вектор/инициализация будут происходить при каждом вызове функции, что не есть хорошо для производительности.
__________________
Hovhannes Tumanyan,
CISSP

Old 24.11.2003, 05:28   #9
Младенец
 
Фича's Avatar
 
Join Date: 11 2003
Location: клитляндия
Posts: 39
Rep Power: 0
Default
Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []...
Про эту функцию было уже много сказано и все равно написана не по людски
Вот... а за одно предложу еще один вариант суммирования, который соответствует аппаратной реализации:

Code:
pC[i] = pA[i] ^ pB[i] ^ bCarry;
bCarry = (pA[i]&pB[i]) || (pB[i] & bCarry) || (pA[i] & bCarry);
__________________
pictores veneficiosque futuo

Old 24.11.2003, 05:47   #10
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 47
Posts: 3,760
Rep Power: 0
Default
Quote:
Originally posted by Фича
Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []...

da ladno.... "gospodin"....

ya * pisal v pozaproshlom semestre s tex por ni strochki na c ne napisal. podzabil, sorry. spasibo chto napomnil



Tumanyan: del'no. thanx.
Reply

« Previous Thread | Next Thread »



Реклама:
реклама
Buy text link .

All times are GMT. The time now is 19:57.
Mark Forums Read | View Forum Leaders
Top

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.