Division 32-Bit/32-Bit with 16-Bit Register
Author |
Message |
Gabri #1 / 12
|
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 |
|
|
Michael Brow #2 / 12
|
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 |
|
|
Michael Brow #3 / 12
|
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 |
|
|
Norbert Juff #4 / 12
|
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 |
|
|
Goleman #5 / 12
|
Division 32-Bit/32-Bit with 16-Bit Register
have your tried the floating point unit?
|
Thu, 30 Jun 2005 16:15:10 GMT |
|
|
Gabri #6 / 12
|
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 |
|
|
Terje Mathise #7 / 12
|
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 |
|
|
Ben Peddel #8 / 12
|
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 |
|
|
giusepp #9 / 12
|
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? Quote: > XCHG AX, DX ; get hi-word of dividend, load DX with 0
|
Tue, 05 Jul 2005 23:56:29 GMT |
|
|
Norbert Juff #10 / 12
|
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 |
|
|
giusepp #11 / 12
|
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 |
|
|
Terje Mathise #12 / 12
|
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 |
|
|
|