integer division and multiplication

[Dr Jefyll]

barrym95838 wrote:

It passed my exhaustive half-width test

Nice work, Mike. I've been meaning to ask -- can you elaborate on the test, please? It sounds as if you used the same algorithm and simply rewrote the 65xx code to create a UM/MOD version that deals with shorter operands -- is that right?

As for the code you created (in Forth?) to call the UM/MOD and verify its results, I'm guessing there was a loop whose index served as one of the operands, and, from one iteration to the next, you use addition or subtraction (not division) as a quick way to determine what the result should be.

[barrym95838]

Not as elegant as you may have imagined, Dr. J! Here's a snapshot of my half-width test: D is the divisor, H is dividend:H and L is dividend:L.

Code: Select all

]LIST

 10  FOR H = 0 TO 255
 20  FOR L = 0 TO 255
 30  FOR D = 0 TO 255
 40  IF H >  = D THEN 90
 50  POKE 0,D: POKE 1,H: POKE 2,L: CALL 768
 60 E = H * 256 + L
 65 Q =  INT (E / D)
 70 R = E - Q * D
 80  IF R <  >  PEEK (1) THEN  STOP 
 85  IF Q <  >  PEEK (2) THEN  STOP 
 90  NEXT D,L,H

]CALL-151

*300L

0300-   A0 08       LDY   #$08
0302-   A5 01       LDA   $01
0304-   06 02       ASL   $02
0306-   2A          ROL   
0307-   B0 04       BCS   $030D
0309-   C5 00       CMP   $00
030B-   90 04       BCC   $0311
030D-   E5 00       SBC   $00
030F-   E6 02       INC   $02
0311-   88          DEY   
0312-   D0 F0       BNE   $0304
0314-   85 01       STA   $01
0316-   60          RTS   
0317-   00          BRK   
0318-   00          BRK   
0319-   00          BRK   
031A-   00          BRK   
031B-   00          BRK   
031C-   00          BRK   
031D-   00          BRK   
*

]

It has been "reduced" to 2^24 iterations, which AppleWin can whip through in less than an hour at full boost on my old Windoze machine. The internal structures of the routine(s) were carefully narrowed, hopefully without altering the final judgment ... it would take literally hundreds of years for the same naive set-up to iterate through all 2^48 full-width possibilities.

Mike B.

[Edit: Sorry for polluting a Forth-based thread with Apple-Soft code ... it's still my quick-and-dirty go-to, after all these years ...
]

[chitselb]

Here's a link to a Transactor article about division, with some benchmarks https://archive.org/stream/transactor-magazines-v9-i02 It's on page 10

[BigEd]

(Direct link, browser permitting.)

[JimBoyd]

chitselb wrote:

The UD/MOD base primitive approach was what I first considered and implemented. I came across this in VolksForth, which builds UD/MOD on top of UM/MOD , instead of the other way around. This is cool because, in my opinion, 32/32-bit division is seldom invoked and will be even more rare in my own application code, so I don't want to punish the user on every occurrence of division by crunching the whole 32-bits using UD/MOD as the basic primitive. Also UD/MOD isn't part of the Fig, Forth-79, Forth-83 or ANS standards, while UM/MOD is in the required wordset for Forth-83, aka U/MOD in Forth-79.

Code: Select all

  : ud/mod ( ud1 u2 -- urem udquot )
     >r   0 r@ um/mod   r> swap >r   um/mod r> ;

I came across an idea in Blazin' Forth where a primitive used by other primitives is implemented as a subroutine, the first six bytes being a JSR to the actual code of the routine followed by a JMP to NEXT.
Here is how to implement UD/MOD, for an ITC Forth, in terms of UM/MOD without incurring much of a speed penalty. First implement UM/MOD so its body is a subroutine. This only adds 12 cycles to its execution time.

Code: Select all

CODE UM/MOD  ( UD U1 -- U2 U3 )
   HERE 6 + JSR,  NEXT JMP,
   <actual code for UM/MOD algorithm>
        .
        .
        .
   RTS,  END-CODE

Then call the actual code for the UM/MOD algorithm from UD/MOD.

Code: Select all

HEX
CODE UD/MOD  ( UD1 U1 -- U2 UD2 )
   DEX,  DEX,
   2 ,X LDA,  N 2+ STA,  0 ,X STA,
   3 ,X LDA,  N 3 + STA,  1 ,X STA,
   2 ,X STY,  3 ,X STY,
   ' UM/MOD @ 6 + JSR,
   0 ,X LDA,  PHA,
   1 ,X LDA,  PHA,
   N 2+ LDA,  0 ,X STA,
   N 3 + LDA,  1 ,X STA,
   ' UM/MOD @ 6 + JSR,
   PLA,
   PUSH JMP,  END-CODE

I tried implementing UD/MOD as a primitive with its own division loop, it didn't use UM/MOD. What surprised me was that this way ( the code above ) was not only smaller, but faster as well. Hope this helps.

Cheers,
Jim

Edit: Oops, I forgot about your split stack.
Edit: I forgot to mention that UM/MOD does not use N+2 or N+3.