AKB Forums

Go Back   AKB Forums > Technical sections > Algorithms
Booth's Multiplication Algorithm Booth's Multiplication Algorithm
Home Register Blogs FAQ Members List Calendar Downloads Arcade Mark Forums Read

Algorithms The source of algorithms for your project

Troubles when posting message? Click here! :: Проблемы с отправлением сообщения? Нажмите сюда!

Reply
 
LinkBack Thread Tools Display Modes
Old Nov 23, 2003, 13:05   #1
Banned
 
DaNYer's Avatar
 
Join Date: Oct 2002
Location: Brooklyn, New York
Posts: 3,760
Rep Power: 0
Reputation: 10
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;

}
DaNYer is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 13:06   #2
Banned
 
DaNYer's Avatar
 
Join Date: Oct 2002
Location: Brooklyn, New York
Posts: 3,760
Rep Power: 0
Reputation: 10
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
DaNYer is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 14:39   #3
Administrator
 
greka's Avatar
 
Join Date: Sep 2001
Location: @work
Posts: 5,347
Rep Power: 10
Reputation: 23
Send a message via ICQ to greka
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.
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
greka is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 14:41   #4
Administrator
 
greka's Avatar
 
Join Date: Sep 2001
Location: @work
Posts: 5,347
Rep Power: 10
Reputation: 23
Send a message via ICQ to greka
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]; 
	}
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
greka is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 14:45   #5
Administrator
 
greka's Avatar
 
Join Date: Sep 2001
Location: @work
Posts: 5,347
Rep Power: 10
Reputation: 23
Send a message via ICQ to greka
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
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
greka is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 17:26   #6
Banned
 
DaNYer's Avatar
 
Join Date: Oct 2002
Location: Brooklyn, New York
Posts: 3,760
Rep Power: 0
Reputation: 10
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
DaNYer is offline   Reply With Quote Quote selected
Old Nov 23, 2003, 18:35   #7
Administrator
 
greka's Avatar
 
Join Date: Sep 2001
Location: @work
Posts: 5,347
Rep Power: 10
Reputation: 23
Send a message via ICQ to greka
sorry, ty prav, konechno...

tut nujna operaciya podobnogo roda:

Code:
for (i=0; i<=3; i++)
	{
		A[i] = A[i] ^ 0x01; 
	}
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
greka is offline   Reply With Quote Quote selected
Old Nov 24, 2003, 01:17   #8
Бакалавр
 
Join Date: Mar 2002
Location: Detroit, MI, USA
Posts: 482
Rep Power: 7
Reputation: 10
Вдогонку: вектора с константами лучше вывести из тел функций и сделать глобальными. Иначе, выделение места под вектор/инициализация будут происходить при каждом вызове функции, что не есть хорошо для производительности.
__________________
Hovhannes Tumanyan,
CISSP
Tumanyan is offline   Reply With Quote Quote selected
Old Nov 24, 2003, 04:28   #9
Младенец
 
Фича's Avatar
 
Join Date: Nov 2003
Location: клитляндия
Posts: 39
Rep Power: 0
Reputation: 10
Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []...
Про эту функцию было уже много сказано и все равно написана не по людски
Вот... а за одно предложу еще один вариант суммирования, который соответствует аппаратной реализации:

Code:
pC[i] = pA[i] ^ pB[i] ^ bCarry;
bCarry = (pA[i]&pB[i]) || (pB[i] & bCarry) || (pA[i] & bCarry);
__________________
pictores veneficiosque futuo
Фича is offline   Reply With Quote Quote selected
Old Nov 24, 2003, 04:47   #10
Banned
 
DaNYer's Avatar
 
Join Date: Oct 2002
Location: Brooklyn, New York
Posts: 3,760
Rep Power: 0
Reputation: 10
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.
DaNYer is offline   Reply With Quote Quote selected
Reply

« Нетривиальная задача | Binary Addition »

Thread Tools
Display Modes
Linear Mode Linear Mode

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT. The time now is 21:22.

Contact Us - AKB Portal - Forum Rules - Archive - Top

Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
This board was founded on September 29, 2001
Powered by Viper Internet

Affordable Web Hosting | ParevNet

Buy text link