Jump to content
  • Advertisement
Sign in to follow this  
Nice Coder

Binary method for calculating hardware/Software mults/divs.

This topic is 4997 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!