|
23.11.2003, 14:05
| #1 |
| Banned  Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |  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;
} |
 |
|
23.11.2003, 14:06
| #2 |
| Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |
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 |
| |
|
23.11.2003, 15:39
| #3 |
| Академик  Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 |
recepty na budushee, DaNYer: Code: if(neg)
{
PL[0] = 1;
neg = 1;
}
else
{
PL[0] = 0;
neg = 0;
} Code: PL[0] = neg & 0x01; neg = neg & 0x01; |
| |
|
23.11.2003, 15:41
| #4 |
| Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 |
to je est' v funkcii NEGATE: Code: for (i=0; i<=3; i++)
{
if(A[i] == 1)
A[i] = 0;
else
A[i] = 1;
} Code: for (i=0; i<=3; i++)
{
A[i] = -A[i];
} |
| |
|
23.11.2003, 15:45
| #5 |
| Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 |
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];  |
| |
|
23.11.2003, 18:26
| #6 | |
| Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | Quote:
chegooooo!???? eto binary negate, Greco jan, cavt tanem ya..... minusom tut ne pomojesh  | |
| |
|
23.11.2003, 19:35
| #7 |
| Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 |
sorry, ty prav, konechno... tut nujna operaciya podobnogo roda: Code: for (i=0; i<=3; i++)
{
A[i] = A[i] ^ 0x01;
} |
| |
|
24.11.2003, 02:17
| #8 |
| Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |
Вдогонку: вектора с константами лучше вывести из тел функций и сделать глобальными. Иначе, выделение места под вектор/инициализация будут происходить при каждом вызове функции, что не есть хорошо для производительности.
|
| |
|
24.11.2003, 05:28
| #9 |
| Младенец  Join Date: 11 2003 Location: клитляндия
Posts: 39
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |
Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []... Про эту функцию было уже много сказано и все равно написана не по людски  Вот... а за одно предложу еще один вариант суммирования, который соответствует аппаратной реализации: Code: pC[i] = pA[i] ^ pB[i] ^ bCarry; bCarry = (pA[i]&pB[i]) || (pB[i] & bCarry) || (pA[i] & bCarry); |
| |
|
24.11.2003, 05:47
| #10 | |
| Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | Quote:
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. | |
| |
| Sponsored Links |
