MUL and DIV

[Bertv100]

I'd like to know how to implement the MUL and DIV operators using only AND, OR, XOR, NOT, SHL, SHR, ADD and SUB and without much time consuming looping constructs, of course.

I need this because I'm working on a program that will demonstrate how integers of arbitrary length (64, 128 or even 4096 bit) can be implemented. I already have the above operators, now I still need MUL and DIV (integer division, that is). Eventually I'll also need MOD (integer modulo), but I can implement that when I have DIV.

I'm using the higher level language Turbo Pascal, my integers are stored in an array (vector) and I use Intel byte order. Regards,
Bert Vingerhoets
vingerhoetsbert@hotmail.com

http://www.geocities.com/thevhbcompany/

Don't worry what people think about you. They're too busy wondering what you think about them.

 

[AmkG]

Sorry but there is no other way than to use time consuming looping constructs. At the very least MUL requires you to loop through each bit position, check if it's one, and shift the other bit if it is so, add to the accumulator, rinse, repeat. Just imitate the way we did multiplication in elementary before they allowed us to use calculators.

Division is the opposite of multiplication so when you have a MUL, you can do a DIV. There is really no need to implement a separate DIV, as long as you know how to convert a div to a mul. Remember algebra: division is the same as multiplication by the reciprocal!

x / y = x*r / y*r
if r = 2 ^ n:
x / y = x * (r / y) / 2 ^ n
x / y = x * (r / y) SHR n

of course you need to calculate r / y, he he he...
"Information has a tendency to be free. Which means someone will always tell you something you don't want to know."

 

[Bertv100]

And what happens on processor level? Does it also use loops? Regards,
Bert Vingerhoets
vingerhoetsbert@hotmail.com

http://www.geocities.com/thevhbcompany/

Don't worry what people think about you. They're too busy wondering what you think about them.

 

[AmkG]

It used to be, yes. Now with RISC (I think) it's a long series of hard-wired addition units which is simply the unrolled version of the loop. It's equivalent to a loop the way

PRINT 1
PRINT 2
PRINT 3
PRINT 4
PRINT 5

is equivalent to:

FOR X=1 to 5
PRINT X
NEXT X

So, instead of:
SUB MUL(fact1, fact2)
MASK=1
ACC=0
FOR n=1 to nbits
MASK=MASK SHL 1
IF MASK AND fact2 = 1 THEN ACC=ACC+fact1
fact1=fact1 SHL 1
NEXT n
Return ACC
END SUB
(which older CISC processors implemented in microcode)

the modern RISC processor does something like this:
IF 1 AND fact2 THEN ACC=ACC+fact1
fact1=fact1 SHL 1
IF 2 AND fact2 THEN ACC=ACC+fact1
fact1=fact1 SHL 1
IF 4 AND fact2 THEN ACC=ACC+fact1
fact1=fact1 SHL 1
.
.
.

'course that's all done in hardware. That is one reason why processors are limited by the number of bits it's designed to use, which is why we have 32-bit processors, 16-bit processors, etc. "Information has a tendency to be free. Which means someone will always tell you something you don't want to know."