Multi-Precision Unsigned Integer Multiply and Diivide

Just to make sure for anyone who is reading, this code will be for a PDP-11 which supports 16-Bit values. About 10 years ago, I produced some rather complicated subroutines for multi-precision Unsigned Integer Multiply and used inverse Multiply to effectively produce Divide. Since they were mostly for a minimum of 128-Bit and larger arithmetic, I felt that they were reasonable as a first effort. More recently, I find that I now need a small and reasonably efficient routine (both in code size and efficiency - assume the extra multi-integer instructions MUL and DIV are present) to Encode 32-Bit (perhaps up to 48-Bit, but certainly no larger than 64-Bit) Unsigned Integers - which requires effective division by TEN. I already have very simple alternatives which can perform Unsigned Division of 32-Bit Unsigned Integers (and by extension 48-Bit Unsigned Integers); they either require lengthy one bit at a time manipulation for all 32 bits or a table for subtracting all of the 9 powers of TEN vs all of the 32 Bit Unsigned Integer. Since I already MUST have a subroutine to Encode a 16-Bit Unsigned Integer, that is the acceptable starting point at the present time. The alternative I am using right now is to (R0,R1 holds the 32-Bit Value): Cmp #4999.,R0 ;5000.*65536.=327680000. Bhis 110$ ;Branch if DIV will not overflow 10$: ; Subtract 100,000,000 up to 42 times ;..... 110$: Div #10000.,R0 ;Get two values to Encode ;..... As long as the 32-Bit value is less than 327,680,000 (which means that R0 is less than 5000 - if you divide 327,680,000 by 65536, you get the high order portion of the 32-Bit value - otherwise the quotient overflows), the Div #10000.,R0 can be used. That results in three cases for any Unsigned 32-Bit Integer: (a) Less than 65,536 which is just the remainder, R1 to Encode (b) Less than 327,680,000 which uses the DIV to produce both the quotient, R0, and the remainder, R1 to Encode (c) Less than 4,294,967,296 (which is one more than the maximum for an Unsigned 32-Bit Integer) for which I subtract 100,000,000 up to 42 times (rare and quite acceptable), Encode that value, then finish by taking care of the remainder of up to 99,999,999 using (b) above. Note that the number of subtractions can be greatly reduced (to 12 times or less) if the first subtractions are for 1,000,000,000 Is there some (relatively simple and code size efficient) algorithm that can use the SIGNED PDP-11 DIV instruction for values that are equal or greater than 327,680,000 so that ONLY 16-Bit values need to be Encoded? OR, if the 32-Bit value is first shifted, is there some value that I can use to MUL or DIV with to obtain the first value under (c), i.e. the upper two digits for the HUNDREDS of MILLIONS and BILLIONS without having to subtract up to 42 times (or even 12 times)? For example, if just the upper portion of the 32-Bit value, in R0, is divided by 1525, the result will usually be the required upper two digits, but as each multiple of 100,000,000 is closely approached, the result will (rarely) be one too high. Dividing by 1526 produces a result which will (rarely) be one too low. Perhaps there is an algorithm that will always be correct and the multiple subtract is not needed? Maybe someone has found a correction factor which uses the remainder of the DIV by 1526 plus the lower portion of the original 32-Bit value, in R1, to correct the result when that result is one too low. Just thought I would ask to see if anyone else already found a much better algorithm. Jerome Fine