'{$STAMP BS2pe}
'{$PBASIC 2.5}
' divide31x15.bse  (c) 2003 Tracy Allen http://www.owlogic.com
' computes long division, 31 bit numerator by 15 bit denominator
' unsigned, bit 32 and bit 16 can be the sign
' N = D * Q + R, find Q and R given N and D
' N/D = Q + R/D
' this program will also resolve the remainder fraction R/D
' to the approximation Z/65536=R/D, for subsequent use in ** operation
' for BASIC Stamp using double precision algorithm
' but makes use of PBASIC functions where possible
' to shorten the calculation
' debug code commented back in will show intermediate results

n0       VAR  Word           ' numerator entered by user
n1       VAR  Word

dv       VAR  Word           ' denominator entered by user

q0       VAR  Word           ' quotient to be computed
q1       VAR  Word		' can be as large as numerator

rm       VAR  Word           ' remainder to be computed, won't exceed divisor

z       VAR  Word           ' working variable

idx      VAR  Byte		' index

top:
' demo asks user to input two numbers to test
SEROUT 16,$54,[CR,"enter 8 hex digit numerator and 4 hex denominator (0..9 a..f)"]

SEROUT 16,$54,[CR,"numerator 7fffffff: "]
SERIN 16,$54,[HEX4 n1,HEX4 n0]

SEROUT 16,$54,[CR,"denominator 7fff: "]
SERIN 16,$54,[HEX4 dv]

SEROUT 16,$54,[CR,"thank you..."]

test_divide_by_zero:
IF dv=0 THEN
  SEROUT 16,$54,[CR,"divide by zero" ,CR]
  GOTO top
  ENDIF

show_N_is_zero:		' shortcut, not absolutely necessary, could go right to main calculation
IF N0 | N1 = 0 THEN
  SEROUT 16,$54,[CR,"numerator is zero"]
  GOTO display
  ENDIF

adjust_3115:
  n1=n1 << 1 + n0.BIT15  	' numerator to 16:15 format
				' so low bit can be used as carry/borrow
  n0.BIT15=0

test_N_equals_or_less_than_D:
' pretest n<d, shortcut
' not absolutely necessary to do this, could go right to main calculation
' because the main algorithm will resolve the quotient and remainder correctly
q0 = n0 - dv			' bit 15 set if D0>N0
q1 = n1 - n0.BIT15		' carry
  IF q0 | q1 = 0 THEN
    SEROUT 16,$54,[CR,"numerator=denominator"]
    q0=1      ' quotient=1
    q1=0
    rm=0		' no remainder
    GOTO display
  ENDIF

  IF q1.BIT15=1 THEN
    SEROUT 16,$54,[CR,"numerator<denominator"]
    q0=0		' quotient=0
    q1=0
    rm=n0     ' remainder equals numerator
    GOTO display
  ENDIF

main_calculation:
  q1 = n1/dv		' high word of quotient
  q0 = 0
  z = n1			'
  FOR idx=14 TO 0
    z = z // dv << 1
    q0.BIT0(idx) = z / dv
    ' if z>= dv then q0.bit0(idx)=1 else q0.bit0(idx)=0
  NEXT
  q0 = q0 + (n0/dv)	' result plus contribution from low word
  rm = (z//dv)+(n0//dv) 	' remainder comes from two terms
  q0 = rm / dv + q0	' may be a carry (r0/dv will be 0 or 1)
  q1 = q1 + q0.BIT15	' and carry to high word
  q0.BIT15 = 0	' adjust 16:15
  rm = rm // dv	' final remainder
  q0.BIT15 = q1.BIT0	' reajust 15:16
  q1 = q1 >> 1	' complete readjustment

display:
  SEROUT 16,$54,[CR,"  quotient: ",HEX4 q1,HEX4 q0]
  SEROUT 16,$54,[CR,"  remainder: ",HEX4 rm,CR,CR]

Remainder_fraction:
  ' rm is the remainder in n1:n0 = q1:q0 * dv + rm
    ' now calculate rm/dv, approximated as z/65536
    ' for use with **
  FOR idx=15 TO 0
    rm = rm//dv << 1
    z.BIT0(idx) = rm/dv
  next

display_rationalized:
  SEROUT 16,$54,[CR,"  rationalized: ",HEX4 zm,CR,CR]

GOTO top


DEBUG HOME