I may have some catching up to do, as my RSS feed only downloaded the past 2 or 3 weeks' worth of posts. I doubt Ill have the will to go through everything..
Anyway, this thread spurred me on to have a go at the 32bit multiply. Of course, QPC2 can already do that since it emulates a 020 CPU which has it built in. Im sure a lot of others have had a go, so I decided to try an algorithm unlikely to have been tried here before. I really havent spent a lot of time on it, so it may be unreliable and rubbish. I really just wrote it down in the shortest possible time, then I wrote a harness for it (not included here unless anyone asks) and ran a few tests. Then I did a 32x32=>64 bit version, which is only 7 instructions longer, and also seems to work! Amazing! No refinements and only unsigned multiply.
Code: Select all
mulu32ss
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*
* Multiply two 32 bit unsigned integers using the sheep shit method
*
* This method of multiplication is (or at least was) used by sheep and camel
* herders in the desserts of Arabia. The only skill you need to work this is
* to be able to count!
*
* You dig two parallel columns of small holes in the ground. (The number of
* holes required will depend on the size of of your calculation. It is not
* fixed; you can always add more if you need.)
* In the topmost hole of the left column you put a number of beads (or
* stones or sheep or camel droppings, depending on what's available)
* corresponding to the number of, say, sheep you wish to sell; in the
* topmost right hole the number of beads corresponding to the price per head.
* Then, operating on the second row of the right column, for every two beads
* in the hole above, you put one bead in the hole, rounded down to the nearest
* whole number.
* Continue until there is only one bead left.
* In the left column you double the number of beads for each hole down the
* column. Each row on the left corresponds to the row on the right, so stop
* when you get to the row where the right column contains only one bead.
* Now, starting from the topmost row, take all the the beads from the left
* column, where the corresponding right column contains an ODD number of beads,
* and put them in the accumulator.
* The contents of the accumulator now, magically, contains the number of beads
* that correspond to the total amount of rials, shekels or whatever, for the
* sale; ie multiplication.
*
* The code below emulates that algorithm.
*
*
* Entry Return
* d2.l = multiplier d2.l smashed
* d1.l multiplicand d1.l smashed
* d0.l d0.l accumulator (= result)
*
* cc set on overflow
*
clr.l d0 clear accumulator
tst.l d2 0 x N = 0
beq.s done
tst.l d1 N x 0 = 0
beq.s done
cmp.l d1,d2 smallest number is multiplier
bcs.s begin
exg d1,d2
bra.s begin
*
loop
lsl.l #1,d1 double multiplicand
bvs.s done oops. Overflow!
lsr.l #1,d2 halve multiplier
beq.s done no more to do
begin
btst #0,d2 if even..
beq.s loop ..skip, else..
add.l d1,d0 ..accumulate
bvc.s loop continue unless overflow
*
done
rts
*
end
