Home » CEEFAX disks » telesoftware2.adl » OS\BITS/T\OSB15
OS\BITS/T\OSB15
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 » telesoftware2.adl |
| Filename: | OS\BITS/T\OSB15 |
| Read OK: | ✔ |
| File size: | 0A32 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
Duplicates
There is 1 duplicate copy of this file in the archive:
- CEEFAX disks » telesoftware2.adl » OS\BITS/T\OSB15
- CEEFAX disks » telesoftware5.adl » 26-02-88/T\OSB15
File contents
OSBITS - An Exploration of the BBC Micro at Machine Level
By Programmer
..........................................................
Part 15: Multi-byte Division
This module contains a simple multi-byte division routine
which works almost exactly like the long division example
given last time. The only differences are that this time
the divisor can be 32 bits long. This means that the
accumulator can no longer be used. The dividend and result
(or quotient) have been combined and a full-blown
subtraction into an extra workspace has to be used instead
of a simple CMP with the accumulator.
So we have 'dividend' holding the dividend and 'divisor'
holding the divisor. 'pdws' (partial dividend workspace)
fulfils the role of the accumulator in the last module and
'diff_ws' is used temporarily to hold the result of
subtracting the divisor from the partial dividend.
The algorithm looks like this:
Clear the partial dividend workspace
Loop starts here
Rotate the dividend/result left into partial dividend
Subtract divisor from partial dividend and store
If the result of this is <0 then repeat loop
If the result is >=0 then
Increase dividend/result by one
Transfer result of subtraction into partial dividend
Repeat loop until finished
This algorithm will not work with negative numbers, try it
and see. You would have to covert to positive before
division and adjust the result accordingly. A zero divisor
has been trapped but you could also see what happens when
you allow a zero through. Since zero is always smaller than
the partial dividend the answer always has every bit set, so
-1 is printed out as the result (&FFFFFFFF). If you think
about it there is a kind of perverse logic to this since
this result is the nearest the algorithm can get to
infinity!
If we wanted to continue the division beyond the binary
point we could allocate extra workspace and increase the 32
bit count. In a later module I shall be looking at numbers
with a binary (and decimal) point with fixed and floating
point numbering systems. These basic arithmetic routines
are made easily expandable because we will need them later.
None of the arithmetical routines in these modules have been
ideal. There have been problems with overflow and with
negative numbers, and they have not been particularly fast.
I hope though that they have been clear since arithmetic
manipulation is a major function of many computer programs.
Still, that's enough arithmetic for the moment. Next time
we return to the BBC Micro OS with a look at vectors and
what they can be used for.
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 0d 0d 0d 50 61 72 74 20 31 35 3a 20 |.......Part 15: | 00000090 4d 75 6c 74 69 2d 62 79 74 65 20 44 69 76 69 73 |Multi-byte Divis| 000000a0 69 6f 6e 0d 0d 54 68 69 73 20 6d 6f 64 75 6c 65 |ion..This module| 000000b0 20 63 6f 6e 74 61 69 6e 73 20 61 20 73 69 6d 70 | contains a simp| 000000c0 6c 65 20 6d 75 6c 74 69 2d 62 79 74 65 20 64 69 |le multi-byte di| 000000d0 76 69 73 69 6f 6e 20 72 6f 75 74 69 6e 65 0d 77 |vision routine.w| 000000e0 68 69 63 68 20 77 6f 72 6b 73 20 61 6c 6d 6f 73 |hich works almos| 000000f0 74 20 65 78 61 63 74 6c 79 20 6c 69 6b 65 20 74 |t exactly like t| 00000100 68 65 20 6c 6f 6e 67 20 64 69 76 69 73 69 6f 6e |he long division| 00000110 20 65 78 61 6d 70 6c 65 0d 67 69 76 65 6e 20 6c | example.given l| 00000120 61 73 74 20 74 69 6d 65 2e 20 20 54 68 65 20 6f |ast time. The o| 00000130 6e 6c 79 20 64 69 66 66 65 72 65 6e 63 65 73 20 |nly differences | 00000140 61 72 65 20 74 68 61 74 20 74 68 69 73 20 74 69 |are that this ti| 00000150 6d 65 0d 74 68 65 20 64 69 76 69 73 6f 72 20 63 |me.the divisor c| 00000160 61 6e 20 62 65 20 33 32 20 62 69 74 73 20 6c 6f |an be 32 bits lo| 00000170 6e 67 2e 20 20 54 68 69 73 20 6d 65 61 6e 73 20 |ng. This means | 00000180 74 68 61 74 20 74 68 65 0d 61 63 63 75 6d 75 6c |that the.accumul| 00000190 61 74 6f 72 20 63 61 6e 20 6e 6f 20 6c 6f 6e 67 |ator can no long| 000001a0 65 72 20 62 65 20 75 73 65 64 2e 20 20 54 68 65 |er be used. The| 000001b0 20 64 69 76 69 64 65 6e 64 20 61 6e 64 20 72 65 | dividend and re| 000001c0 73 75 6c 74 0d 28 6f 72 20 71 75 6f 74 69 65 6e |sult.(or quotien| 000001d0 74 29 20 68 61 76 65 20 62 65 65 6e 20 63 6f 6d |t) have been com| 000001e0 62 69 6e 65 64 20 61 6e 64 20 61 20 66 75 6c 6c |bined and a full| 000001f0 2d 62 6c 6f 77 6e 0d 73 75 62 74 72 61 63 74 69 |-blown.subtracti| 00000200 6f 6e 20 69 6e 74 6f 20 61 6e 20 65 78 74 72 61 |on into an extra| 00000210 20 77 6f 72 6b 73 70 61 63 65 20 68 61 73 20 74 | workspace has t| 00000220 6f 20 62 65 20 75 73 65 64 20 69 6e 73 74 65 61 |o be used instea| 00000230 64 0d 6f 66 20 61 20 73 69 6d 70 6c 65 20 43 4d |d.of a simple CM| 00000240 50 20 77 69 74 68 20 74 68 65 20 61 63 63 75 6d |P with the accum| 00000250 75 6c 61 74 6f 72 2e 0d 0d 53 6f 20 77 65 20 68 |ulator...So we h| 00000260 61 76 65 20 27 64 69 76 69 64 65 6e 64 27 20 68 |ave 'dividend' h| 00000270 6f 6c 64 69 6e 67 20 74 68 65 20 64 69 76 69 64 |olding the divid| 00000280 65 6e 64 20 61 6e 64 20 27 64 69 76 69 73 6f 72 |end and 'divisor| 00000290 27 0d 68 6f 6c 64 69 6e 67 20 74 68 65 20 64 69 |'.holding the di| 000002a0 76 69 73 6f 72 2e 20 20 27 70 64 77 73 27 20 28 |visor. 'pdws' (| 000002b0 70 61 72 74 69 61 6c 20 64 69 76 69 64 65 6e 64 |partial dividend| 000002c0 20 77 6f 72 6b 73 70 61 63 65 29 0d 66 75 6c 66 | workspace).fulf| 000002d0 69 6c 73 20 74 68 65 20 72 6f 6c 65 20 6f 66 20 |ils the role of | 000002e0 74 68 65 20 61 63 63 75 6d 75 6c 61 74 6f 72 20 |the accumulator | 000002f0 69 6e 20 74 68 65 20 6c 61 73 74 20 6d 6f 64 75 |in the last modu| 00000300 6c 65 20 61 6e 64 0d 27 64 69 66 66 5f 77 73 27 |le and.'diff_ws'| 00000310 20 69 73 20 75 73 65 64 20 74 65 6d 70 6f 72 61 | is used tempora| 00000320 72 69 6c 79 20 74 6f 20 68 6f 6c 64 20 74 68 65 |rily to hold the| 00000330 20 72 65 73 75 6c 74 20 6f 66 0d 73 75 62 74 72 | result of.subtr| 00000340 61 63 74 69 6e 67 20 74 68 65 20 64 69 76 69 73 |acting the divis| 00000350 6f 72 20 66 72 6f 6d 20 74 68 65 20 70 61 72 74 |or from the part| 00000360 69 61 6c 20 64 69 76 69 64 65 6e 64 2e 0d 0d 54 |ial dividend...T| 00000370 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 6c 6f 6f |he algorithm loo| 00000380 6b 73 20 6c 69 6b 65 20 74 68 69 73 3a 0d 0d 20 |ks like this:.. | 00000390 20 43 6c 65 61 72 20 74 68 65 20 70 61 72 74 69 | Clear the parti| 000003a0 61 6c 20 64 69 76 69 64 65 6e 64 20 77 6f 72 6b |al dividend work| 000003b0 73 70 61 63 65 0d 20 20 4c 6f 6f 70 20 73 74 61 |space. Loop sta| 000003c0 72 74 73 20 68 65 72 65 0d 20 20 20 20 52 6f 74 |rts here. Rot| 000003d0 61 74 65 20 74 68 65 20 64 69 76 69 64 65 6e 64 |ate the dividend| 000003e0 2f 72 65 73 75 6c 74 20 6c 65 66 74 20 69 6e 74 |/result left int| 000003f0 6f 20 70 61 72 74 69 61 6c 20 64 69 76 69 64 65 |o partial divide| 00000400 6e 64 0d 20 20 20 20 53 75 62 74 72 61 63 74 20 |nd. Subtract | 00000410 64 69 76 69 73 6f 72 20 66 72 6f 6d 20 70 61 72 |divisor from par| 00000420 74 69 61 6c 20 64 69 76 69 64 65 6e 64 20 61 6e |tial dividend an| 00000430 64 20 73 74 6f 72 65 0d 20 20 20 20 49 66 20 74 |d store. If t| 00000440 68 65 20 72 65 73 75 6c 74 20 6f 66 20 74 68 69 |he result of thi| 00000450 73 20 69 73 20 3c 30 20 74 68 65 6e 20 72 65 70 |s is <0 then rep| 00000460 65 61 74 20 6c 6f 6f 70 0d 20 20 20 20 49 66 20 |eat loop. If | 00000470 74 68 65 20 72 65 73 75 6c 74 20 69 73 20 3e 3d |the result is >=| 00000480 30 20 74 68 65 6e 0d 20 20 20 20 20 20 49 6e 63 |0 then. Inc| 00000490 72 65 61 73 65 20 64 69 76 69 64 65 6e 64 2f 72 |rease dividend/r| 000004a0 65 73 75 6c 74 20 62 79 20 6f 6e 65 0d 20 20 20 |esult by one. | 000004b0 20 20 20 54 72 61 6e 73 66 65 72 20 72 65 73 75 | Transfer resu| 000004c0 6c 74 20 6f 66 20 73 75 62 74 72 61 63 74 69 6f |lt of subtractio| 000004d0 6e 20 69 6e 74 6f 20 70 61 72 74 69 61 6c 20 64 |n into partial d| 000004e0 69 76 69 64 65 6e 64 0d 20 20 52 65 70 65 61 74 |ividend. Repeat| 000004f0 20 6c 6f 6f 70 20 75 6e 74 69 6c 20 66 69 6e 69 | loop until fini| 00000500 73 68 65 64 0d 0d 54 68 69 73 20 61 6c 67 6f 72 |shed..This algor| 00000510 69 74 68 6d 20 77 69 6c 6c 20 6e 6f 74 20 77 6f |ithm will not wo| 00000520 72 6b 20 77 69 74 68 20 6e 65 67 61 74 69 76 65 |rk with negative| 00000530 20 6e 75 6d 62 65 72 73 2c 20 74 72 79 20 69 74 | numbers, try it| 00000540 0d 61 6e 64 20 73 65 65 2e 20 20 59 6f 75 20 77 |.and see. You w| 00000550 6f 75 6c 64 20 68 61 76 65 20 74 6f 20 63 6f 76 |ould have to cov| 00000560 65 72 74 20 74 6f 20 70 6f 73 69 74 69 76 65 20 |ert to positive | 00000570 62 65 66 6f 72 65 0d 64 69 76 69 73 69 6f 6e 20 |before.division | 00000580 61 6e 64 20 61 64 6a 75 73 74 20 74 68 65 20 72 |and adjust the r| 00000590 65 73 75 6c 74 20 61 63 63 6f 72 64 69 6e 67 6c |esult accordingl| 000005a0 79 2e 20 20 41 20 7a 65 72 6f 20 64 69 76 69 73 |y. A zero divis| 000005b0 6f 72 0d 68 61 73 20 62 65 65 6e 20 74 72 61 70 |or.has been trap| 000005c0 70 65 64 20 62 75 74 20 79 6f 75 20 63 6f 75 6c |ped but you coul| 000005d0 64 20 61 6c 73 6f 20 73 65 65 20 77 68 61 74 20 |d also see what | 000005e0 68 61 70 70 65 6e 73 20 77 68 65 6e 0d 79 6f 75 |happens when.you| 000005f0 20 61 6c 6c 6f 77 20 61 20 7a 65 72 6f 20 74 68 | allow a zero th| 00000600 72 6f 75 67 68 2e 20 20 53 69 6e 63 65 20 7a 65 |rough. Since ze| 00000610 72 6f 20 69 73 20 61 6c 77 61 79 73 20 73 6d 61 |ro is always sma| 00000620 6c 6c 65 72 20 74 68 61 6e 0d 74 68 65 20 70 61 |ller than.the pa| 00000630 72 74 69 61 6c 20 64 69 76 69 64 65 6e 64 20 74 |rtial dividend t| 00000640 68 65 20 61 6e 73 77 65 72 20 61 6c 77 61 79 73 |he answer always| 00000650 20 68 61 73 20 65 76 65 72 79 20 62 69 74 20 73 | has every bit s| 00000660 65 74 2c 20 73 6f 0d 2d 31 20 69 73 20 70 72 69 |et, so.-1 is pri| 00000670 6e 74 65 64 20 6f 75 74 20 61 73 20 74 68 65 20 |nted out as the | 00000680 72 65 73 75 6c 74 20 28 26 46 46 46 46 46 46 46 |result (&FFFFFFF| 00000690 46 29 2e 20 20 49 66 20 79 6f 75 20 74 68 69 6e |F). If you thin| 000006a0 6b 0d 61 62 6f 75 74 20 69 74 20 74 68 65 72 65 |k.about it there| 000006b0 20 69 73 20 61 20 6b 69 6e 64 20 6f 66 20 70 65 | is a kind of pe| 000006c0 72 76 65 72 73 65 20 6c 6f 67 69 63 20 74 6f 20 |rverse logic to | 000006d0 74 68 69 73 20 73 69 6e 63 65 0d 74 68 69 73 20 |this since.this | 000006e0 72 65 73 75 6c 74 20 69 73 20 74 68 65 20 6e 65 |result is the ne| 000006f0 61 72 65 73 74 20 74 68 65 20 61 6c 67 6f 72 69 |arest the algori| 00000700 74 68 6d 20 63 61 6e 20 67 65 74 20 74 6f 0d 69 |thm can get to.i| 00000710 6e 66 69 6e 69 74 79 21 0d 0d 49 66 20 77 65 20 |nfinity!..If we | 00000720 77 61 6e 74 65 64 20 74 6f 20 63 6f 6e 74 69 6e |wanted to contin| 00000730 75 65 20 74 68 65 20 64 69 76 69 73 69 6f 6e 20 |ue the division | 00000740 62 65 79 6f 6e 64 20 74 68 65 20 62 69 6e 61 72 |beyond the binar| 00000750 79 0d 70 6f 69 6e 74 20 77 65 20 63 6f 75 6c 64 |y.point we could| 00000760 20 61 6c 6c 6f 63 61 74 65 20 65 78 74 72 61 20 | allocate extra | 00000770 77 6f 72 6b 73 70 61 63 65 20 61 6e 64 20 69 6e |workspace and in| 00000780 63 72 65 61 73 65 20 74 68 65 20 33 32 0d 62 69 |crease the 32.bi| 00000790 74 20 63 6f 75 6e 74 2e 20 20 49 6e 20 61 20 6c |t count. In a l| 000007a0 61 74 65 72 20 6d 6f 64 75 6c 65 20 49 20 73 68 |ater module I sh| 000007b0 61 6c 6c 20 62 65 20 6c 6f 6f 6b 69 6e 67 20 61 |all be looking a| 000007c0 74 20 6e 75 6d 62 65 72 73 0d 77 69 74 68 20 61 |t numbers.with a| 000007d0 20 62 69 6e 61 72 79 20 28 61 6e 64 20 64 65 63 | binary (and dec| 000007e0 69 6d 61 6c 29 20 70 6f 69 6e 74 20 77 69 74 68 |imal) point with| 000007f0 20 66 69 78 65 64 20 61 6e 64 20 66 6c 6f 61 74 | fixed and float| 00000800 69 6e 67 0d 70 6f 69 6e 74 20 6e 75 6d 62 65 72 |ing.point number| 00000810 69 6e 67 20 73 79 73 74 65 6d 73 2e 20 20 54 68 |ing systems. Th| 00000820 65 73 65 20 62 61 73 69 63 20 61 72 69 74 68 6d |ese basic arithm| 00000830 65 74 69 63 20 72 6f 75 74 69 6e 65 73 0d 61 72 |etic routines.ar| 00000840 65 20 6d 61 64 65 20 65 61 73 69 6c 79 20 65 78 |e made easily ex| 00000850 70 61 6e 64 61 62 6c 65 20 62 65 63 61 75 73 65 |pandable because| 00000860 20 77 65 20 77 69 6c 6c 20 6e 65 65 64 20 74 68 | we will need th| 00000870 65 6d 20 6c 61 74 65 72 2e 0d 0d 4e 6f 6e 65 20 |em later...None | 00000880 6f 66 20 74 68 65 20 61 72 69 74 68 6d 65 74 69 |of the arithmeti| 00000890 63 61 6c 20 72 6f 75 74 69 6e 65 73 20 69 6e 20 |cal routines in | 000008a0 74 68 65 73 65 20 6d 6f 64 75 6c 65 73 20 68 61 |these modules ha| 000008b0 76 65 20 62 65 65 6e 0d 69 64 65 61 6c 2e 20 20 |ve been.ideal. | 000008c0 54 68 65 72 65 20 68 61 76 65 20 62 65 65 6e 20 |There have been | 000008d0 70 72 6f 62 6c 65 6d 73 20 77 69 74 68 20 6f 76 |problems with ov| 000008e0 65 72 66 6c 6f 77 20 61 6e 64 20 77 69 74 68 0d |erflow and with.| 000008f0 6e 65 67 61 74 69 76 65 20 6e 75 6d 62 65 72 73 |negative numbers| 00000900 2c 20 61 6e 64 20 74 68 65 79 20 68 61 76 65 20 |, and they have | 00000910 6e 6f 74 20 62 65 65 6e 20 70 61 72 74 69 63 75 |not been particu| 00000920 6c 61 72 6c 79 20 66 61 73 74 2e 20 0d 49 20 68 |larly fast. .I h| 00000930 6f 70 65 20 74 68 6f 75 67 68 20 74 68 61 74 20 |ope though that | 00000940 74 68 65 79 20 68 61 76 65 20 62 65 65 6e 20 63 |they have been c| 00000950 6c 65 61 72 20 73 69 6e 63 65 20 61 72 69 74 68 |lear since arith| 00000960 6d 65 74 69 63 0d 6d 61 6e 69 70 75 6c 61 74 69 |metic.manipulati| 00000970 6f 6e 20 69 73 20 61 20 6d 61 6a 6f 72 20 66 75 |on is a major fu| 00000980 6e 63 74 69 6f 6e 20 6f 66 20 6d 61 6e 79 20 63 |nction of many c| 00000990 6f 6d 70 75 74 65 72 20 70 72 6f 67 72 61 6d 73 |omputer programs| 000009a0 2e 0d 0d 53 74 69 6c 6c 2c 20 74 68 61 74 27 73 |...Still, that's| 000009b0 20 65 6e 6f 75 67 68 20 61 72 69 74 68 6d 65 74 | enough arithmet| 000009c0 69 63 20 66 6f 72 20 74 68 65 20 6d 6f 6d 65 6e |ic for the momen| 000009d0 74 2e 20 20 4e 65 78 74 20 74 69 6d 65 0d 77 65 |t. Next time.we| 000009e0 20 72 65 74 75 72 6e 20 74 6f 20 74 68 65 20 42 | return to the B| 000009f0 42 43 20 4d 69 63 72 6f 20 4f 53 20 77 69 74 68 |BC Micro OS with| 00000a00 20 61 20 6c 6f 6f 6b 20 61 74 20 76 65 63 74 6f | a look at vecto| 00000a10 72 73 20 61 6e 64 0d 77 68 61 74 20 74 68 65 79 |rs and.what they| 00000a20 20 63 61 6e 20 62 65 20 75 73 65 64 20 66 6f 72 | can be used for| 00000a30 2e 0d |..| 00000a32
OS\BITS/T\OSB15.m0
OS\BITS/T\OSB15.m1
OS\BITS/T\OSB15.m2
OS\BITS/T\OSB15.m4
OS\BITS/T\OSB15.m5
.