Home » CEEFAX disks » telesoftware5.adl » 17-02-88/T\OSB13
17-02-88/T\OSB13
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » CEEFAX disks » telesoftware5.adl |
| Filename: | 17-02-88/T\OSB13 |
| Read OK: | ✔ |
| File size: | 2E02 bytes |
| Load address: | 0000 |
| Exec address: | FFFFFFFF |
Duplicates
There is 1 duplicate copy of this file in the archive:
- CEEFAX disks » telesoftware5.adl » 07-02-88/T\OSB13
- CEEFAX disks » telesoftware5.adl » 17-02-88/T\OSB13
File contents
OSBITS - An Exploration of the BBC Micro at Machine Level
By Programmer
...........................................................
Part 13: Multi-Byte Multiplication
While I have no desire to labour the point it is worth
taking a detailed look at multiplication where the numbers
being multiplied are both several bytes long. I have called
this multi-byte arithmetic although it is often known as
multi-precision arithmetic.
The last module included a routine which multiplied a large
number by a small one; a four byte number by a one byte
number. The extension of this to arbitrarily large numbers
is straightforward but I want to deal with it separately so
that any confusion that may still be in your mind from last
time is dispelled.
Let's recap on the method employed in multiplication. It is
exactly like the long multiplication you will have done at
school (and probably not used since) except, of course, that
we will be working in binary. Ironically this makes it
easier although when working on paper we have to be careful
about binary maths because we are unused to it.
Returning to the single byte example from last time we have
the two numbers 11 and 27 which we want to multiply
together. 11 is 1011 in binary because it is made up of
2^3 + 2^1 + 2^0 (8+2+1) and 27 is 11011 because it is made
up of 2^4 + 2^3 + 2^1 + 2^0 (16+8+2+1). It is irrelevant
that the numbers are related in a way that is obvious in
binary.
11011
x
1011
---------
11011
11011o
11011ooo
---------
100101001
This is how we carried out the multiplication in the last
module. When we start multiplying large numbers together
though we run into a problem. If you multiply a number with
x bits by a number with y bits the product has x+y bits (I'm
assuming the numbers are both positive). If you want to
make sure that your result does not overflow you have to
allow for a result of that size. This in fact means that
when you do your multiplication you have to have a partial
product workspace that is x+y bits long. Obviously the more
bits in your partial product workspace the slower the
routine becomes because you are carrying out additions on
more bytes than you want the result to have.
It's worth looking at a different algorithm since there are
several ways of implementing multiplication. First I'll
rewrite the sum above to separate out the two additions.
11011
x
1011
---------
11011
11011o
---------
1010001
11011ooo
---------
100101001
What we are doing here is shifting the multiplicand left and
then conditionally adding it onto the partial product. As
an alternative how about shifting the partial product right
instead? This would look like this:
11011
x
1011
---------
00000 ppws is empty to start with
11011 lsb of 1011 is 1 so add 11011 to ppws
11011 new ppws
1101 1 shift ppws right one bit
11011 bit 1 of 1011 is 1 so add 11011 to ppws
101000 1
10100 01 shift ppws right one bit
00000 bit 2 of 1011 is 0 so don't add
10100 01 new ppws
1010 001 shift ppws right one bit
11011 bit 3 of 1011 is 1 so add 11011 to ppws
100101 001 new ppws
10010 1001 shift ppws right one bit
If we count leading zeros in our multiplier and so carry out
eight operations (the next byte size up) we carry out
another four shifts and get the result
1 00101001
On each occasion we are shifting the multiplier right to
start with and then immediately afterwards we shift the ppws
right. Now this could be a useful feature because if we can
combine the two shifts, multiplier and ppws, into a single
shift operation we will end up with the result in the space
where the multiplier was.
I haven't worried too much about speed before. With the
number translation program last time the speed of the user
was the limiting factor anyway, so speed considerations were
irrelevant. With a multiplication speed is a very important
consideration so let's look at the algorithm we have come up
with now.
Clear ppws (partial product work space)
Shift multiplier right, puts lsb into carry flag
If carry set add multiplicand to ppws
Shift ppws and multiplier right
Repeat last two lines until all bits processed
When you have finished the lower bytes of the result have
replaced the multiplicand and the 'overflow' remains in the
ppws. Now that looks short and to the point, the only
asymmetrical part being the initial shift, but we've got to
start somewhere.
So let's turn it into a program.
When rotating a multi-byte number you start at the far end,
(i.e. if rotating left start at the right and vice versa)
and use ASL or LSR as the first rotation so that you do not
shift the carry value in, because you do not want it! The
other rotates will be ROL or ROR because then you use the
carry to carry the relevant bit over from one byte to the
next. In this case we will treat the ppws and multiplier as
a single long block of memory with the ppws to the left of
the multiplier.
There is no limit to the size of numbers you can multiply
together with this method. Remember that a four byte number
multiplied by another four byte number can result in an
eight byte result, so you have to allow for this
possibility. If we were dealing solely with positive
numbers then, by treating the ppws and multiplier as a
single piece of work space, we would automatically have
enough room for a large result. We could test for an
overflow by looking to see if anything was in the top 4
bytes.
A negative number with 4 bytes is defined as one with the
top most bit (bit 31) set. Clearly if we are working to a
64 bit result then that number should be held in memory in
8 bytes with the top bit (number 63) set. All the bits
between 31 and 63 would also be set. To make this routine
operate totally correctly for negative numbers we would have
to expand the multiplier and multiplicand into 64 bit
numbers and have a routine that ran through 64 times instead
of 32. For simplicity I have not done so. The result is
that it is possible to generate a result (positive or
negative) that is too big but it is very difficult to trap.
The simplest solution would be to check to see what sign the
result should be and then convert both numbers to positive,
carry out the multiplication, and convert back afterwards if
needed. Then you could just check to see if anything was
left in ppws after the multiplication. Anything there would
indicate an overflow and hence an error. Although we didn't
error trap the addition and subtraction in module 2 it could
have easily been done by branching to the error code
whenever the overflow flag was set after adding or
subtracting the highest byte.
The input routine in the last module can be modified to
always give a positive result and an indication of sign.
I am not going to use that input module here because all the
superfluous code is likely to cloud the main issue, which is
the multiplication. I leave it to you to bolt the routines
together. So I use dear old BASIC indirection operators to
put the numbers to be multiplied into the workspace and to
read the result out afterwards.
The multiplicand goes into 'multiplicand' and the multiplier
goes into 'multiplier'. 'ppws' is the partial product
workspace. This arrangement fits nicely with the
requirement for ppws and multiplier to be together. [In
fact the memory used for multi-byte maths does not need to
be contiguous, in a block, but it is sensible to have it
so.]
A further note on speed. The 6502 works faster when it is
using zero page workspace, so we should really use some of
this for our routines. I am not going to in this example
because it keeps a consistency with earlier modules and I
leave it to you to make the adjustment if you want to. It
doesn't affect the algorithm at all.
Firstly the workspace is cleared and then a counter is
initialised to the number of bits in the numbers. Since
this routine will cope with negative numbers as easily as
positive ones (2's complement negative that is) we will need
all 32 bits. -1 is &FFFFFFFF (I will refrain from printing
out 32 '1's just to illustrate this point.)
The first thing that happens in the code is that we clear
our partial product workspace and set the bit counter to 32
(or however many bits you are working with). To get our
algorithm ready we have to first rotate or shift the
multiplier right to put its least significant bit (lsb) into
the carry flag. We can then use branches on carry to decide
whether or not to add the multiplicand onto the contents of
the partial product workspace.
'mbm_loop' (for multi-byte multiplication) is the top of the
main loop. In it we first check the carry flag to see if
the lsb of the multiplier was set. If it was then we will
add the multiplicand onto the ppws but if not the program
goes to 'no_add_mbm' where both the ppws and the multiplier
are rotated right. (Where I refer to 'ws_something' I mean
the group of bytes that make up that word, in this case
'multiplicand' to 'multiplicand+3'.) This rotation puts the
lsb of the multiplier into the carry flag ready for another
run around the loop.
Remember we rotate the ppws and multiplier each time we go
around the loop whether or not we add the multiplicand to
the partial product. Following the rotation the X register,
which is counting the loop for us, is reduced by one.
Counting down is usually better than counting up because a
simple BNE will suffice to trap zero rather than having to
CMP with anything. Here we BNE back to 'mbm_loop'.
When we finally fall through the BNE we reach an RTS which
finishes the routine. The four byte result is in
'multiplier' with any overflow in 'ppws'. Then follow the
three FNEQUM functions that reserve memory for the
workspace. If you have BASIC 2 or later you can replace
them with EQUD 0 in each case.
The BASIC at the end prints out the result with a check and
tells you what exactly is in 'ppws' and 'multiplier' so you
can see what happens if you enter large numbers. However,
for a product under 32 bytes the results will be correct for
positive and negative.
Multiplication and division routines are amongst the most
time sensitive in maths. In an early module when I said
that you might wish to do more than just multiply faster I
was in fact hiding the truth. The routines in BBC BASIC are
so efficient that you can multiply two integers together
faster from his BASIC than with this code here. However I
am aiming for clarity (built for comfort not for speed I
believe) which is my excuse and I will stick to it.
If you wish to expand (or contract) this routine to work
with a different number of bytes you simply change the size
of the workspace areas accordingly and add or subtract from
the lists of LDA/ADC/STAs and LSR/RORs. Remember that by
convention with the 6502 a multi-byte number is stored with
its lowest significant byte in the lowest memory location
and the most significant byte in the highest location. This
results from the way a 16 bit address must be stored with
the less significant byte first.
Next time we move on to division and an output routine which
needs division to operate. Then on to a general division
routine similar to the multiplication one in this module.
00000000 4f 53 42 49 54 53 20 2d 20 41 6e 20 45 78 70 6c |OSBITS - An Expl| 00000010 6f 72 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 42 |oration of the B| 00000020 42 43 20 4d 69 63 72 6f 20 61 74 20 4d 61 63 68 |BC Micro at Mach| 00000030 69 6e 65 20 4c 65 76 65 6c 0d 0d 42 79 20 50 72 |ine Level..By Pr| 00000040 6f 67 72 61 6d 6d 65 72 0d 0d 2e 2e 2e 2e 2e 2e |ogrammer........| 00000050 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e |................| * 00000080 2e 2e 2e 2e 2e 0d 0d 0d 50 61 72 74 20 31 33 3a |........Part 13:| 00000090 20 4d 75 6c 74 69 2d 42 79 74 65 20 4d 75 6c 74 | Multi-Byte Mult| 000000a0 69 70 6c 69 63 61 74 69 6f 6e 0d 0d 57 68 69 6c |iplication..Whil| 000000b0 65 20 49 20 68 61 76 65 20 6e 6f 20 64 65 73 69 |e I have no desi| 000000c0 72 65 20 74 6f 20 6c 61 62 6f 75 72 20 74 68 65 |re to labour the| 000000d0 20 70 6f 69 6e 74 20 69 74 20 69 73 20 77 6f 72 | point it is wor| 000000e0 74 68 0d 74 61 6b 69 6e 67 20 61 20 64 65 74 61 |th.taking a deta| 000000f0 69 6c 65 64 20 6c 6f 6f 6b 20 61 74 20 6d 75 6c |iled look at mul| 00000100 74 69 70 6c 69 63 61 74 69 6f 6e 20 77 68 65 72 |tiplication wher| 00000110 65 20 74 68 65 20 6e 75 6d 62 65 72 73 0d 62 65 |e the numbers.be| 00000120 69 6e 67 20 6d 75 6c 74 69 70 6c 69 65 64 20 61 |ing multiplied a| 00000130 72 65 20 62 6f 74 68 20 73 65 76 65 72 61 6c 20 |re both several | 00000140 62 79 74 65 73 20 6c 6f 6e 67 2e 20 20 49 20 68 |bytes long. I h| 00000150 61 76 65 20 63 61 6c 6c 65 64 0d 74 68 69 73 20 |ave called.this | 00000160 6d 75 6c 74 69 2d 62 79 74 65 20 61 72 69 74 68 |multi-byte arith| 00000170 6d 65 74 69 63 20 61 6c 74 68 6f 75 67 68 20 69 |metic although i| 00000180 74 20 69 73 20 6f 66 74 65 6e 20 6b 6e 6f 77 6e |t is often known| 00000190 20 61 73 0d 6d 75 6c 74 69 2d 70 72 65 63 69 73 | as.multi-precis| 000001a0 69 6f 6e 20 61 72 69 74 68 6d 65 74 69 63 2e 0d |ion arithmetic..| 000001b0 0d 54 68 65 20 6c 61 73 74 20 6d 6f 64 75 6c 65 |.The last module| 000001c0 20 69 6e 63 6c 75 64 65 64 20 61 20 72 6f 75 74 | included a rout| 000001d0 69 6e 65 20 77 68 69 63 68 20 6d 75 6c 74 69 70 |ine which multip| 000001e0 6c 69 65 64 20 61 20 6c 61 72 67 65 0d 6e 75 6d |lied a large.num| 000001f0 62 65 72 20 62 79 20 61 20 73 6d 61 6c 6c 20 6f |ber by a small o| 00000200 6e 65 3b 20 61 20 66 6f 75 72 20 62 79 74 65 20 |ne; a four byte | 00000210 6e 75 6d 62 65 72 20 62 79 20 61 20 6f 6e 65 20 |number by a one | 00000220 62 79 74 65 0d 6e 75 6d 62 65 72 2e 20 20 54 68 |byte.number. Th| 00000230 65 20 65 78 74 65 6e 73 69 6f 6e 20 6f 66 20 74 |e extension of t| 00000240 68 69 73 20 74 6f 20 61 72 62 69 74 72 61 72 69 |his to arbitrari| 00000250 6c 79 20 6c 61 72 67 65 20 6e 75 6d 62 65 72 73 |ly large numbers| 00000260 0d 69 73 20 73 74 72 61 69 67 68 74 66 6f 72 77 |.is straightforw| 00000270 61 72 64 20 62 75 74 20 49 20 77 61 6e 74 20 74 |ard but I want t| 00000280 6f 20 64 65 61 6c 20 77 69 74 68 20 69 74 20 73 |o deal with it s| 00000290 65 70 61 72 61 74 65 6c 79 20 73 6f 0d 74 68 61 |eparately so.tha| 000002a0 74 20 61 6e 79 20 63 6f 6e 66 75 73 69 6f 6e 20 |t any confusion | 000002b0 74 68 61 74 20 6d 61 79 20 73 74 69 6c 6c 20 62 |that may still b| 000002c0 65 20 69 6e 20 79 6f 75 72 20 6d 69 6e 64 20 66 |e in your mind f| 000002d0 72 6f 6d 20 6c 61 73 74 0d 74 69 6d 65 20 69 73 |rom last.time is| 000002e0 20 64 69 73 70 65 6c 6c 65 64 2e 0d 0d 4c 65 74 | dispelled...Let| 000002f0 27 73 20 72 65 63 61 70 20 6f 6e 20 74 68 65 20 |'s recap on the | 00000300 6d 65 74 68 6f 64 20 65 6d 70 6c 6f 79 65 64 20 |method employed | 00000310 69 6e 20 6d 75 6c 74 69 70 6c 69 63 61 74 69 6f |in multiplicatio| 00000320 6e 2e 20 20 49 74 20 69 73 0d 65 78 61 63 74 6c |n. It is.exactl| 00000330 79 20 6c 69 6b 65 20 74 68 65 20 6c 6f 6e 67 20 |y like the long | 00000340 6d 75 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 79 |multiplication y| 00000350 6f 75 20 77 69 6c 6c 20 68 61 76 65 20 64 6f 6e |ou will have don| 00000360 65 20 61 74 0d 73 63 68 6f 6f 6c 20 28 61 6e 64 |e at.school (and| 00000370 20 70 72 6f 62 61 62 6c 79 20 6e 6f 74 20 75 73 | probably not us| 00000380 65 64 20 73 69 6e 63 65 29 20 65 78 63 65 70 74 |ed since) except| 00000390 2c 20 6f 66 20 63 6f 75 72 73 65 2c 20 74 68 61 |, of course, tha| 000003a0 74 0d 77 65 20 77 69 6c 6c 20 62 65 20 77 6f 72 |t.we will be wor| 000003b0 6b 69 6e 67 20 69 6e 20 62 69 6e 61 72 79 2e 20 |king in binary. | 000003c0 20 49 72 6f 6e 69 63 61 6c 6c 79 20 74 68 69 73 | Ironically this| 000003d0 20 6d 61 6b 65 73 20 69 74 0d 65 61 73 69 65 72 | makes it.easier| 000003e0 20 61 6c 74 68 6f 75 67 68 20 77 68 65 6e 20 77 | although when w| 000003f0 6f 72 6b 69 6e 67 20 6f 6e 20 70 61 70 65 72 20 |orking on paper | 00000400 77 65 20 68 61 76 65 20 74 6f 20 62 65 20 63 61 |we have to be ca| 00000410 72 65 66 75 6c 0d 61 62 6f 75 74 20 62 69 6e 61 |reful.about bina| 00000420 72 79 20 6d 61 74 68 73 20 62 65 63 61 75 73 65 |ry maths because| 00000430 20 77 65 20 61 72 65 20 75 6e 75 73 65 64 20 74 | we are unused t| 00000440 6f 20 69 74 2e 0d 0d 52 65 74 75 72 6e 69 6e 67 |o it...Returning| 00000450 20 74 6f 20 74 68 65 20 73 69 6e 67 6c 65 20 62 | to the single b| 00000460 79 74 65 20 65 78 61 6d 70 6c 65 20 66 72 6f 6d |yte example from| 00000470 20 6c 61 73 74 20 74 69 6d 65 20 77 65 20 68 61 | last time we ha| 00000480 76 65 0d 74 68 65 20 74 77 6f 20 6e 75 6d 62 65 |ve.the two numbe| 00000490 72 73 20 31 31 20 61 6e 64 20 32 37 20 77 68 69 |rs 11 and 27 whi| 000004a0 63 68 20 77 65 20 77 61 6e 74 20 74 6f 20 6d 75 |ch we want to mu| 000004b0 6c 74 69 70 6c 79 0d 74 6f 67 65 74 68 65 72 2e |ltiply.together.| 000004c0 20 20 31 31 20 69 73 20 31 30 31 31 20 69 6e 20 | 11 is 1011 in | 000004d0 62 69 6e 61 72 79 20 62 65 63 61 75 73 65 20 69 |binary because i| 000004e0 74 20 69 73 20 6d 61 64 65 20 75 70 20 6f 66 0d |t is made up of.| 000004f0 32 5e 33 20 2b 20 32 5e 31 20 2b 20 32 5e 30 20 |2^3 + 2^1 + 2^0 | 00000500 28 38 2b 32 2b 31 29 20 61 6e 64 20 32 37 20 69 |(8+2+1) and 27 i| 00000510 73 20 31 31 30 31 31 20 62 65 63 61 75 73 65 20 |s 11011 because | 00000520 69 74 20 69 73 20 6d 61 64 65 0d 75 70 20 6f 66 |it is made.up of| 00000530 20 32 5e 34 20 2b 20 32 5e 33 20 2b 20 32 5e 31 | 2^4 + 2^3 + 2^1| 00000540 20 2b 20 32 5e 30 20 28 31 36 2b 38 2b 32 2b 31 | + 2^0 (16+8+2+1| 00000550 29 2e 20 20 49 74 20 69 73 20 69 72 72 65 6c 65 |). It is irrele| 00000560 76 61 6e 74 0d 74 68 61 74 20 74 68 65 20 6e 75 |vant.that the nu| 00000570 6d 62 65 72 73 20 61 72 65 20 72 65 6c 61 74 65 |mbers are relate| 00000580 64 20 69 6e 20 61 20 77 61 79 20 74 68 61 74 20 |d in a way that | 00000590 69 73 20 6f 62 76 69 6f 75 73 20 69 6e 0d 62 69 |is obvious in.bi| 000005a0 6e 61 72 79 2e 0d 0d 20 20 20 20 20 20 20 20 20 |nary... | 000005b0 20 20 20 20 20 20 20 20 20 20 20 20 31 31 30 31 | 1101| 000005c0 31 0d 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |1. | 000005d0 20 20 20 20 20 20 20 20 20 20 20 78 0d 20 20 20 | x. | 000005e0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000005f0 20 20 20 31 30 31 31 0d 20 20 20 20 20 20 20 20 | 1011. | 00000600 20 20 20 20 20 20 20 20 20 2d 2d 2d 2d 2d 2d 2d | -------| 00000610 2d 2d 0d 20 20 20 20 20 20 20 20 20 20 20 20 20 |--. | 00000620 20 20 20 20 20 20 20 20 31 31 30 31 31 0d 20 20 | 11011. | 00000630 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000640 20 20 31 31 30 31 31 6f 0d 20 20 20 20 20 20 20 | 11011o. | 00000650 20 20 20 20 20 20 20 20 20 20 20 31 31 30 31 31 | 11011| 00000660 6f 6f 6f 0d 20 20 20 20 20 20 20 20 20 20 20 20 |ooo. | 00000670 20 20 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d 20 | ---------. | 00000680 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000690 31 30 30 31 30 31 30 30 31 0d 0d 54 68 69 73 20 |100101001..This | 000006a0 69 73 20 68 6f 77 20 77 65 20 63 61 72 72 69 65 |is how we carrie| 000006b0 64 20 6f 75 74 20 74 68 65 20 6d 75 6c 74 69 70 |d out the multip| 000006c0 6c 69 63 61 74 69 6f 6e 20 69 6e 20 74 68 65 20 |lication in the | 000006d0 6c 61 73 74 0d 6d 6f 64 75 6c 65 2e 20 20 57 68 |last.module. Wh| 000006e0 65 6e 20 77 65 20 73 74 61 72 74 20 6d 75 6c 74 |en we start mult| 000006f0 69 70 6c 79 69 6e 67 20 6c 61 72 67 65 20 6e 75 |iplying large nu| 00000700 6d 62 65 72 73 20 74 6f 67 65 74 68 65 72 0d 74 |mbers together.t| 00000710 68 6f 75 67 68 20 77 65 20 72 75 6e 20 69 6e 74 |hough we run int| 00000720 6f 20 61 20 70 72 6f 62 6c 65 6d 2e 20 20 49 66 |o a problem. If| 00000730 20 79 6f 75 20 6d 75 6c 74 69 70 6c 79 20 61 20 | you multiply a | 00000740 6e 75 6d 62 65 72 20 77 69 74 68 0d 78 20 62 69 |number with.x bi| 00000750 74 73 20 62 79 20 61 20 6e 75 6d 62 65 72 20 77 |ts by a number w| 00000760 69 74 68 20 79 20 62 69 74 73 20 74 68 65 20 70 |ith y bits the p| 00000770 72 6f 64 75 63 74 20 68 61 73 20 78 2b 79 20 62 |roduct has x+y b| 00000780 69 74 73 20 28 49 27 6d 0d 61 73 73 75 6d 69 6e |its (I'm.assumin| 00000790 67 20 74 68 65 20 6e 75 6d 62 65 72 73 20 61 72 |g the numbers ar| 000007a0 65 20 62 6f 74 68 20 70 6f 73 69 74 69 76 65 29 |e both positive)| 000007b0 2e 20 20 49 66 20 79 6f 75 20 77 61 6e 74 20 74 |. If you want t| 000007c0 6f 0d 6d 61 6b 65 20 73 75 72 65 20 74 68 61 74 |o.make sure that| 000007d0 20 79 6f 75 72 20 72 65 73 75 6c 74 20 64 6f 65 | your result doe| 000007e0 73 20 6e 6f 74 20 6f 76 65 72 66 6c 6f 77 20 79 |s not overflow y| 000007f0 6f 75 20 68 61 76 65 20 74 6f 0d 61 6c 6c 6f 77 |ou have to.allow| 00000800 20 66 6f 72 20 61 20 72 65 73 75 6c 74 20 6f 66 | for a result of| 00000810 20 74 68 61 74 20 73 69 7a 65 2e 20 20 54 68 69 | that size. Thi| 00000820 73 20 69 6e 20 66 61 63 74 20 6d 65 61 6e 73 20 |s in fact means | 00000830 74 68 61 74 0d 77 68 65 6e 20 79 6f 75 20 64 6f |that.when you do| 00000840 20 79 6f 75 72 20 6d 75 6c 74 69 70 6c 69 63 61 | your multiplica| 00000850 74 69 6f 6e 20 79 6f 75 20 68 61 76 65 20 74 6f |tion you have to| 00000860 20 68 61 76 65 20 61 20 70 61 72 74 69 61 6c 0d | have a partial.| 00000870 70 72 6f 64 75 63 74 20 77 6f 72 6b 73 70 61 63 |product workspac| 00000880 65 20 74 68 61 74 20 69 73 20 78 2b 79 20 62 69 |e that is x+y bi| 00000890 74 73 20 6c 6f 6e 67 2e 20 20 4f 62 76 69 6f 75 |ts long. Obviou| 000008a0 73 6c 79 20 74 68 65 20 6d 6f 72 65 0d 62 69 74 |sly the more.bit| 000008b0 73 20 69 6e 20 79 6f 75 72 20 70 61 72 74 69 61 |s in your partia| 000008c0 6c 20 70 72 6f 64 75 63 74 20 77 6f 72 6b 73 70 |l product worksp| 000008d0 61 63 65 20 74 68 65 20 73 6c 6f 77 65 72 20 74 |ace the slower t| 000008e0 68 65 0d 72 6f 75 74 69 6e 65 20 62 65 63 6f 6d |he.routine becom| 000008f0 65 73 20 62 65 63 61 75 73 65 20 79 6f 75 20 61 |es because you a| 00000900 72 65 20 63 61 72 72 79 69 6e 67 20 6f 75 74 20 |re carrying out | 00000910 61 64 64 69 74 69 6f 6e 73 20 6f 6e 0d 6d 6f 72 |additions on.mor| 00000920 65 20 62 79 74 65 73 20 74 68 61 6e 20 79 6f 75 |e bytes than you| 00000930 20 77 61 6e 74 20 74 68 65 20 72 65 73 75 6c 74 | want the result| 00000940 20 74 6f 20 68 61 76 65 2e 0d 0d 49 74 27 73 20 | to have...It's | 00000950 77 6f 72 74 68 20 6c 6f 6f 6b 69 6e 67 20 61 74 |worth looking at| 00000960 20 61 20 64 69 66 66 65 72 65 6e 74 20 61 6c 67 | a different alg| 00000970 6f 72 69 74 68 6d 20 73 69 6e 63 65 20 74 68 65 |orithm since the| 00000980 72 65 20 61 72 65 0d 73 65 76 65 72 61 6c 20 77 |re are.several w| 00000990 61 79 73 20 6f 66 20 69 6d 70 6c 65 6d 65 6e 74 |ays of implement| 000009a0 69 6e 67 20 6d 75 6c 74 69 70 6c 69 63 61 74 69 |ing multiplicati| 000009b0 6f 6e 2e 20 46 69 72 73 74 20 49 27 6c 6c 0d 72 |on. First I'll.r| 000009c0 65 77 72 69 74 65 20 74 68 65 20 73 75 6d 20 61 |ewrite the sum a| 000009d0 62 6f 76 65 20 74 6f 20 73 65 70 61 72 61 74 65 |bove to separate| 000009e0 20 6f 75 74 20 74 68 65 20 74 77 6f 20 61 64 64 | out the two add| 000009f0 69 74 69 6f 6e 73 2e 0d 0d 20 20 20 20 20 20 20 |itions... | 00000a00 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 31 | 11| 00000a10 30 31 31 0d 20 20 20 20 20 20 20 20 20 20 20 20 |011. | 00000a20 20 20 20 20 20 20 20 20 20 20 20 20 20 78 0d 20 | x. | 00000a30 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000a40 20 20 20 20 20 31 30 31 31 0d 20 20 20 20 20 20 | 1011. | 00000a50 20 20 20 20 20 20 20 20 20 20 20 2d 2d 2d 2d 2d | -----| 00000a60 2d 2d 2d 2d 0d 20 20 20 20 20 20 20 20 20 20 20 |----. | 00000a70 20 20 20 20 20 20 20 20 20 20 31 31 30 31 31 0d | 11011.| 00000a80 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000a90 20 20 20 20 31 31 30 31 31 6f 0d 20 20 20 20 20 | 11011o. | 00000aa0 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d 2d 2d | ----| 00000ab0 2d 2d 2d 2d 2d 0d 20 20 20 20 20 20 20 20 20 20 |-----. | 00000ac0 20 20 20 20 20 20 20 20 20 31 30 31 30 30 30 31 | 1010001| 00000ad0 0d 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00000ae0 20 20 20 31 31 30 31 31 6f 6f 6f 0d 20 20 20 20 | 11011ooo. | 00000af0 20 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d 2d | ---| 00000b00 2d 2d 2d 2d 2d 2d 0d 20 20 20 20 20 20 20 20 20 |------. | 00000b10 20 20 20 20 20 20 20 20 31 30 30 31 30 31 30 30 | 10010100| 00000b20 31 0d 0d 57 68 61 74 20 77 65 20 61 72 65 20 64 |1..What we are d| 00000b30 6f 69 6e 67 20 68 65 72 65 20 69 73 20 73 68 69 |oing here is shi| 00000b40 66 74 69 6e 67 20 74 68 65 20 6d 75 6c 74 69 70 |fting the multip| 00000b50 6c 69 63 61 6e 64 20 6c 65 66 74 20 61 6e 64 0d |licand left and.| 00000b60 74 68 65 6e 20 63 6f 6e 64 69 74 69 6f 6e 61 6c |then conditional| 00000b70 6c 79 20 61 64 64 69 6e 67 20 69 74 20 6f 6e 74 |ly adding it ont| 00000b80 6f 20 74 68 65 20 70 61 72 74 69 61 6c 20 70 72 |o the partial pr| 00000b90 6f 64 75 63 74 2e 20 20 41 73 0d 61 6e 20 61 6c |oduct. As.an al| 00000ba0 74 65 72 6e 61 74 69 76 65 20 68 6f 77 20 61 62 |ternative how ab| 00000bb0 6f 75 74 20 73 68 69 66 74 69 6e 67 20 74 68 65 |out shifting the| 00000bc0 20 70 61 72 74 69 61 6c 20 70 72 6f 64 75 63 74 | partial product| 00000bd0 20 72 69 67 68 74 0d 69 6e 73 74 65 61 64 3f 20 | right.instead? | 00000be0 20 54 68 69 73 20 77 6f 75 6c 64 20 6c 6f 6f 6b | This would look| 00000bf0 20 6c 69 6b 65 20 74 68 69 73 3a 0d 0d 20 20 20 | like this:.. | 00000c00 20 20 20 20 31 31 30 31 31 0d 20 20 20 20 20 20 | 11011. | 00000c10 20 20 20 20 20 78 0d 20 20 20 20 20 20 20 20 31 | x. 1| 00000c20 30 31 31 0d 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d |011. ---------| 00000c30 0d 20 20 20 20 20 20 20 30 30 30 30 30 20 20 20 |. 00000 | 00000c40 20 20 20 20 70 70 77 73 20 69 73 20 65 6d 70 74 | ppws is empt| 00000c50 79 20 74 6f 20 73 74 61 72 74 20 77 69 74 68 0d |y to start with.| 00000c60 0d 20 20 20 20 20 20 20 31 31 30 31 31 20 20 20 |. 11011 | 00000c70 20 20 20 20 6c 73 62 20 6f 66 20 31 30 31 31 20 | lsb of 1011 | 00000c80 69 73 20 31 20 73 6f 20 61 64 64 20 31 31 30 31 |is 1 so add 1101| 00000c90 31 20 74 6f 20 70 70 77 73 0d 20 20 20 20 20 20 |1 to ppws. | 00000ca0 20 31 31 30 31 31 20 20 20 20 20 20 20 6e 65 77 | 11011 new| 00000cb0 20 70 70 77 73 0d 20 20 20 20 20 20 20 20 31 31 | ppws. 11| 00000cc0 30 31 20 31 20 20 20 20 20 73 68 69 66 74 20 70 |01 1 shift p| 00000cd0 70 77 73 20 72 69 67 68 74 20 6f 6e 65 20 62 69 |pws right one bi| 00000ce0 74 0d 0d 20 20 20 20 20 20 20 31 31 30 31 31 20 |t.. 11011 | 00000cf0 20 20 20 20 20 20 62 69 74 20 31 20 6f 66 20 31 | bit 1 of 1| 00000d00 30 31 31 20 69 73 20 31 20 73 6f 20 61 64 64 20 |011 is 1 so add | 00000d10 31 31 30 31 31 20 74 6f 20 70 70 77 73 0d 20 20 |11011 to ppws. | 00000d20 20 20 20 20 31 30 31 30 30 30 20 31 0d 20 20 20 | 101000 1. | 00000d30 20 20 20 20 31 30 31 30 30 20 30 31 20 20 20 20 | 10100 01 | 00000d40 73 68 69 66 74 20 70 70 77 73 20 72 69 67 68 74 |shift ppws right| 00000d50 20 6f 6e 65 20 62 69 74 0d 0d 20 20 20 20 20 20 | one bit.. | 00000d60 20 30 30 30 30 30 20 20 20 20 20 20 20 62 69 74 | 00000 bit| 00000d70 20 32 20 6f 66 20 31 30 31 31 20 69 73 20 30 20 | 2 of 1011 is 0 | 00000d80 73 6f 20 64 6f 6e 27 74 20 61 64 64 0d 20 20 20 |so don't add. | 00000d90 20 20 20 20 31 30 31 30 30 20 30 31 20 20 20 20 | 10100 01 | 00000da0 6e 65 77 20 70 70 77 73 0d 20 20 20 20 20 20 20 |new ppws. | 00000db0 20 31 30 31 30 20 30 30 31 20 20 20 73 68 69 66 | 1010 001 shif| 00000dc0 74 20 70 70 77 73 20 72 69 67 68 74 20 6f 6e 65 |t ppws right one| 00000dd0 20 62 69 74 0d 0d 20 20 20 20 20 20 20 31 31 30 | bit.. 110| 00000de0 31 31 20 20 20 20 20 20 20 62 69 74 20 33 20 6f |11 bit 3 o| 00000df0 66 20 31 30 31 31 20 69 73 20 31 20 73 6f 20 61 |f 1011 is 1 so a| 00000e00 64 64 20 31 31 30 31 31 20 74 6f 20 70 70 77 73 |dd 11011 to ppws| 00000e10 0d 20 20 20 20 20 20 31 30 30 31 30 31 20 30 30 |. 100101 00| 00000e20 31 20 20 20 6e 65 77 20 70 70 77 73 0d 20 20 20 |1 new ppws. | 00000e30 20 20 20 20 31 30 30 31 30 20 31 30 30 31 20 20 | 10010 1001 | 00000e40 73 68 69 66 74 20 70 70 77 73 20 72 69 67 68 74 |shift ppws right| 00000e50 20 6f 6e 65 20 62 69 74 0d 0d 49 66 20 77 65 20 | one bit..If we | 00000e60 63 6f 75 6e 74 20 6c 65 61 64 69 6e 67 20 7a 65 |count leading ze| 00000e70 72 6f 73 20 69 6e 20 6f 75 72 20 6d 75 6c 74 69 |ros in our multi| 00000e80 70 6c 69 65 72 20 61 6e 64 20 73 6f 20 63 61 72 |plier and so car| 00000e90 72 79 20 6f 75 74 0d 65 69 67 68 74 20 6f 70 65 |ry out.eight ope| 00000ea0 72 61 74 69 6f 6e 73 20 28 74 68 65 20 6e 65 78 |rations (the nex| 00000eb0 74 20 62 79 74 65 20 73 69 7a 65 20 75 70 29 20 |t byte size up) | 00000ec0 77 65 20 63 61 72 72 79 20 6f 75 74 0d 61 6e 6f |we carry out.ano| 00000ed0 74 68 65 72 20 66 6f 75 72 20 73 68 69 66 74 73 |ther four shifts| 00000ee0 20 61 6e 64 20 67 65 74 20 74 68 65 20 72 65 73 | and get the res| 00000ef0 75 6c 74 0d 0d 20 20 20 20 20 20 20 20 20 20 20 |ult.. | 00000f00 20 20 20 20 20 20 20 31 20 30 30 31 30 31 30 30 | 1 0010100| 00000f10 31 0d 0d 4f 6e 20 65 61 63 68 20 6f 63 63 61 73 |1..On each occas| 00000f20 69 6f 6e 20 77 65 20 61 72 65 20 73 68 69 66 74 |ion we are shift| 00000f30 69 6e 67 20 74 68 65 20 6d 75 6c 74 69 70 6c 69 |ing the multipli| 00000f40 65 72 20 72 69 67 68 74 20 74 6f 0d 73 74 61 72 |er right to.star| 00000f50 74 20 77 69 74 68 20 61 6e 64 20 74 68 65 6e 20 |t with and then | 00000f60 69 6d 6d 65 64 69 61 74 65 6c 79 20 61 66 74 65 |immediately afte| 00000f70 72 77 61 72 64 73 20 77 65 20 73 68 69 66 74 20 |rwards we shift | 00000f80 74 68 65 20 70 70 77 73 0d 72 69 67 68 74 2e 20 |the ppws.right. | 00000f90 20 4e 6f 77 20 74 68 69 73 20 63 6f 75 6c 64 20 | Now this could | 00000fa0 62 65 20 61 20 75 73 65 66 75 6c 20 66 65 61 74 |be a useful feat| 00000fb0 75 72 65 20 62 65 63 61 75 73 65 20 69 66 20 77 |ure because if w| 00000fc0 65 20 63 61 6e 0d 63 6f 6d 62 69 6e 65 20 74 68 |e can.combine th| 00000fd0 65 20 74 77 6f 20 73 68 69 66 74 73 2c 20 6d 75 |e two shifts, mu| 00000fe0 6c 74 69 70 6c 69 65 72 20 61 6e 64 20 70 70 77 |ltiplier and ppw| 00000ff0 73 2c 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65 |s, into a single| 00001000 0d 73 68 69 66 74 1a 20 6f 70 65 72 61 74 69 6f |.shift. operatio| 00001010 6e 20 77 65 20 77 69 6c 6c 20 65 6e 64 20 75 70 |n we will end up| 00001020 20 77 69 74 68 20 74 68 65 20 72 65 73 75 6c 74 | with the result| 00001030 20 69 6e 20 74 68 65 20 73 70 61 63 65 0d 77 68 | in the space.wh| 00001040 65 72 65 20 74 68 65 20 6d 75 6c 74 69 70 6c 69 |ere the multipli| 00001050 65 72 20 77 61 73 2e 0d 0d 49 20 68 61 76 65 6e |er was...I haven| 00001060 27 74 20 77 6f 72 72 69 65 64 20 74 6f 6f 20 6d |'t worried too m| 00001070 75 63 68 20 61 62 6f 75 74 20 73 70 65 65 64 20 |uch about speed | 00001080 62 65 66 6f 72 65 2e 20 20 57 69 74 68 20 74 68 |before. With th| 00001090 65 0d 6e 75 6d 62 65 72 20 74 72 61 6e 73 6c 61 |e.number transla| 000010a0 74 69 6f 6e 20 70 72 6f 67 72 61 6d 20 6c 61 73 |tion program las| 000010b0 74 20 74 69 6d 65 20 74 68 65 20 73 70 65 65 64 |t time the speed| 000010c0 20 6f 66 20 74 68 65 20 75 73 65 72 0d 77 61 73 | of the user.was| 000010d0 20 74 68 65 20 6c 69 6d 69 74 69 6e 67 20 66 61 | the limiting fa| 000010e0 63 74 6f 72 20 61 6e 79 77 61 79 2c 20 73 6f 20 |ctor anyway, so | 000010f0 73 70 65 65 64 20 63 6f 6e 73 69 64 65 72 61 74 |speed considerat| 00001100 69 6f 6e 73 20 77 65 72 65 0d 69 72 72 65 6c 65 |ions were.irrele| 00001110 76 61 6e 74 2e 20 20 57 69 74 68 20 61 20 6d 75 |vant. With a mu| 00001120 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 73 70 65 |ltiplication spe| 00001130 65 64 20 69 73 20 61 20 76 65 72 79 20 69 6d 70 |ed is a very imp| 00001140 6f 72 74 61 6e 74 0d 63 6f 6e 73 69 64 65 72 61 |ortant.considera| 00001150 74 69 6f 6e 20 73 6f 20 6c 65 74 27 73 20 6c 6f |tion so let's lo| 00001160 6f 6b 20 61 74 20 74 68 65 20 61 6c 67 6f 72 69 |ok at the algori| 00001170 74 68 6d 20 77 65 20 68 61 76 65 20 63 6f 6d 65 |thm we have come| 00001180 20 75 70 0d 77 69 74 68 20 6e 6f 77 2e 0d 0d 20 | up.with now... | 00001190 20 20 20 43 6c 65 61 72 20 70 70 77 73 20 28 70 | Clear ppws (p| 000011a0 61 72 74 69 61 6c 20 70 72 6f 64 75 63 74 20 77 |artial product w| 000011b0 6f 72 6b 20 73 70 61 63 65 29 0d 20 20 20 20 53 |ork space). S| 000011c0 68 69 66 74 20 6d 75 6c 74 69 70 6c 69 65 72 20 |hift multiplier | 000011d0 72 69 67 68 74 2c 20 70 75 74 73 20 6c 73 62 20 |right, puts lsb | 000011e0 69 6e 74 6f 20 63 61 72 72 79 20 66 6c 61 67 0d |into carry flag.| 000011f0 20 20 20 20 49 66 20 63 61 72 72 79 20 73 65 74 | If carry set| 00001200 20 61 64 64 20 6d 75 6c 74 69 70 6c 69 63 61 6e | add multiplican| 00001210 64 20 74 6f 20 70 70 77 73 0d 20 20 20 20 53 68 |d to ppws. Sh| 00001220 69 66 74 20 70 70 77 73 20 61 6e 64 20 6d 75 6c |ift ppws and mul| 00001230 74 69 70 6c 69 65 72 20 72 69 67 68 74 0d 20 20 |tiplier right. | 00001240 20 20 52 65 70 65 61 74 20 6c 61 73 74 20 74 77 | Repeat last tw| 00001250 6f 20 6c 69 6e 65 73 20 75 6e 74 69 6c 20 61 6c |o lines until al| 00001260 6c 20 62 69 74 73 20 70 72 6f 63 65 73 73 65 64 |l bits processed| 00001270 0d 0d 57 68 65 6e 20 79 6f 75 20 68 61 76 65 20 |..When you have | 00001280 66 69 6e 69 73 68 65 64 20 74 68 65 20 6c 6f 77 |finished the low| 00001290 65 72 20 62 79 74 65 73 20 6f 66 20 74 68 65 20 |er bytes of the | 000012a0 72 65 73 75 6c 74 20 68 61 76 65 0d 72 65 70 6c |result have.repl| 000012b0 61 63 65 64 20 74 68 65 20 6d 75 6c 74 69 70 6c |aced the multipl| 000012c0 69 63 61 6e 64 20 61 6e 64 20 74 68 65 20 27 6f |icand and the 'o| 000012d0 76 65 72 66 6c 6f 77 27 20 72 65 6d 61 69 6e 73 |verflow' remains| 000012e0 20 69 6e 20 74 68 65 0d 70 70 77 73 2e 20 20 4e | in the.ppws. N| 000012f0 6f 77 20 74 68 61 74 20 6c 6f 6f 6b 73 20 73 68 |ow that looks sh| 00001300 6f 72 74 20 61 6e 64 20 74 6f 20 74 68 65 20 70 |ort and to the p| 00001310 6f 69 6e 74 2c 20 74 68 65 20 6f 6e 6c 79 0d 61 |oint, the only.a| 00001320 73 79 6d 6d 65 74 72 69 63 61 6c 20 70 61 72 74 |symmetrical part| 00001330 20 62 65 69 6e 67 20 74 68 65 20 69 6e 69 74 69 | being the initi| 00001340 61 6c 20 73 68 69 66 74 2c 20 62 75 74 20 77 65 |al shift, but we| 00001350 27 76 65 20 67 6f 74 20 74 6f 0d 73 74 61 72 74 |'ve got to.start| 00001360 20 73 6f 6d 65 77 68 65 72 65 2e 0d 0d 53 6f 20 | somewhere...So | 00001370 6c 65 74 27 73 20 74 75 72 6e 20 69 74 20 69 6e |let's turn it in| 00001380 74 6f 20 61 20 70 72 6f 67 72 61 6d 2e 0d 0d 57 |to a program...W| 00001390 68 65 6e 20 72 6f 74 61 74 69 6e 67 20 61 20 6d |hen rotating a m| 000013a0 75 6c 74 69 2d 62 79 74 65 20 6e 75 6d 62 65 72 |ulti-byte number| 000013b0 20 79 6f 75 20 73 74 61 72 74 20 61 74 20 74 68 | you start at th| 000013c0 65 20 66 61 72 20 65 6e 64 2c 0d 28 69 2e 65 2e |e far end,.(i.e.| 000013d0 20 69 66 20 72 6f 74 61 74 69 6e 67 20 6c 65 66 | if rotating lef| 000013e0 74 20 73 74 61 72 74 20 61 74 20 74 68 65 20 72 |t start at the r| 000013f0 69 67 68 74 20 61 6e 64 20 76 69 63 65 20 76 65 |ight and vice ve| 00001400 72 73 61 29 0d 61 6e 64 20 75 73 65 20 41 53 4c |rsa).and use ASL| 00001410 20 6f 72 20 4c 53 52 20 61 73 20 74 68 65 20 66 | or LSR as the f| 00001420 69 72 73 74 20 72 6f 74 61 74 69 6f 6e 20 73 6f |irst rotation so| 00001430 20 74 68 61 74 20 79 6f 75 20 64 6f 20 6e 6f 74 | that you do not| 00001440 0d 73 68 69 66 74 20 74 68 65 20 63 61 72 72 79 |.shift the carry| 00001450 20 76 61 6c 75 65 20 69 6e 2c 20 62 65 63 61 75 | value in, becau| 00001460 73 65 20 79 6f 75 20 64 6f 20 6e 6f 74 20 77 61 |se you do not wa| 00001470 6e 74 20 69 74 21 20 20 54 68 65 0d 6f 74 68 65 |nt it! The.othe| 00001480 72 20 72 6f 74 61 74 65 73 20 77 69 6c 6c 20 62 |r rotates will b| 00001490 65 20 52 4f 4c 20 6f 72 20 52 4f 52 20 62 65 63 |e ROL or ROR bec| 000014a0 61 75 73 65 20 74 68 65 6e 20 79 6f 75 20 75 73 |ause then you us| 000014b0 65 20 74 68 65 0d 63 61 72 72 79 20 74 6f 20 63 |e the.carry to c| 000014c0 61 72 72 79 20 74 68 65 20 72 65 6c 65 76 61 6e |arry the relevan| 000014d0 74 20 62 69 74 20 6f 76 65 72 20 66 72 6f 6d 20 |t bit over from | 000014e0 6f 6e 65 20 62 79 74 65 20 74 6f 20 74 68 65 0d |one byte to the.| 000014f0 6e 65 78 74 2e 20 20 49 6e 20 74 68 69 73 20 63 |next. In this c| 00001500 61 73 65 20 77 65 20 77 69 6c 6c 20 74 72 65 61 |ase we will trea| 00001510 74 20 74 68 65 20 70 70 77 73 20 61 6e 64 20 6d |t the ppws and m| 00001520 75 6c 74 69 70 6c 69 65 72 20 61 73 0d 61 20 73 |ultiplier as.a s| 00001530 69 6e 67 6c 65 20 6c 6f 6e 67 20 62 6c 6f 63 6b |ingle long block| 00001540 20 6f 66 20 6d 65 6d 6f 72 79 20 77 69 74 68 20 | of memory with | 00001550 74 68 65 20 70 70 77 73 20 74 6f 20 74 68 65 20 |the ppws to the | 00001560 6c 65 66 74 20 6f 66 0d 74 68 65 20 6d 75 6c 74 |left of.the mult| 00001570 69 70 6c 69 65 72 2e 0d 0d 54 68 65 72 65 20 69 |iplier...There i| 00001580 73 20 6e 6f 20 6c 69 6d 69 74 20 74 6f 20 74 68 |s no limit to th| 00001590 65 20 73 69 7a 65 20 6f 66 20 6e 75 6d 62 65 72 |e size of number| 000015a0 73 20 79 6f 75 20 63 61 6e 20 6d 75 6c 74 69 70 |s you can multip| 000015b0 6c 79 0d 74 6f 67 65 74 68 65 72 20 77 69 74 68 |ly.together with| 000015c0 20 74 68 69 73 20 6d 65 74 68 6f 64 2e 20 20 52 | this method. R| 000015d0 65 6d 65 6d 62 65 72 20 74 68 61 74 20 61 20 66 |emember that a f| 000015e0 6f 75 72 20 62 79 74 65 20 6e 75 6d 62 65 72 0d |our byte number.| 000015f0 6d 75 6c 74 69 70 6c 69 65 64 20 62 79 20 61 6e |multiplied by an| 00001600 6f 74 68 65 72 20 66 6f 75 72 20 62 79 74 65 20 |other four byte | 00001610 6e 75 6d 62 65 72 20 63 61 6e 20 72 65 73 75 6c |number can resul| 00001620 74 20 69 6e 20 61 6e 0d 65 69 67 68 74 20 62 79 |t in an.eight by| 00001630 74 65 20 72 65 73 75 6c 74 2c 20 73 6f 20 79 6f |te result, so yo| 00001640 75 20 68 61 76 65 20 74 6f 20 61 6c 6c 6f 77 20 |u have to allow | 00001650 66 6f 72 20 74 68 69 73 0d 70 6f 73 73 69 62 69 |for this.possibi| 00001660 6c 69 74 79 2e 20 20 49 66 20 77 65 20 77 65 72 |lity. If we wer| 00001670 65 20 64 65 61 6c 69 6e 67 20 73 6f 6c 65 6c 79 |e dealing solely| 00001680 20 77 69 74 68 20 70 6f 73 69 74 69 76 65 0d 6e | with positive.n| 00001690 75 6d 62 65 72 73 20 74 68 65 6e 2c 20 62 79 20 |umbers then, by | 000016a0 74 72 65 61 74 69 6e 67 20 74 68 65 20 70 70 77 |treating the ppw| 000016b0 73 20 61 6e 64 20 6d 75 6c 74 69 70 6c 69 65 72 |s and multiplier| 000016c0 20 61 73 20 61 0d 73 69 6e 67 6c 65 20 70 69 65 | as a.single pie| 000016d0 63 65 20 6f 66 20 77 6f 72 6b 20 73 70 61 63 65 |ce of work space| 000016e0 2c 20 77 65 20 77 6f 75 6c 64 20 61 75 74 6f 6d |, we would autom| 000016f0 61 74 69 63 61 6c 6c 79 20 68 61 76 65 0d 65 6e |atically have.en| 00001700 6f 75 67 68 20 72 6f 6f 6d 20 66 6f 72 20 61 20 |ough room for a | 00001710 6c 61 72 67 65 20 72 65 73 75 6c 74 2e 20 20 57 |large result. W| 00001720 65 20 63 6f 75 6c 64 20 74 65 73 74 20 66 6f 72 |e could test for| 00001730 20 61 6e 0d 6f 76 65 72 66 6c 6f 77 20 62 79 20 | an.overflow by | 00001740 6c 6f 6f 6b 69 6e 67 20 74 6f 20 73 65 65 20 69 |looking to see i| 00001750 66 20 61 6e 79 74 68 69 6e 67 20 77 61 73 20 69 |f anything was i| 00001760 6e 20 74 68 65 20 74 6f 70 20 34 0d 62 79 74 65 |n the top 4.byte| 00001770 73 2e 0d 0d 41 20 6e 65 67 61 74 69 76 65 20 6e |s...A negative n| 00001780 75 6d 62 65 72 20 77 69 74 68 20 34 20 62 79 74 |umber with 4 byt| 00001790 65 73 20 69 73 20 64 65 66 69 6e 65 64 20 61 73 |es is defined as| 000017a0 20 6f 6e 65 20 77 69 74 68 20 74 68 65 0d 74 6f | one with the.to| 000017b0 70 20 6d 6f 73 74 20 62 69 74 20 28 62 69 74 20 |p most bit (bit | 000017c0 33 31 29 20 73 65 74 2e 20 20 43 6c 65 61 72 6c |31) set. Clearl| 000017d0 79 20 69 66 20 77 65 20 61 72 65 20 77 6f 72 6b |y if we are work| 000017e0 69 6e 67 20 74 6f 20 61 0d 36 34 20 62 69 74 20 |ing to a.64 bit | 000017f0 72 65 73 75 6c 74 20 74 68 65 6e 20 74 68 61 74 |result then that| 00001800 20 6e 75 6d 62 65 72 20 73 68 6f 75 6c 64 20 62 | number should b| 00001810 65 20 68 65 6c 64 20 69 6e 20 6d 65 6d 6f 72 79 |e held in memory| 00001820 20 69 6e 0d 38 20 62 79 74 65 73 20 77 69 74 68 | in.8 bytes with| 00001830 20 74 68 65 20 74 6f 70 20 62 69 74 20 28 6e 75 | the top bit (nu| 00001840 6d 62 65 72 20 36 33 29 20 73 65 74 2e 20 20 41 |mber 63) set. A| 00001850 6c 6c 20 74 68 65 20 62 69 74 73 0d 62 65 74 77 |ll the bits.betw| 00001860 65 65 6e 20 33 31 20 61 6e 64 20 36 33 20 77 6f |een 31 and 63 wo| 00001870 75 6c 64 20 61 6c 73 6f 20 62 65 20 73 65 74 2e |uld also be set.| 00001880 20 20 54 6f 20 6d 61 6b 65 20 74 68 69 73 20 72 | To make this r| 00001890 6f 75 74 69 6e 65 0d 6f 70 65 72 61 74 65 20 74 |outine.operate t| 000018a0 6f 74 61 6c 6c 79 20 63 6f 72 72 65 63 74 6c 79 |otally correctly| 000018b0 20 66 6f 72 20 6e 65 67 61 74 69 76 65 20 6e 75 | for negative nu| 000018c0 6d 62 65 72 73 20 77 65 20 77 6f 75 6c 64 20 68 |mbers we would h| 000018d0 61 76 65 0d 74 6f 20 65 78 70 61 6e 64 20 74 68 |ave.to expand th| 000018e0 65 20 6d 75 6c 74 69 70 6c 69 65 72 20 61 6e 64 |e multiplier and| 000018f0 20 6d 75 6c 74 69 70 6c 69 63 61 6e 64 20 69 6e | multiplicand in| 00001900 74 6f 20 36 34 20 62 69 74 0d 6e 75 6d 62 65 72 |to 64 bit.number| 00001910 73 20 61 6e 64 20 68 61 76 65 20 61 20 72 6f 75 |s and have a rou| 00001920 74 69 6e 65 20 74 68 61 74 20 72 61 6e 20 74 68 |tine that ran th| 00001930 72 6f 75 67 68 20 36 34 20 74 69 6d 65 73 20 69 |rough 64 times i| 00001940 6e 73 74 65 61 64 0d 6f 66 20 33 32 2e 20 20 46 |nstead.of 32. F| 00001950 6f 72 20 73 69 6d 70 6c 69 63 69 74 79 20 49 20 |or simplicity I | 00001960 68 61 76 65 20 6e 6f 74 20 64 6f 6e 65 20 73 6f |have not done so| 00001970 2e 20 20 54 68 65 20 72 65 73 75 6c 74 20 69 73 |. The result is| 00001980 0d 74 68 61 74 20 69 74 20 69 73 20 70 6f 73 73 |.that it is poss| 00001990 69 62 6c 65 20 74 6f 20 67 65 6e 65 72 61 74 65 |ible to generate| 000019a0 20 61 20 72 65 73 75 6c 74 20 28 70 6f 73 69 74 | a result (posit| 000019b0 69 76 65 20 6f 72 0d 6e 65 67 61 74 69 76 65 29 |ive or.negative)| 000019c0 20 74 68 61 74 20 69 73 20 74 6f 6f 20 62 69 67 | that is too big| 000019d0 20 62 75 74 20 69 74 20 69 73 20 76 65 72 79 20 | but it is very | 000019e0 64 69 66 66 69 63 75 6c 74 20 74 6f 20 74 72 61 |difficult to tra| 000019f0 70 2e 0d 0d 54 68 65 20 73 69 6d 70 6c 65 73 74 |p...The simplest| 00001a00 20 73 6f 6c 75 74 69 6f 6e 20 77 6f 75 6c 64 20 | solution would | 00001a10 62 65 20 74 6f 20 63 68 65 63 6b 20 74 6f 20 73 |be to check to s| 00001a20 65 65 20 77 68 61 74 20 73 69 67 6e 20 74 68 65 |ee what sign the| 00001a30 0d 72 65 73 75 6c 74 20 73 68 6f 75 6c 64 20 62 |.result should b| 00001a40 65 20 61 6e 64 20 74 68 65 6e 20 63 6f 6e 76 65 |e and then conve| 00001a50 72 74 20 62 6f 74 68 20 6e 75 6d 62 65 72 73 20 |rt both numbers | 00001a60 74 6f 20 70 6f 73 69 74 69 76 65 2c 0d 63 61 72 |to positive,.car| 00001a70 72 79 20 6f 75 74 20 74 68 65 20 6d 75 6c 74 69 |ry out the multi| 00001a80 70 6c 69 63 61 74 69 6f 6e 2c 20 61 6e 64 20 63 |plication, and c| 00001a90 6f 6e 76 65 72 74 20 62 61 63 6b 20 61 66 74 65 |onvert back afte| 00001aa0 72 77 61 72 64 73 20 69 66 0d 6e 65 65 64 65 64 |rwards if.needed| 00001ab0 2e 20 20 54 68 65 6e 20 79 6f 75 20 63 6f 75 6c |. Then you coul| 00001ac0 64 20 6a 75 73 74 20 63 68 65 63 6b 20 74 6f 20 |d just check to | 00001ad0 73 65 65 20 69 66 20 61 6e 79 74 68 69 6e 67 20 |see if anything | 00001ae0 77 61 73 0d 6c 65 66 74 20 69 6e 20 70 70 77 73 |was.left in ppws| 00001af0 20 61 66 74 65 72 20 74 68 65 20 6d 75 6c 74 69 | after the multi| 00001b00 70 6c 69 63 61 74 69 6f 6e 2e 20 20 41 6e 79 74 |plication. Anyt| 00001b10 68 69 6e 67 20 74 68 65 72 65 20 77 6f 75 6c 64 |hing there would| 00001b20 0d 69 6e 64 69 63 61 74 65 20 61 6e 20 6f 76 65 |.indicate an ove| 00001b30 72 66 6c 6f 77 20 61 6e 64 20 68 65 6e 63 65 20 |rflow and hence | 00001b40 61 6e 20 65 72 72 6f 72 2e 20 20 41 6c 74 68 6f |an error. Altho| 00001b50 75 67 68 20 77 65 20 64 69 64 6e 27 74 0d 65 72 |ugh we didn't.er| 00001b60 72 6f 72 20 74 72 61 70 20 74 68 65 20 61 64 64 |ror trap the add| 00001b70 69 74 69 6f 6e 20 61 6e 64 20 73 75 62 74 72 61 |ition and subtra| 00001b80 63 74 69 6f 6e 20 69 6e 20 6d 6f 64 75 6c 65 20 |ction in module | 00001b90 32 20 69 74 20 63 6f 75 6c 64 0d 68 61 76 65 20 |2 it could.have | 00001ba0 65 61 73 69 6c 79 20 62 65 65 6e 20 64 6f 6e 65 |easily been done| 00001bb0 20 62 79 20 62 72 61 6e 63 68 69 6e 67 20 74 6f | by branching to| 00001bc0 20 74 68 65 20 65 72 72 6f 72 20 63 6f 64 65 0d | the error code.| 00001bd0 77 68 65 6e 65 76 65 72 20 74 68 65 20 6f 76 65 |whenever the ove| 00001be0 72 66 6c 6f 77 20 66 6c 61 67 20 77 61 73 20 73 |rflow flag was s| 00001bf0 65 74 20 61 66 74 65 72 20 61 64 64 69 6e 67 20 |et after adding | 00001c00 6f 72 0d 73 75 62 74 72 61 63 74 69 6e 67 20 74 |or.subtracting t| 00001c10 68 65 20 68 69 67 68 65 73 74 20 62 79 74 65 2e |he highest byte.| 00001c20 0d 0d 54 68 65 20 69 6e 70 75 74 20 72 6f 75 74 |..The input rout| 00001c30 69 6e 65 20 69 6e 20 74 68 65 20 6c 61 73 74 20 |ine in the last | 00001c40 6d 6f 64 75 6c 65 20 63 61 6e 20 62 65 20 6d 6f |module can be mo| 00001c50 64 69 66 69 65 64 20 74 6f 0d 61 6c 77 61 79 73 |dified to.always| 00001c60 20 67 69 76 65 20 61 20 70 6f 73 69 74 69 76 65 | give a positive| 00001c70 20 72 65 73 75 6c 74 20 61 6e 64 20 61 6e 20 69 | result and an i| 00001c80 6e 64 69 63 61 74 69 6f 6e 20 6f 66 20 73 69 67 |ndication of sig| 00001c90 6e 2e 0d 49 20 61 6d 20 6e 6f 74 20 67 6f 69 6e |n..I am not goin| 00001ca0 67 20 74 6f 20 75 73 65 20 74 68 61 74 20 69 6e |g to use that in| 00001cb0 70 75 74 20 6d 6f 64 75 6c 65 20 68 65 72 65 20 |put module here | 00001cc0 62 65 63 61 75 73 65 20 61 6c 6c 20 74 68 65 0d |because all the.| 00001cd0 73 75 70 65 72 66 6c 75 6f 75 73 20 63 6f 64 65 |superfluous code| 00001ce0 20 69 73 20 6c 69 6b 65 6c 79 20 74 6f 20 63 6c | is likely to cl| 00001cf0 6f 75 64 20 74 68 65 20 6d 61 69 6e 20 69 73 73 |oud the main iss| 00001d00 75 65 2c 20 77 68 69 63 68 20 69 73 0d 74 68 65 |ue, which is.the| 00001d10 20 6d 75 6c 74 69 70 6c 69 63 61 74 69 6f 6e 2e | multiplication.| 00001d20 20 20 49 20 6c 65 61 76 65 20 69 74 20 74 6f 20 | I leave it to | 00001d30 79 6f 75 20 74 6f 20 62 6f 6c 74 20 74 68 65 20 |you to bolt the | 00001d40 72 6f 75 74 69 6e 65 73 0d 74 6f 67 65 74 68 65 |routines.togethe| 00001d50 72 2e 20 20 53 6f 20 49 20 75 73 65 20 64 65 61 |r. So I use dea| 00001d60 72 20 6f 6c 64 20 42 41 53 49 43 20 69 6e 64 69 |r old BASIC indi| 00001d70 72 65 63 74 69 6f 6e 20 6f 70 65 72 61 74 6f 72 |rection operator| 00001d80 73 20 74 6f 0d 70 75 74 20 74 68 65 20 6e 75 6d |s to.put the num| 00001d90 62 65 72 73 20 74 6f 20 62 65 20 6d 75 6c 74 69 |bers to be multi| 00001da0 70 6c 69 65 64 20 69 6e 74 6f 20 74 68 65 20 77 |plied into the w| 00001db0 6f 72 6b 73 70 61 63 65 20 61 6e 64 20 74 6f 0d |orkspace and to.| 00001dc0 72 65 61 64 20 74 68 65 20 72 65 73 75 6c 74 20 |read the result | 00001dd0 6f 75 74 20 61 66 74 65 72 77 61 72 64 73 2e 0d |out afterwards..| 00001de0 0d 54 68 65 20 6d 75 6c 74 69 70 6c 69 63 61 6e |.The multiplican| 00001df0 64 20 67 6f 65 73 20 69 6e 74 6f 20 27 6d 75 6c |d goes into 'mul| 00001e00 74 69 70 6c 69 63 61 6e 64 27 20 61 6e 64 20 74 |tiplicand' and t| 00001e10 68 65 20 6d 75 6c 74 69 70 6c 69 65 72 0d 67 6f |he multiplier.go| 00001e20 65 73 20 69 6e 74 6f 20 27 6d 75 6c 74 69 70 6c |es into 'multipl| 00001e30 69 65 72 27 2e 20 20 27 70 70 77 73 27 20 69 73 |ier'. 'ppws' is| 00001e40 20 74 68 65 20 70 61 72 74 69 61 6c 20 70 72 6f | the partial pro| 00001e50 64 75 63 74 0d 77 6f 72 6b 73 70 61 63 65 2e 20 |duct.workspace. | 00001e60 20 54 68 69 73 20 61 72 72 61 6e 67 65 6d 65 6e | This arrangemen| 00001e70 74 20 66 69 74 73 20 6e 69 63 65 6c 79 20 77 69 |t fits nicely wi| 00001e80 74 68 20 74 68 65 0d 72 65 71 75 69 72 65 6d 65 |th the.requireme| 00001e90 6e 74 20 66 6f 72 20 70 70 77 73 20 61 6e 64 20 |nt for ppws and | 00001ea0 6d 75 6c 74 69 70 6c 69 65 72 20 74 6f 20 62 65 |multiplier to be| 00001eb0 20 74 6f 67 65 74 68 65 72 2e 20 20 5b 49 6e 0d | together. [In.| 00001ec0 66 61 63 74 20 74 68 65 20 6d 65 6d 6f 72 79 20 |fact the memory | 00001ed0 75 73 65 64 20 66 6f 72 20 6d 75 6c 74 69 2d 62 |used for multi-b| 00001ee0 79 74 65 20 6d 61 74 68 73 20 64 6f 65 73 20 6e |yte maths does n| 00001ef0 6f 74 20 6e 65 65 64 20 74 6f 0d 62 65 20 63 6f |ot need to.be co| 00001f00 6e 74 69 67 75 6f 75 73 2c 20 69 6e 20 61 20 62 |ntiguous, in a b| 00001f10 6c 6f 63 6b 2c 20 62 75 74 20 69 74 20 69 73 20 |lock, but it is | 00001f20 73 65 6e 73 69 62 6c 65 20 74 6f 20 68 61 76 65 |sensible to have| 00001f30 20 69 74 0d 73 6f 2e 5d 0d 0d 41 20 66 75 72 74 | it.so.]..A furt| 00001f40 68 65 72 20 6e 6f 74 65 20 6f 6e 20 73 70 65 65 |her note on spee| 00001f50 64 2e 20 20 54 68 65 20 36 35 30 32 20 77 6f 72 |d. The 6502 wor| 00001f60 6b 73 20 66 61 73 74 65 72 20 77 68 65 6e 20 69 |ks faster when i| 00001f70 74 20 69 73 0d 75 73 69 6e 67 20 7a 65 72 6f 20 |t is.using zero | 00001f80 70 61 67 65 20 77 6f 72 6b 73 70 61 63 65 2c 20 |page workspace, | 00001f90 73 6f 20 77 65 20 73 68 6f 75 6c 64 20 72 65 61 |so we should rea| 00001fa0 6c 6c 79 20 75 73 65 20 73 6f 6d 65 20 6f 66 0d |lly use some of.| 00001fb0 74 68 69 73 20 66 6f 72 20 6f 75 72 20 72 6f 75 |this for our rou| 00001fc0 74 69 6e 65 73 2e 20 20 49 20 61 6d 20 6e 6f 74 |tines. I am not| 00001fd0 20 67 6f 69 6e 67 20 74 6f 20 69 6e 20 74 68 69 | going to in thi| 00001fe0 73 20 65 78 61 6d 70 6c 65 0d 62 65 63 61 75 73 |s example.becaus| 00001ff0 65 20 69 74 20 6b 65 65 70 73 20 61 20 63 6f 6e |e it keeps a con| 00002000 73 69 73 74 65 6e 63 79 20 77 69 74 68 20 65 61 |sistency with ea| 00002010 72 6c 69 65 72 20 6d 6f 64 75 6c 65 73 20 61 6e |rlier modules an| 00002020 64 20 49 0d 6c 65 61 76 65 20 69 74 20 74 6f 20 |d I.leave it to | 00002030 79 6f 75 20 74 6f 20 6d 61 6b 65 20 74 68 65 20 |you to make the | 00002040 61 64 6a 75 73 74 6d 65 6e 74 20 69 66 20 79 6f |adjustment if yo| 00002050 75 20 77 61 6e 74 20 74 6f 2e 20 20 49 74 0d 64 |u want to. It.d| 00002060 6f 65 73 6e 27 74 20 61 66 66 65 63 74 20 74 68 |oesn't affect th| 00002070 65 20 61 6c 67 6f 72 69 74 68 6d 20 61 74 20 61 |e algorithm at a| 00002080 6c 6c 2e 0d 0d 46 69 72 73 74 6c 79 20 74 68 65 |ll...Firstly the| 00002090 20 77 6f 72 6b 73 70 61 63 65 20 69 73 20 63 6c | workspace is cl| 000020a0 65 61 72 65 64 20 61 6e 64 20 74 68 65 6e 20 61 |eared and then a| 000020b0 20 63 6f 75 6e 74 65 72 20 69 73 0d 69 6e 69 74 | counter is.init| 000020c0 69 61 6c 69 73 65 64 20 74 6f 20 74 68 65 20 6e |ialised to the n| 000020d0 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e |umber of bits in| 000020e0 20 74 68 65 20 6e 75 6d 62 65 72 73 2e 20 20 53 | the numbers. S| 000020f0 69 6e 63 65 0d 74 68 69 73 20 72 6f 75 74 69 6e |ince.this routin| 00002100 65 20 77 69 6c 6c 20 63 6f 70 65 20 77 69 74 68 |e will cope with| 00002110 20 6e 65 67 61 74 69 76 65 20 6e 75 6d 62 65 72 | negative number| 00002120 73 20 61 73 20 65 61 73 69 6c 79 20 61 73 0d 70 |s as easily as.p| 00002130 6f 73 69 74 69 76 65 20 6f 6e 65 73 20 28 32 27 |ositive ones (2'| 00002140 73 20 63 6f 6d 70 6c 65 6d 65 6e 74 20 6e 65 67 |s complement neg| 00002150 61 74 69 76 65 20 74 68 61 74 20 69 73 29 20 77 |ative that is) w| 00002160 65 20 77 69 6c 6c 20 6e 65 65 64 0d 61 6c 6c 20 |e will need.all | 00002170 33 32 20 62 69 74 73 2e 20 20 2d 31 20 69 73 20 |32 bits. -1 is | 00002180 26 46 46 46 46 46 46 46 46 20 28 49 20 77 69 6c |&FFFFFFFF (I wil| 00002190 6c 20 72 65 66 72 61 69 6e 20 66 72 6f 6d 20 70 |l refrain from p| 000021a0 72 69 6e 74 69 6e 67 0d 6f 75 74 20 33 32 20 27 |rinting.out 32 '| 000021b0 31 27 73 20 6a 75 73 74 20 74 6f 20 69 6c 6c 75 |1's just to illu| 000021c0 73 74 72 61 74 65 20 74 68 69 73 20 70 6f 69 6e |strate this poin| 000021d0 74 2e 29 0d 0d 54 68 65 20 66 69 72 73 74 20 74 |t.)..The first t| 000021e0 68 69 6e 67 20 74 68 61 74 20 68 61 70 70 65 6e |hing that happen| 000021f0 73 20 69 6e 20 74 68 65 20 63 6f 64 65 20 69 73 |s in the code is| 00002200 20 74 68 61 74 20 77 65 20 63 6c 65 61 72 0d 6f | that we clear.o| 00002210 75 72 20 70 61 72 74 69 61 6c 20 70 72 6f 64 75 |ur partial produ| 00002220 63 74 20 77 6f 72 6b 73 70 61 63 65 20 61 6e 64 |ct workspace and| 00002230 20 73 65 74 20 74 68 65 20 62 69 74 20 63 6f 75 | set the bit cou| 00002240 6e 74 65 72 20 74 6f 20 33 32 0d 28 6f 72 20 68 |nter to 32.(or h| 00002250 6f 77 65 76 65 72 20 6d 61 6e 79 20 62 69 74 73 |owever many bits| 00002260 20 79 6f 75 20 61 72 65 20 77 6f 72 6b 69 6e 67 | you are working| 00002270 20 77 69 74 68 29 2e 20 20 54 6f 20 67 65 74 20 | with). To get | 00002280 6f 75 72 0d 61 6c 67 6f 72 69 74 68 6d 20 72 65 |our.algorithm re| 00002290 61 64 79 20 77 65 20 68 61 76 65 20 74 6f 20 66 |ady we have to f| 000022a0 69 72 73 74 20 72 6f 74 61 74 65 20 6f 72 20 73 |irst rotate or s| 000022b0 68 69 66 74 20 74 68 65 0d 6d 75 6c 74 69 70 6c |hift the.multipl| 000022c0 69 65 72 20 72 69 67 68 74 20 74 6f 20 70 75 74 |ier right to put| 000022d0 20 69 74 73 20 6c 65 61 73 74 20 73 69 67 6e 69 | its least signi| 000022e0 66 69 63 61 6e 74 20 62 69 74 20 28 6c 73 62 29 |ficant bit (lsb)| 000022f0 20 69 6e 74 6f 0d 74 68 65 20 63 61 72 72 79 20 | into.the carry | 00002300 66 6c 61 67 2e 20 20 57 65 20 63 61 6e 20 74 68 |flag. We can th| 00002310 65 6e 20 75 73 65 20 62 72 61 6e 63 68 65 73 20 |en use branches | 00002320 6f 6e 20 63 61 72 72 79 20 74 6f 20 64 65 63 69 |on carry to deci| 00002330 64 65 0d 77 68 65 74 68 65 72 20 6f 72 20 6e 6f |de.whether or no| 00002340 74 20 74 6f 20 61 64 64 20 74 68 65 20 6d 75 6c |t to add the mul| 00002350 74 69 70 6c 69 63 61 6e 64 20 6f 6e 74 6f 20 74 |tiplicand onto t| 00002360 68 65 20 63 6f 6e 74 65 6e 74 73 20 6f 66 0d 74 |he contents of.t| 00002370 68 65 20 70 61 72 74 69 61 6c 20 70 72 6f 64 75 |he partial produ| 00002380 63 74 20 77 6f 72 6b 73 70 61 63 65 2e 0d 0d 27 |ct workspace...'| 00002390 6d 62 6d 5f 6c 6f 6f 70 27 20 28 66 6f 72 20 6d |mbm_loop' (for m| 000023a0 75 6c 74 69 2d 62 79 74 65 20 6d 75 6c 74 69 70 |ulti-byte multip| 000023b0 6c 69 63 61 74 69 6f 6e 29 20 69 73 20 74 68 65 |lication) is the| 000023c0 20 74 6f 70 20 6f 66 20 74 68 65 0d 6d 61 69 6e | top of the.main| 000023d0 20 6c 6f 6f 70 2e 20 20 49 6e 20 69 74 20 77 65 | loop. In it we| 000023e0 20 66 69 72 73 74 20 63 68 65 63 6b 20 74 68 65 | first check the| 000023f0 20 63 61 72 72 79 20 66 6c 61 67 20 74 6f 20 73 | carry flag to s| 00002400 65 65 20 69 66 0d 74 68 65 20 6c 73 62 20 6f 66 |ee if.the lsb of| 00002410 20 74 68 65 20 6d 75 6c 74 69 70 6c 69 65 72 20 | the multiplier | 00002420 77 61 73 20 73 65 74 2e 20 20 49 66 20 69 74 20 |was set. If it | 00002430 77 61 73 20 74 68 65 6e 20 77 65 20 77 69 6c 6c |was then we will| 00002440 0d 61 64 64 20 74 68 65 20 6d 75 6c 74 69 70 6c |.add the multipl| 00002450 69 63 61 6e 64 20 6f 6e 74 6f 20 74 68 65 20 70 |icand onto the p| 00002460 70 77 73 20 62 75 74 20 69 66 20 6e 6f 74 20 74 |pws but if not t| 00002470 68 65 20 70 72 6f 67 72 61 6d 0d 67 6f 65 73 20 |he program.goes | 00002480 74 6f 20 27 6e 6f 5f 61 64 64 5f 6d 62 6d 27 20 |to 'no_add_mbm' | 00002490 77 68 65 72 65 20 62 6f 74 68 20 74 68 65 20 70 |where both the p| 000024a0 70 77 73 20 61 6e 64 20 74 68 65 20 6d 75 6c 74 |pws and the mult| 000024b0 69 70 6c 69 65 72 0d 61 72 65 20 72 6f 74 61 74 |iplier.are rotat| 000024c0 65 64 20 72 69 67 68 74 2e 20 20 28 57 68 65 72 |ed right. (Wher| 000024d0 65 20 49 20 72 65 66 65 72 20 74 6f 20 27 77 73 |e I refer to 'ws| 000024e0 5f 73 6f 6d 65 74 68 69 6e 67 27 20 49 20 6d 65 |_something' I me| 000024f0 61 6e 0d 74 68 65 20 67 72 6f 75 70 20 6f 66 20 |an.the group of | 00002500 62 79 74 65 73 20 74 68 61 74 20 6d 61 6b 65 20 |bytes that make | 00002510 75 70 20 74 68 61 74 20 77 6f 72 64 2c 20 69 6e |up that word, in| 00002520 20 74 68 69 73 20 63 61 73 65 0d 27 6d 75 6c 74 | this case.'mult| 00002530 69 70 6c 69 63 61 6e 64 27 20 74 6f 20 27 6d 75 |iplicand' to 'mu| 00002540 6c 74 69 70 6c 69 63 61 6e 64 2b 33 27 2e 29 20 |ltiplicand+3'.) | 00002550 20 54 68 69 73 20 72 6f 74 61 74 69 6f 6e 20 70 | This rotation p| 00002560 75 74 73 20 74 68 65 0d 6c 73 62 20 6f 66 20 74 |uts the.lsb of t| 00002570 68 65 20 6d 75 6c 74 69 70 6c 69 65 72 20 69 6e |he multiplier in| 00002580 74 6f 20 74 68 65 20 63 61 72 72 79 20 66 6c 61 |to the carry fla| 00002590 67 20 72 65 61 64 79 20 66 6f 72 20 61 6e 6f 74 |g ready for anot| 000025a0 68 65 72 0d 72 75 6e 20 61 72 6f 75 6e 64 20 74 |her.run around t| 000025b0 68 65 20 6c 6f 6f 70 2e 0d 0d 52 65 6d 65 6d 62 |he loop...Rememb| 000025c0 65 72 20 77 65 20 72 6f 74 61 74 65 20 74 68 65 |er we rotate the| 000025d0 20 70 70 77 73 20 61 6e 64 20 6d 75 6c 74 69 70 | ppws and multip| 000025e0 6c 69 65 72 20 65 61 63 68 20 74 69 6d 65 20 77 |lier each time w| 000025f0 65 20 67 6f 0d 61 72 6f 75 6e 64 20 74 68 65 20 |e go.around the | 00002600 6c 6f 6f 70 20 77 68 65 74 68 65 72 20 6f 72 20 |loop whether or | 00002610 6e 6f 74 20 77 65 20 61 64 64 20 74 68 65 20 6d |not we add the m| 00002620 75 6c 74 69 70 6c 69 63 61 6e 64 20 74 6f 0d 74 |ultiplicand to.t| 00002630 68 65 20 70 61 72 74 69 61 6c 20 70 72 6f 64 75 |he partial produ| 00002640 63 74 2e 20 20 46 6f 6c 6c 6f 77 69 6e 67 20 74 |ct. Following t| 00002650 68 65 20 72 6f 74 61 74 69 6f 6e 20 74 68 65 20 |he rotation the | 00002660 58 20 72 65 67 69 73 74 65 72 2c 0d 77 68 69 63 |X register,.whic| 00002670 68 20 69 73 20 63 6f 75 6e 74 69 6e 67 20 74 68 |h is counting th| 00002680 65 20 6c 6f 6f 70 20 66 6f 72 20 75 73 2c 20 69 |e loop for us, i| 00002690 73 20 72 65 64 75 63 65 64 20 62 79 20 6f 6e 65 |s reduced by one| 000026a0 2e 20 0d 43 6f 75 6e 74 69 6e 67 20 64 6f 77 6e |. .Counting down| 000026b0 20 69 73 20 75 73 75 61 6c 6c 79 20 62 65 74 74 | is usually bett| 000026c0 65 72 20 74 68 61 6e 20 63 6f 75 6e 74 69 6e 67 |er than counting| 000026d0 20 75 70 20 62 65 63 61 75 73 65 20 61 0d 73 69 | up because a.si| 000026e0 6d 70 6c 65 20 42 4e 45 20 77 69 6c 6c 20 73 75 |mple BNE will su| 000026f0 66 66 69 63 65 20 74 6f 20 74 72 61 70 20 7a 65 |ffice to trap ze| 00002700 72 6f 20 72 61 74 68 65 72 20 74 68 61 6e 20 68 |ro rather than h| 00002710 61 76 69 6e 67 20 74 6f 0d 43 4d 50 20 77 69 74 |aving to.CMP wit| 00002720 68 20 61 6e 79 74 68 69 6e 67 2e 20 20 48 65 72 |h anything. Her| 00002730 65 20 77 65 20 42 4e 45 20 62 61 63 6b 20 74 6f |e we BNE back to| 00002740 20 27 6d 62 6d 5f 6c 6f 6f 70 27 2e 0d 0d 57 68 | 'mbm_loop'...Wh| 00002750 65 6e 20 77 65 20 66 69 6e 61 6c 6c 79 20 66 61 |en we finally fa| 00002760 6c 6c 20 74 68 72 6f 75 67 68 20 74 68 65 20 42 |ll through the B| 00002770 4e 45 20 77 65 20 72 65 61 63 68 20 61 6e 20 52 |NE we reach an R| 00002780 54 53 20 77 68 69 63 68 0d 66 69 6e 69 73 68 65 |TS which.finishe| 00002790 73 20 74 68 65 20 72 6f 75 74 69 6e 65 2e 20 20 |s the routine. | 000027a0 54 68 65 20 66 6f 75 72 20 62 79 74 65 20 72 65 |The four byte re| 000027b0 73 75 6c 74 20 69 73 20 69 6e 0d 27 6d 75 6c 74 |sult is in.'mult| 000027c0 69 70 6c 69 65 72 27 20 77 69 74 68 20 61 6e 79 |iplier' with any| 000027d0 20 6f 76 65 72 66 6c 6f 77 20 69 6e 20 27 70 70 | overflow in 'pp| 000027e0 77 73 27 2e 20 20 54 68 65 6e 20 66 6f 6c 6c 6f |ws'. Then follo| 000027f0 77 20 74 68 65 0d 74 68 72 65 65 20 46 4e 45 51 |w the.three FNEQ| 00002800 55 4d 20 66 75 6e 63 74 69 6f 6e 73 20 74 68 61 |UM functions tha| 00002810 74 20 72 65 73 65 72 76 65 20 6d 65 6d 6f 72 79 |t reserve memory| 00002820 20 66 6f 72 20 74 68 65 0d 77 6f 72 6b 73 70 61 | for the.workspa| 00002830 63 65 2e 20 20 49 66 20 79 6f 75 20 68 61 76 65 |ce. If you have| 00002840 20 42 41 53 49 43 20 32 20 6f 72 20 6c 61 74 65 | BASIC 2 or late| 00002850 72 20 79 6f 75 20 63 61 6e 20 72 65 70 6c 61 63 |r you can replac| 00002860 65 0d 74 68 65 6d 20 77 69 74 68 20 45 51 55 44 |e.them with EQUD| 00002870 20 30 20 69 6e 20 65 61 63 68 20 63 61 73 65 2e | 0 in each case.| 00002880 0d 0d 54 68 65 20 42 41 53 49 43 20 61 74 20 74 |..The BASIC at t| 00002890 68 65 20 65 6e 64 20 70 72 69 6e 74 73 20 6f 75 |he end prints ou| 000028a0 74 20 74 68 65 20 72 65 73 75 6c 74 20 77 69 74 |t the result wit| 000028b0 68 20 61 20 63 68 65 63 6b 20 61 6e 64 0d 74 65 |h a check and.te| 000028c0 6c 6c 73 20 79 6f 75 20 77 68 61 74 20 65 78 61 |lls you what exa| 000028d0 63 74 6c 79 20 69 73 20 69 6e 20 27 70 70 77 73 |ctly is in 'ppws| 000028e0 27 20 61 6e 64 20 27 6d 75 6c 74 69 70 6c 69 65 |' and 'multiplie| 000028f0 72 27 20 73 6f 20 79 6f 75 0d 63 61 6e 20 73 65 |r' so you.can se| 00002900 65 20 77 68 61 74 20 68 61 70 70 65 6e 73 20 69 |e what happens i| 00002910 66 20 79 6f 75 20 65 6e 74 65 72 20 6c 61 72 67 |f you enter larg| 00002920 65 20 6e 75 6d 62 65 72 73 2e 20 20 48 6f 77 65 |e numbers. Howe| 00002930 76 65 72 2c 0d 66 6f 72 20 61 20 70 72 6f 64 75 |ver,.for a produ| 00002940 63 74 20 75 6e 64 65 72 20 33 32 20 62 79 74 65 |ct under 32 byte| 00002950 73 20 74 68 65 20 72 65 73 75 6c 74 73 20 77 69 |s the results wi| 00002960 6c 6c 20 62 65 20 63 6f 72 72 65 63 74 20 66 6f |ll be correct fo| 00002970 72 0d 70 6f 73 69 74 69 76 65 20 61 6e 64 20 6e |r.positive and n| 00002980 65 67 61 74 69 76 65 2e 0d 0d 4d 75 6c 74 69 70 |egative...Multip| 00002990 6c 69 63 61 74 69 6f 6e 20 61 6e 64 20 64 69 76 |lication and div| 000029a0 69 73 69 6f 6e 20 72 6f 75 74 69 6e 65 73 20 61 |ision routines a| 000029b0 72 65 20 61 6d 6f 6e 67 73 74 20 74 68 65 20 6d |re amongst the m| 000029c0 6f 73 74 0d 74 69 6d 65 20 73 65 6e 73 69 74 69 |ost.time sensiti| 000029d0 76 65 20 69 6e 20 6d 61 74 68 73 2e 20 20 49 6e |ve in maths. In| 000029e0 20 61 6e 20 65 61 72 6c 79 20 6d 6f 64 75 6c 65 | an early module| 000029f0 20 77 68 65 6e 20 49 20 73 61 69 64 0d 74 68 61 | when I said.tha| 00002a00 74 20 79 6f 75 20 6d 69 67 68 74 20 77 69 73 68 |t you might wish| 00002a10 20 74 6f 20 64 6f 20 6d 6f 72 65 20 74 68 61 6e | to do more than| 00002a20 20 6a 75 73 74 20 6d 75 6c 74 69 70 6c 79 20 66 | just multiply f| 00002a30 61 73 74 65 72 20 49 0d 77 61 73 20 69 6e 20 66 |aster I.was in f| 00002a40 61 63 74 20 68 69 64 69 6e 67 20 74 68 65 20 74 |act hiding the t| 00002a50 72 75 74 68 2e 20 20 54 68 65 20 72 6f 75 74 69 |ruth. The routi| 00002a60 6e 65 73 20 69 6e 20 42 42 43 20 42 41 53 49 43 |nes in BBC BASIC| 00002a70 20 61 72 65 0d 73 6f 20 65 66 66 69 63 69 65 6e | are.so efficien| 00002a80 74 20 74 68 61 74 20 79 6f 75 20 63 61 6e 20 6d |t that you can m| 00002a90 75 6c 74 69 70 6c 79 20 74 77 6f 20 69 6e 74 65 |ultiply two inte| 00002aa0 67 65 72 73 20 74 6f 67 65 74 68 65 72 0d 66 61 |gers together.fa| 00002ab0 73 74 65 72 20 66 72 6f 6d 20 68 69 73 20 42 41 |ster from his BA| 00002ac0 53 49 43 20 74 68 61 6e 20 77 69 74 68 20 74 68 |SIC than with th| 00002ad0 69 73 20 63 6f 64 65 20 68 65 72 65 2e 20 20 48 |is code here. H| 00002ae0 6f 77 65 76 65 72 20 49 0d 61 6d 20 61 69 6d 69 |owever I.am aimi| 00002af0 6e 67 20 66 6f 72 20 63 6c 61 72 69 74 79 20 28 |ng for clarity (| 00002b00 62 75 69 6c 74 20 66 6f 72 20 63 6f 6d 66 6f 72 |built for comfor| 00002b10 74 20 6e 6f 74 20 66 6f 72 20 73 70 65 65 64 20 |t not for speed | 00002b20 49 0d 62 65 6c 69 65 76 65 29 20 77 68 69 63 68 |I.believe) which| 00002b30 20 69 73 20 6d 79 20 65 78 63 75 73 65 20 61 6e | is my excuse an| 00002b40 64 20 49 20 77 69 6c 6c 20 73 74 69 63 6b 20 74 |d I will stick t| 00002b50 6f 20 69 74 2e 0d 0d 49 66 20 79 6f 75 20 77 69 |o it...If you wi| 00002b60 73 68 20 74 6f 20 65 78 70 61 6e 64 20 28 6f 72 |sh to expand (or| 00002b70 20 63 6f 6e 74 72 61 63 74 29 20 74 68 69 73 20 | contract) this | 00002b80 72 6f 75 74 69 6e 65 20 74 6f 20 77 6f 72 6b 0d |routine to work.| 00002b90 77 69 74 68 20 61 20 64 69 66 66 65 72 65 6e 74 |with a different| 00002ba0 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 | number of bytes| 00002bb0 20 79 6f 75 20 73 69 6d 70 6c 79 20 63 68 61 6e | you simply chan| 00002bc0 67 65 20 74 68 65 20 73 69 7a 65 0d 6f 66 20 74 |ge the size.of t| 00002bd0 68 65 20 77 6f 72 6b 73 70 61 63 65 20 61 72 65 |he workspace are| 00002be0 61 73 20 61 63 63 6f 72 64 69 6e 67 6c 79 20 61 |as accordingly a| 00002bf0 6e 64 20 61 64 64 20 6f 72 20 73 75 62 74 72 61 |nd add or subtra| 00002c00 63 74 20 66 72 6f 6d 0d 74 68 65 20 6c 69 73 74 |ct from.the list| 00002c10 73 20 6f 66 20 4c 44 41 2f 41 44 43 2f 53 54 41 |s of LDA/ADC/STA| 00002c20 73 20 61 6e 64 20 4c 53 52 2f 52 4f 52 73 2e 20 |s and LSR/RORs. | 00002c30 20 52 65 6d 65 6d 62 65 72 20 74 68 61 74 20 62 | Remember that b| 00002c40 79 0d 63 6f 6e 76 65 6e 74 69 6f 6e 20 77 69 74 |y.convention wit| 00002c50 68 20 74 68 65 20 36 35 30 32 20 61 20 6d 75 6c |h the 6502 a mul| 00002c60 74 69 2d 62 79 74 65 20 6e 75 6d 62 65 72 20 69 |ti-byte number i| 00002c70 73 20 73 74 6f 72 65 64 20 77 69 74 68 0d 69 74 |s stored with.it| 00002c80 73 20 6c 6f 77 65 73 74 20 73 69 67 6e 69 66 69 |s lowest signifi| 00002c90 63 61 6e 74 20 62 79 74 65 20 69 6e 20 74 68 65 |cant byte in the| 00002ca0 20 6c 6f 77 65 73 74 20 6d 65 6d 6f 72 79 20 6c | lowest memory l| 00002cb0 6f 63 61 74 69 6f 6e 0d 61 6e 64 20 74 68 65 20 |ocation.and the | 00002cc0 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61 6e 74 |most significant| 00002cd0 20 62 79 74 65 20 69 6e 20 74 68 65 20 68 69 67 | byte in the hig| 00002ce0 68 65 73 74 20 6c 6f 63 61 74 69 6f 6e 2e 20 20 |hest location. | 00002cf0 54 68 69 73 0d 72 65 73 75 6c 74 73 20 66 72 6f |This.results fro| 00002d00 6d 20 74 68 65 20 77 61 79 20 61 20 31 36 20 62 |m the way a 16 b| 00002d10 69 74 20 61 64 64 72 65 73 73 20 6d 75 73 74 20 |it address must | 00002d20 62 65 20 73 74 6f 72 65 64 20 77 69 74 68 0d 74 |be stored with.t| 00002d30 68 65 20 6c 65 73 73 20 73 69 67 6e 69 66 69 63 |he less signific| 00002d40 61 6e 74 20 62 79 74 65 20 66 69 72 73 74 2e 0d |ant byte first..| 00002d50 0d 4e 65 78 74 20 74 69 6d 65 20 77 65 20 6d 6f |.Next time we mo| 00002d60 76 65 20 6f 6e 20 74 6f 20 64 69 76 69 73 69 6f |ve on to divisio| 00002d70 6e 20 61 6e 64 20 61 6e 20 6f 75 74 70 75 74 20 |n and an output | 00002d80 72 6f 75 74 69 6e 65 20 77 68 69 63 68 0d 6e 65 |routine which.ne| 00002d90 65 64 73 20 64 69 76 69 73 69 6f 6e 20 74 6f 20 |eds division to | 00002da0 6f 70 65 72 61 74 65 2e 20 20 54 68 65 6e 20 6f |operate. Then o| 00002db0 6e 20 74 6f 20 61 20 67 65 6e 65 72 61 6c 20 64 |n to a general d| 00002dc0 69 76 69 73 69 6f 6e 0d 72 6f 75 74 69 6e 65 20 |ivision.routine | 00002dd0 73 69 6d 69 6c 61 72 20 74 6f 20 74 68 65 20 6d |similar to the m| 00002de0 75 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 6f 6e |ultiplication on| 00002df0 65 20 69 6e 20 74 68 69 73 20 6d 6f 64 75 6c 65 |e in this module| 00002e00 2e 0d |..| 00002e02
17-02-88/T\OSB13.m0
17-02-88/T\OSB13.m1
17-02-88/T\OSB13.m2
17-02-88/T\OSB13.m4
17-02-88/T\OSB13.m5
.