• Advertisement
Sign in to follow this  

Binary method for calculating hardware/Software mults/divs.

This topic is 4729 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If you were to have a 64 bit number, and you need to do mults or divs with it, what do you do? (without hardware support?) My idea (mult only, does anyone have any idea where i could find div stuff? and how it works?) (lets go with 4 bit numebers for now, its simpler. You have your numbers, Alpha and beta. Now, you can represent alpha and beta, as a*2^0 + b*2^1 + c*2^2 + d*2^3 for each number. Also, because a (and b) can only be 0 or 1 (it is representing one bit, same with b), ab = a and b. now, you multiply each number, and collect terms) (a*2^0 + b*2^1 + c*2^2 + d*2^3)(e*2^0 + f*2^1 + g*2^2 + h*2^3) = ae * 2^0 + af * 2^1 + ag * 2^2 + ah * 2^3 + be * 2^1 + af * 2^2 + bg * 2^3 + bh * 2^4 + ce * 2^2 + cf * 2^3 + cg * 2^4 + ch * 2^5 + de * 2^3 + df * 2^4 + dg * 2^5 + dh * 2^6 (ok, figured it out myself) = ae * 2^0 + afbe * 2^1 + agafce * 2^2 + ahbgcfde * 2^3 + bhcgdf * 2^4 + chdg * 2^5 + dh * 2^6 Nice eh? For once byte multiplication, with an 8 bit result, with overflow. (a*2^0 + b*2^1 + c*2^2 + d*2^3+e*2^4+f*2^5+g*2^6+h*2^7)(i*2^0 + j*2^1 + k*2^2 + l*2^3 + m*2^4 + n*2^5 + o*2^6 + p*2^7)
Result =
ai*2^0 + aj*2^1 + ak*2^2 + al*2^3 + am*2^4 + an*2^5+ ao*2^5 + ap*2^7 +
bi*2^1 + bj*2^2 + bk*2^3 + bl*2^4 + bm*2^4 + bn*2^6+ bo*2^7 +
ci*2^2 + cj*2^3 + ck*2^4 + cl*2^5 + cm*2^6 + cn*2^7 +
di*2^3 + dj*2^4 + dk*2^5 + dl*2^6 + dm*2^7 +
ei*2^4 + ej*2^5 + ek*2^6 + el*2^7 +
fi*2^5 + fj*2^6 + fk*2^7 +
gi*2^6 + gj*2^7
Now how would i find the overflow? happy term collecting! (i'll probably do it in a little while, its 9:30 here and i've got the flu, so im going off to bed soon). Now each multiplication by the two power, and the multiplication between two bits, are just an and and a bitshift. is there any easier ways for it? What do you think of this method? Could you do something similar for division? Ive been thinking about making some hardware mult/div circuits for awhile now, and i'm looking for methods to do it with (tho software methods are nice to know too, incase i can apply the principal in hardware) From, Nice coder [Edited by - Nice Coder on March 4, 2005 4:53:11 PM]

Share this post


Link to post
Share on other sites
Advertisement
say you want to multiply A and B

here is some pseudo code:


R := 0 // result

for (i = 0; i < number of bits of an int; i++)
{
if (highest bit set of A is set)
R := R+B
R := R+R // shift bits of R up, R = R <<1 in C / C++
A:= A+A // shift bits of A one upwards, A = A << 1 in C
} // end for
// result of multiplication is in R

Share this post


Link to post
Share on other sites
How does that work, and how did you (or the person that made it) come up with it?

Heres my little routine.


Count = 1
nc = nb

for each bit in an int
bit = numb & count
count = count + count
nc = nc + nc
if bit then Result = result + nc
Next bit


They are both as fast... and can easily be parellised. (and i can get rid of that if statement, with a subtraction, an and and a bitshift, but then again so can you.).

From,
Nice coder

Share this post


Link to post
Share on other sites
That is simple long multiplication. In base ten 123 * 456 would be done like this:

123 *
456
---
738 + this is 6 * 123
615 + this is 5 * 123 * 10
492 this is 4 * 123 * 100
-----
56088

In binary, this becomes:

1111011 *
111001000
---------
0000000 +
0000000 +
0000000 +
1111011 +
0000000 +
0000000 +
1111011 +
1111011 +
1111011
----------------
1101101100011000

which can be implemented as bit tests, shifts and additions. (Note this is elementary mathematics).

The same can be done for division, although a bit more complex. In base ten, 672 / 12 is calculated thus:

