Re: re-discovering the QL... mandelbrot 1989-2023
Posted: Sat Apr 01, 2023 4:10 pm
I havent touched my "QL" since last I wrote and have only landed on this site by accident once or twice in the past 3 or 4 months, so it was nice to see when I did take a peek that theres actually been some recent neural activity! For example a guy who hasnt touched his QL since the eighties, but has realised that screen sizes are not limited to 512x256 in four colours and whose product just worked on my system right out of the box..
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.
It seems slightly faster on QPC2 than a previous version I wrote using a more "standard" algorithm. Notice theres not a mulu in sight!
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