Division 32-Bit/32-Bit with 16-Bit Register 
Author Message
 Division 32-Bit/32-Bit with 16-Bit Register

Hi,

I need a algorithm to divide 32-bit numbers with 32-Bit numbers  with
32-bit numbers as results and 32-bit numbers as remainder without
using 32-Bit register.

thanks for your help,
Gabriel



Thu, 30 Jun 2005 03:12:52 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:
> Hi,

> I need a algorithm to divide 32-bit numbers with 32-Bit numbers  with
> 32-bit numbers as results and 32-bit numbers as remainder without
> using 32-Bit register.

See recent thread called "division". Basically like (note: not tested)
  mov  ax,[number_in+2]
  xor  dx,dx
  mov  cx,divisor
  div  cx
  mov  [number_out + 2],ax
  mov  ax,[number_in]
  div  cx
  mov  [number_out],ax
  mov  [remainder],dx

--
Michael Brown
My inbox is always open (remove the obvious):



Thu, 30 Jun 2005 10:56:54 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register
Arg, ignore last post, I meant to "close" it but hit send instead ... I'm
working on the "right" way now ...

--
Michael Brown
My inbox is always open (remove the obvious):



Thu, 30 Jun 2005 10:57:00 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:

> Hi,

> I need a algorithm to divide 32-bit numbers with 32-Bit numbers  with
> 32-bit numbers as results and 32-bit numbers as remainder without
> using 32-Bit register.

> thanks for your help,
> Gabriel

It would have been advantageous to specify whether signed or unsigned
division is desired. If you need a 32-bit signed division with remainder
I recommend the following code from my publicly released TP7/BP7
replacement library BPL70N16.ZIP. I tested it extensively back when
I wrote it and never received any bug report so it should work fine.

-- Norbert

; *******************************************************
; *                                                     *
; *     Turbo Pascal Runtime Library Version 7.0        *
; *     Longint Division                                *
; *                                                     *
; *     Copyright (C) 1989-1993 Norbert Juffa           *
; *                                                     *
; *******************************************************

             TITLE   LDIV

CODE         SEGMENT BYTE PUBLIC

             ASSUME  CS:CODE

; Externals

             EXTRN   HaltError:NEAR

; Publics

             PUBLIC  LongDiv

;-------------------------------------------------------------------------------
; LongDiv divides two LONGINT numbers, the dividend and the divisor, resulting
; in a quotient and a remainder. The routine checks for an attempted division
; by zero. In that case, it returns to the error handler with error code C8h.
;
; INPUT:     DX:AX     dividend
;            BX:CX     divisor
;
; OUTPUT:    DX:AX     quotient of division of dividend by divisor
;            BX:CX     remainder of division of dividend by divisor
;
; DESTROYS:  AX,BX,CX,DX,SI,DI,Flags
;-------------------------------------------------------------------------------

LongDiv      PROC    FAR
             XOR     DX, BX            ; SF set if quotient negative
             PUSHF                     ; save flag
             XOR     DX, BX            ; dividend negative ?
             PUSHF                     ; SF set if dividend (&remaindr) negative
             JNS     $dividnd_pos      ; no, ->
             NOT     DX                ; negate
             NEG     AX                ;  dividend
             SBB     DX, -1            ;   in DX:AX
$dividnd_pos:OR      BX, BX            ; divisor negative ?
             JNS     $divisor_pos      ; no, ->
             NOT     BX                ; negate
             NEG     CX                ;  divisor
             SBB     BX, -1            ;   in BX:CX
$divisor_pos:JNZ     $big_divisor      ; divisor > 65535
             CMP     DX, CX            ; only one division needed ?
             JB      $one_div          ; yes, one division sufficient
             JCXZ    $zero_divide      ; divisor is zero, error
             DB      087h, 0C3h        ; XCHG    AX, BX            ; save lo-word of dividend in BX
             XCHG    AX, DX            ; get hi-word of dividend, load DX with 0
             DIV     CX                ; hi-word of quotient in AX
             XCHG    AX, BX            ; BX = quot. hi-word, AX = divid. lo-word
$one_div:    DIV     CX                ; AX = quotient lo-word
             MOV     CX, DX            ; CX = remainder lo-word,
             MOV     DX, BX            ; DX = quotient hi-word
             XOR     BX, BX            ; clear remainder hi-word (rem. in BX:CX)
             JMP     $set_sign         ; make signed
$big_divisor:PUSH    DX                ; save
             PUSH    AX                ;  dividend
             MOV     SI, CX            ; save
             MOV     DI, BX            ;  divisor
             OR      BH, BH            ; shift more than 8 bits ?
             JZ      $scale_down       ; no, do bit shifts
             MOV     CL, CH            ; shift
             MOV     CH, BL            ;  divisor
             MOV     BL, BH            ;   and
             XOR     BH, BH            ;    dividend
             MOV     AL, AH            ;     8 bits
             MOV     AH, DL            ;      right
             MOV     DL, DH            ;       each
             MOV     DH, BH            ;
$scale_down: SHR     DX, 1             ; scale
             RCR     AX, 1             ;  divisor
             SHR     BX, 1             ;   and
             RCR     CX, 1             ;    dividend until
             JNZ     $scale_down       ;      divisor < 65536
             DIV     CX                ; compute quotient
             MOV     CX, AX            ; save quotient
             MOV     BX, AX            ; save quotient
             MUL     DI                ; quotient * divisor hi-word
             XCHG    AX, CX            ; save result in CX, get quotient from AX
             MUL     SI                ; quotient * divisor lo-word
             ADD     DX, CX            ; DX:AX = quotient * divisor
             POP     CX                ; get dividend lo-word
             SUB     CX, AX            ; divid. lo-word - (quot.*divisor)lo-word
             MOV     AX, BX            ; get quotient
             POP     BX                ; restore dividend hi-word
             SBB     BX, DX            ;  subtract divisor * quot. from dividend
             JNB     $remaindr_ok      ; ok if remainder > 0
             ADD     CX, SI            ; compute
             ADC     BX, DI            ;  correct remaindr (0.095% of all cases)
             DEC     AX                ; adjust quotient
$remaindr_ok:XOR     DX, DX            ; clear hi-word of quotient (AX 7FFFh)
$set_sign:   POPF                      ; remainder negative ?
             JNS     $pos_remaind      ; no, ->
             NOT     BX                ; negate
             NEG     CX                ;  remainder
             SBB     BX, -1            ;   in BX:CX
$pos_remaind:POPF                      ; result negative ?
             JNS     $pos_result       ; no, ->
             NOT     DX                ; negate
             NEG     AX                ;  quotient
             SBB     DX, -1            ;   in DX:AX
$pos_result: RET                       ; done, return & pop arguments
$zero_divide:ADD     SP, 4             ; remove saved flags from stack
             MOV     AX, 0C8H          ; load error code 200, "division by zero"
             JMP     HaltError         ; execute error handler
LongDiv      ENDP

             ALIGN   4

CODE         ENDS

             END



Thu, 30 Jun 2005 14:56:08 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register
have your tried the floating point unit?


Thu, 30 Jun 2005 16:15:10 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:
> It would have been advantageous to specify whether signed or unsigned
> division is desired.

I need a unsigned division.

thank's
Gabriel



Fri, 01 Jul 2005 03:24:36 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:

> It would have been advantageous to specify whether signed or unsigned
> division is desired.

> I need a unsigned division.

That's relatively straight forward.

The easy way out is to require a fp unit, in which case you can simply
zero-entend both inputs to 64 bits, load them as 64-bit ints, and then
do the division (with suitable rounding (truncate or minus-infinity)),
and store the result back out.

Without a fp unit, you have to handle the case where both divisor and
dividend requires more than 16 bits: Scale down the divisor so that it
does fit in 16 bits (round up), do the division (which might give a
result which is slightly to small, and then multiply back by the
original divisor.

Subtract and repeat until the remainder is less than the divisior, which
normally will only take one or two iterations.

Terje

--

"almost all programming can be viewed as an exercise in caching"



Fri, 01 Jul 2005 07:06:43 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:
> have your tried the floating point unit?

Like, load two integers, divide them, truncate the result, store it as the
quotient, multiply the quotient by the divisor, subtract the result from the
dividend, and store the result as the remainder. Is that what you mean?
(faster than the integer divide on the 386, I think!)


Fri, 01 Jul 2005 17:15:29 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:

>> Hi,
>> I need a algorithm to divide 32-bit numbers with 32-Bit numbers  with
>> 32-bit numbers as results and 32-bit numbers as remainder without
>> using 32-Bit register.
>It would have been advantageous to specify whether signed or unsigned
>division is desired. If you need a 32-bit signed division with remainder
>I recommend the following code from my publicly released TP7/BP7
>replacement library BPL70N16.ZIP. I tested it extensively back when
>I wrote it and never received any bug report so it should work fine.

>-- Norbert

>; *******************************************************
>; *                                                     *
>; *     Turbo Pascal Runtime Library Version 7.0        *
>; *     Longint Division                                *
>; *                                                     *
>; *     Copyright (C) 1989-1993 Norbert Juffa           *
>; *                                                     *
>; *******************************************************

>             TITLE   LDIV

>CODE         SEGMENT BYTE PUBLIC

>             ASSUME  CS:CODE

>; Externals

>             EXTRN   HaltError:NEAR

>; Publics

>             PUBLIC  LongDiv

>;-------------------------------------------------------------------------------
>; LongDiv divides two LONGINT numbers, the dividend and the divisor, resulting
>; in a quotient and a remainder. The routine checks for an attempted division
>; by zero. In that case, it returns to the error handler with error code C8h.
>;
>; INPUT:     DX:AX     dividend
>;            BX:CX     divisor
>;
>; OUTPUT:    DX:AX     quotient of division of dividend by divisor
>;            BX:CX     remainder of division of dividend by divisor
>;
>; DESTROYS:  AX,BX,CX,DX,SI,DI,Flags
>;-------------------------------------------------------------------------------

>LongDiv      PROC    FAR
>             XOR     DX, BX            ; SF set if quotient negative
>             PUSHF                     ; save flag
>             XOR     DX, BX            ; dividend negative ?
>             PUSHF                     ; SF set if dividend (&remaindr) negative
>             JNS     $dividnd_pos      ; no, ->
>             NOT     DX                ; negate
>             NEG     AX                ;  dividend
>             SBB     DX, -1            ;   in DX:AX
>$dividnd_pos:OR      BX, BX            ; divisor negative ?
>             JNS     $divisor_pos      ; no, ->
>             NOT     BX                ; negate
>             NEG     CX                ;  divisor
>             SBB     BX, -1            ;   in BX:CX
>$divisor_pos:JNZ     $big_divisor      ; divisor > 65535
>             CMP     DX, CX            ; only one division needed ?
>             JB      $one_div          ; yes, one division sufficient
>             JCXZ    $zero_divide      ; divisor is zero, error
>             DB      087h, 0C3h        ; XCHG    AX, BX; save lo-word of dividend in BX

What is 'db  087h, 0C3h'? What is its purpose?

- Show quoted text -

Quote:
>             XCHG    AX, DX            ; get hi-word of dividend, load DX with 0



Tue, 05 Jul 2005 23:56:29 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:
> >             DB      087h, 0C3h        ; XCHG    AX, BX; save lo-word of dividend in BX

> What is 'db  087h, 0C3h'? What is its purpose?

It's an alternate opcode for "XCHG AX, BX" as implied by
the comment. The x86 ISA includes many cases of redundant
instruction encodings. Most assemblers automatically pick
the shortest such encoding (1 byte in this case). In this
piece of old code, I made use of alternate encodings to
shift code around slightly for the purpose of branch target
alignment (for performance reasons).

C:\>debug
-a
0AC9:0100 xchg ax, bx
0AC9:0102 xchg bx, ax
0AC9:0103
-u 100 102
0AC9:0100 87C3          XCHG    AX,BX
0AC9:0102 93            XCHG    BX,AX

BTW, I have reworked the previously posted code to perform
unsigned 32-bit division. See below.

-- Norbert

             ;; uldivide divides 2 unsigned 32-bit
             ;; it returns both quotient and remainder
             ;;
             ;; in:  DX:AX = dividend
             ;;      BX:CX = divisor
             ;;
             ;; out: DX:AX = quotient
             ;;      BX:CX = remainder
             ;;
             ;; destroys: AX, BX, CX, DX, SI, DI, Flags
uldivide:
             OR      BX, BX            ; divisor > 65535 ?
             JNZ     short $big_divisor; yup
             CMP     DX, CX            ; only one division needed ?
             JB      short $one_div    ; yes, one division sufficient
             XCHG    AX, BX            ; save lo-word of dividend in BX
             XCHG    AX, DX            ; AX = dividend_hi, load DX with 0
             DIV     CX                ; hi-word of quotient in AX
             XCHG    AX, BX            ; BX = quotient_hi, AX = dividend_lo
$one_div:    DIV     CX                ; AX = quotient_lo
             MOV     CX, DX            ; CX = remainder_lo
             MOV     DX, BX            ; DX = quotient_hi
             XOR     BX, BX            ; clear remainder_hi (rem. in BX:CX)
             JMP     short $done       ; finished!
$big_divisor:PUSH    BP                ; save frame pointer
             PUSH    DX                ; save
             PUSH    AX                ;  dividend
             MOV     SI, CX            ; save
             MOV     DI, BX            ;  divisor
             OR      BH, BH            ; shift more than 8 bits ?
             JZ      short $scale_down ; no, do bit shifts
             MOV     CL, CH            ; shift
             MOV     CH, BL            ;  divisor
             MOV     BL, BH            ;   and
             XOR     BH, BH            ;    dividend
             MOV     AL, AH            ;     8 bits
             MOV     AH, DL            ;      right
             MOV     DL, DH            ;       each
             MOV     DH, BH            ;
$scale_down: SHR     DX, 1             ; scale
             RCR     AX, 1             ;  divisor
             SHR     BX, 1             ;   and
             RCR     CX, 1             ;    dividend until
             JNZ     short $scale_down ;      divisor < 65536
             DIV     CX                ; AX = preliminary quotient
             MOV     CX, AX            ; save quotient
             MOV     BX, AX            ; save quotient
             MUL     DI                ; quotient * divisor_hi
             XCHG    AX, CX            ; save result in CX, quotient to AX
             MUL     SI                ; quotient * divisor_lo
             POP     BP                ; get dividend_lo
             SUB     BP, AX            ; dividend_lo - (quot.*divisor_lo)_lo
             MOV     AX, BX            ; quotient
             POP     BX                ; get dividend hi-word
             SBB     BX, DX            ; dividend_hi - (quot.*divisor_lo)_hi
             SUB     BX, CX            ; dividend_hi - (quot.*divisor_hi)
             MOV     CX, BP            ; remainder_lo
             POP     BP                ; restore frame pointer
             JNC     short $remaindr_ok; dividend >= (quotient * divisor)
             ADD     CX, SI            ; compute
             ADC     BX, DI            ;  correct remainder
             DEC     AX                ; adjust quotient
$remaindr_ok:XOR     DX, DX            ; clr quotient_hi (quotient <= FFFFh)
$done:



Thu, 14 Jul 2005 07:56:20 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register
On Sat, 25 Jan 2003 23:56:20 +0000 (UTC), "Norbert Juffa"

Quote:

>> >             DB      087h, 0C3h        ; XCHG    AX, BX; save lo-word of dividend in BX

>> What is 'db  087h, 0C3h'? What is its purpose?

>It's an alternate opcode for "XCHG AX, BX" as implied by
>the comment. The x86 ISA includes many cases of redundant
>instruction encodings. Most assemblers automatically pick
>the shortest such encoding (1 byte in this case). In this
>piece of old code, I made use of alternate encodings to
>shift code around slightly for the purpose of branch target
>alignment (for performance reasons).

>C:\>debug
>-a
>0AC9:0100 xchg ax, bx
>0AC9:0102 xchg bx, ax
>0AC9:0103
>-u 100 102
>0AC9:0100 87C3          XCHG    AX,BX
>0AC9:0102 93            XCHG    BX,AX

>BTW, I have reworked the previously posted code to perform
>unsigned 32-bit division. See below.

>-- Norbert

>             ;; uldivide divides 2 unsigned 32-bit
>             ;; it returns both quotient and remainder
>             ;;
>             ;; in:  DX:AX = dividend
>             ;;      BX:CX = divisor
>             ;;
>             ;; out: DX:AX = quotient
>             ;;      BX:CX = remainder
>             ;;
>             ;; destroys: AX, BX, CX, DX, SI, DI, Flags
>uldivide:
>             OR      BX, BX            ; divisor > 65535 ?
>             JNZ     short $big_divisor; yup
>             CMP     DX, CX            ; only one division needed ?
>             JB      short $one_div    ; yes, one division sufficient
>             XCHG    AX, BX            ; save lo-word of dividend in BX
>             XCHG    AX, DX            ; AX = dividend_hi, load DX with 0
>             DIV     CX                ; hi-word of quotient in AX
>             XCHG    AX, BX            ; BX = quotient_hi, AX = dividend_lo
>$one_div:    DIV     CX                ; AX = quotient_lo
>             MOV     CX, DX            ; CX = remainder_lo
>             MOV     DX, BX            ; DX = quotient_hi
>             XOR     BX, BX            ; clear remainder_hi (rem. in BX:CX)
>             JMP     short $done       ; finished!
>$big_divisor:PUSH    BP                ; save frame pointer
>             PUSH    DX                ; save
>             PUSH    AX                ;  dividend
>             MOV     SI, CX            ; save
>             MOV     DI, BX            ;  divisor
>             OR      BH, BH            ; shift more than 8 bits ?
>             JZ      short $scale_down ; no, do bit shifts
>             MOV     CL, CH            ; shift
>             MOV     CH, BL            ;  divisor
>             MOV     BL, BH            ;   and
>             XOR     BH, BH            ;    dividend
>             MOV     AL, AH            ;     8 bits
>             MOV     AH, DL            ;      right
>             MOV     DL, DH            ;       each
>             MOV     DH, BH            ;
>$scale_down: SHR     DX, 1             ; scale
>             RCR     AX, 1             ;  divisor
>             SHR     BX, 1             ;   and
>             RCR     CX, 1             ;    dividend until
>             JNZ     short $scale_down ;      divisor < 65536
>             DIV     CX                ; AX = preliminary quotient
>             MOV     CX, AX            ; save quotient
>             MOV     BX, AX            ; save quotient
>             MUL     DI                ; quotient * divisor_hi
>             XCHG    AX, CX            ; save result in CX, quotient to AX
>             MUL     SI                ; quotient * divisor_lo
>             POP     BP                ; get dividend_lo
>             SUB     BP, AX            ; dividend_lo - (quot.*divisor_lo)_lo
>             MOV     AX, BX            ; quotient
>             POP     BX                ; get dividend hi-word
>             SBB     BX, DX            ; dividend_hi - (quot.*divisor_lo)_hi
>             SUB     BX, CX            ; dividend_hi - (quot.*divisor_hi)
>             MOV     CX, BP            ; remainder_lo
>             POP     BP                ; restore frame pointer
>             JNC     short $remaindr_ok; dividend >= (quotient * divisor)
>             ADD     CX, SI            ; compute
>             ADC     BX, DI            ;  correct remainder
>             DEC     AX                ; adjust quotient
>$remaindr_ok:XOR     DX, DX            ; clr quotient_hi (quotient <= FFFFh)
>$done:

Thank you very very much indeed :))))
I'm reading this code, and your divide make me think in improvement of
a small newbie-divide proc that I wrote in C, for arrays of chars
(with the usual way to do division). I remember that a small (and
doubtful) change made that divide improved x2. Now I will use 16 bits
array, and C first, then asm (if there is time and all will go well)
________________
We have to walk