056
-----
12 | 672
6 ; 12 doesn't go into 6 = first 0
-0 ; find remainder
67 ; times 10 and add next digit, 12 goes into 67 5 times = 5
-60 ; find remainder
72 ; times 10 and add next digit, 12 goes into 72 6 times = 6

which, in binary becomes:

0000111000
-----------
1100 |1010100000
1 ; 1100 doesn't go into 1 = first 0
10 ; 1100 doesn't go into 10 = second 0
101 ; 1100 doesn't go into 101 = third 0
1010 ; 1100 doesn't go into 1010 = 4th 0
10101 ; 1100 does go into 10101 once, first 1
-1100 ; find remainder
10010 ; add next digit, 1100 does go into 10010, second 1
-1100 ; find remainder
1100
-1100
0000

so the code becomes shifting, comparing, subtraction and bit setting. The intermediate values can only ever be divided by the divisor 0 or 1 times. This can be impemented in hardware but is not a trivial design, it requires a synchronous clocked system with an FSM, shifting and arithmetic functions.

This is how my LongInt class (which has been linked to elsewhere) implements multiplication and division although it uses base 256.

Skizz

Share this post


Link to post
Share on other sites
A division circuit wouldn't be any worse than a multiplication circuit. Same basic components (shift registers, ALU) but different control ROMs. I have to catch a plane soon, but maybe later tonight I'll give an example of how this would be done in hardware. Let's say modified Booth's algorithm for multiplication and a straight-forward long-hand division strategy for, well, division.

Share this post


