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]

say you want to multiply A and B

here is some pseudo code:

R := 0 // resultfor (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

How does that work, and how did you (or the person that made it) come up with it?

Heres my little routine.

Count = 1nc = nbfor each bit in an intbit = numb & count count = count + countnc = nc + ncif bit then Result = result + ncNext 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

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

Does anybody have anything more to add?

From,
Nice coder

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

.............

Zipster?

From,
Nice coder