Thu, 21 Jul 2005 17:56:28 GMT  
 Division 32-Bit/32-Bit with 16-Bit Register

Quote:

> Thank you very very much indeed :))))
> I'm reading this code, and your divide make me think in improvement of
> a small newbie-divide proc that I wrote in C, for arrays of chars
> (with the usual way to do division). I remember that a small (and
> doubtful) change made that divide improved x2. Now I will use 16 bits
> array, and C first, then asm (if there is time and all will go well)

If you have a very long divisor, then you should almost certainly use
reciprocal multiplication instead:

One method is to calculate a 64-bit accurate fp reciprocal, and then
iteratively use that to multiply the leading 64 bits of the current
remainder (starting with the full number):

The answer is an approximate result, with about 63-65 significant bits:

Multiply back, subtract from the original number and repeat.

For even longer numbers, you can use Newton-Rhapson to convert the
initial approximate reciprocal into something which has as many
significant bits as your divisor/dividend, then replace the division
with a single multiplication (which you can do with FFTs if the operands
are really long).

Take a look at GMP (Use Google!) for asm versions of all these algorithms!

Terje

--

"almost all programming can be viewed as an exercise in caching"

----------------------------------------------------------------------
This e-mail with attached documents is only for the intended recipient
and may contain information that is confidential and/or privileged.
If you are not the intended recipient, you are hereby notified that
any unauthorised reading, copying, disclosure or distribution of the
e-mail and/or attached documents is expressly forbidden, and may be a
criminal offence, and that Hydro shall not be liable for any action
taken by you based on the electronically transmitted information.
If you have received this e-mail by mistake, you are kindly requested
to immediately inform the sender thereof and delete the e-mail and
attached documents.



Fri, 22 Jul 2005 15:56:37 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. 32-bit bin2ascii with 16-bit registers

2. Errors: cannot use 16-bit register with a 32-bit address

3. 32-bit bin2ascii with 16-bit registers

4. 16, 16/32, 32 bit Forths: Pros/Cons?

5. 32 bit ST communicating with 16 bit VB

6. How to use SE at any color resolution (256, 16-bit, 32-bit)

7. Can I use 16 bit DLL and 32-bit exe together

8. Changing from 16-bit to 32-bit makes zillion duplicate symbols

9. 16-bit to 32-bit woes

10. Should I use 16 bit or 32 bit??

11. Graphics Error 16-bit vs 32-bit

12. Printing 16 bit and 32 bit

 

 
Powered by phpBB® Forum Software