Link to post
Share on other sites
Thanks to both of you (zipster, i'm looking forward to it.)!

(google doesn't seem to help with this :( additions and subtractions are fine...)


Istn't there a faster way for binary division (i never got the hang of long division tho...), maybe a shortcut?

Also

ae * 2^0 + af * 2^1 + ag * 2^2 + ah * 2^3 +
be * 2^1 + af * 2^2 + bg * 2^3 + bh * 2^4 +
ce * 2^2 + cf * 2^3 + cg * 2^4 + ch * 2^5 +
de * 2^3 + df * 2^4 + dg * 2^5 + dh * 2^6

=
ae * 2^0 + (af + be * 2^1) + (ag + af + ce * 2^2) +
(ah + bg + cf + de * 2^3) + (bh + cg + df * 2^4) +
(ch + dg * 2^5) + (dh * 2^6)

Is that right (i really need to work on my math skills.)

xz + yz = (x+y)z right?

This seriously screws up my algorithm.


oww well.

My mult routine (in software)

(cish psudocode)

numc = numb;
while (numb) {
bit = numb&1;
numb >>= 1;
if (bit) {result = result + numc;)
}


:)

From,
Nice coder

Share this post


Link to post
Share on other sites
Yes, I was going to post something about the hardware implementation but I realized that without all the appropriate background information and diagrams it would take an extremely long time to explain everything. At the same time I don't just want to say "well here's what the control and dispatch units would look like!" and leave you hanging. I have a few lecture slides from the course I took on digital logic and design however the professor is really uptight about who has access to the slides on his website, so I'm not sure if I can post them here. If you still want me to go ahead and post something I can, but I don't know how much background I'll be able to give you on how exactly each component works (shift register, ALU, control/dispatch units) except for how they work together in a multiplication/division circuit. So basically, I can give all the what's and the how's, but maybe not so much the why's.

Share this post


Link to post
Share on other sites
Thats ok.

I like the hows, and i could probably figure out most of it myself. (if i had too...)

Try to get a nice explanation. I don't need very many pictures, but a schematic and how it works would be much appriciated. The why it was made would be nice.

Basically: Please post, and i'll try to understand it as much as possible (if not, i'm sure that a few pm's could sort things out [lol]). I'm usually good at understanding things. (yay for being G&T!!)

Maybe start with a very simple (like 4 bit, really really slow&simple) mult/div unit, before going on to the harder ones?

From,
Nice coder

Share this post


Link to post
Share on other sites
Mr zipster, i think that you said that you would post it.....

Anybody else?

....


Anybody?

From,
Nice coder

Share this post


Link to post
Share on other sites
Dmitry [lol]. Thats a little... off-center.

Is anything better then the multi-add-with-shift design for multiplication? (currently, this would be huge, in the 100clock range.)

From,
Nice coder

Share this post


Link to post
Share on other sites
Ok, my best is using the binary method.

basically if i can get the last bit nicely, then i'm set.

B0 = a & e
B1 = (a & f) | (b & e)

Ect.

But how would i quickly work out the parity of a group of bits? (ie. if the number of bits is odd or even?)

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Dmitry [lol]. Thats a little... off-center.

Is anything better then the multi-add-with-shift design for multiplication? (currently, this would be huge, in the 100clock range.)

From,
Nice coder

don't think there's better ways of doing multiplication. You can have small multiplication table for 4bit multiplications, and use them instead. Basically same thing as multiplying decimal numbers manually.

As about division, from that thread,


//subtraction is needed for division. Of course i can do cool subtraction via cool addition,but it's...inelegant
int coolsub(int a,int b){
int c,result, tmp;
c=((~a)&b)<<1;
result=a^b;
while(c!=0){
tmp=result^c;
c=((~result)&c)<<1;
result=tmp;
};
return result;
};

const high_bit=( ~((unsigned int)(0)) ^ (~((unsigned int)(0))>>1) );

int cooldivide(int a,int b){
if(b==0)return 0;//division by zero. What i should return....
if(b==1)return a;
int s=0;
//note that general >,<,<=,>= do subtraction :)
if(a&high_bit){a=coolsub(0,a);s=1;}
if(b&high_bit){b=coolsub(0,b);s^=1;}
int c,d,m=1,r=0;
c=b;
d=c<<1;
while(d>c){
c=d;
d<<=1;
m<<=1;
}
int e=a;
int k=0;
do{
k=coolsub(e,c);
if((k&high_bit)==0){e=k;r+=m;};
m>>=1;
c>>=1;
}while((m!=0)&&(e!=0));
if(s){return coolsub(0,r);}else{return r;}
}


[/quote]
you can replace coolsub with "-" if you like.

Share this post


Link to post
Share on other sites
Ok, say i have 4 bits, a,b,c and d.


Truth table
0000 = 0
0001 = 1
0010 = 1
0011 = 0
0100 = 1
0101 = 0
0110 = 0
0111 = 1
1000 = 1
1001 = 0
1010 = 0
1011 = 1
1100 = 0
1101 = 1
1110 = 1
1111 = 0


Maybe someone else can work this out.... Its stumping me.

From,
Nice coder

Share this post


Link to post
Share on other sites
Dmitry - Considering that i'm doing all this on hardware, (for one of the banks).

From,
Nice coder

Share this post


Link to post
Share on other sites
Ok. Parity = a ^ b ^ c ^ d
Picking a line
0111 = 1

0 ^ 1 = 1
1 ^ 1 = 0

Result = 1 ^ 0 = 1

Now, its cumative, sao i can use a tree based approach. Log2 n time (even though most of it is done beforehand.)

From,
Nice coder

Share this post


Link to post
Share on other sites
Now the algorithm reads:

B0 = ae
B1 = af ^ be
B2 = ag ^ af ^ ce
B3 = ah ^ bg ^ cf ^ de
B4 = bh ^ cg ^ df
B5 = ch ^ dg
B6 = dh

Now, this is 4 bit arithmatic
so we go up to B3 which is
B0 = ae
B1 = af ^ be
B2 = ag ^ af ^ ce
B3 = ah ^ bg ^ cf ^ de
Now, we have overflow which is
Overflow = (bh ^ cg ^ df) | (ch ^ dg) | (dh)

Thats 4 bit mult + overflow. Also very fast.

From,
Nice coder

Share this post


Link to post
Share on other sites
Result =
ai*2^0 + aj*2^1 + ak*2^2 + al*2^3 + am*2^4 + an*2^5+ ao*2^5 + ap*2^7 +

bi*2^1 + bj*2^2 + bk*2^3 + bl*2^4 + bm*2^5 + bn*2^6+ bo*2^7 +

ci*2^2 + cj*2^3 + ck*2^4 + cl*2^5 + cm*2^6 + cn*2^7 +

di*2^3 + dj*2^4 + dk*2^5 + dl*2^6 + dm*2^7 +

ei*2^4 + ej*2^5 + ek*2^6 + el*2^7 +

fi*2^5 + fj*2^6 + fk*2^7 +

gi*2^6 + gj*2^7

Problem, how do i handle overflow?

For eg. ap + bo + cn + ddm + el + fk + gj> what if there all one?

From,
Nice coder

Share this post


Link to post
Share on other sites
My problem is that this is a hardware multiplication unit, so i end up with a little bit of a problem.

I end up with a bit of a bit-counting and adding problem... [bawling]

From,
Nice coder

Share this post


Link to post
Share on other sites
i posted Lord Clickster of Clicksters into some of your threads, where you asked about adders. On bottom of that page are << and >> , and next is exactly about multiplication. Interactive diagram.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement