3. division by constant

division by constant

  • M

    hoi

    weiß jemand wie das funktioniert ?
    hab zwar scho google in anspruch genommen, wber iegendwie bin ich damit nicht weitergekommen.

    vielleicht kann jemand das mit ner division durch 10 erklaeren.

    cermy

    Meep Meep

    0
  • C

    wenn du erklärst, was das sein soll, erklären wir dir vielleicht, wie es funktioniert 🙂

    0
  • M

    hoi camper

    da gehts um schnelle division mit einem bestimmten devisor. aehnlich multiplikation mit kehrwert

    kleiner auszug aus Agner Fogs Pentium Optimization:

    Dividing by a constant can be done by multiplying with the reciprocal. A useful algorithm for
integer division by a constant is as follows:

To calculate the unsigned integer division q = x / d, you first calculate the reciprocal of the
divisor, f = 2r / d, where r defines the position of the binary decimal point (radix point). Then
multiply x with f and shift right r positions. The maximum value of r is 32+b, where b is the
number of binary digits in d minus 1. (b is the highest integer for which 2b ≤ d). Use r = 32+b
to cover the maximum range for the value of the dividend x.

This method needs some refinement in order to compensate for rounding errors. The
following algorithm will give you the correct result for unsigned integer division with
truncation, i.e. the same result as the DIV instruction gives (Thanks to Terje Mathisen who

invented this method):
b = (the number of significant bits in d) - 1
r = 32 + b
f = 2r / d

If f is an integer then d is a power of 2: goto case A.
If f is not an integer, then check if the fractional part of f is < 0.5
If the fractional part of f < 0.5: goto case B.
If the fractional part of f > 0.5: goto case C.

case A (d = 2b):
result = x SHR b
case B (fractional part of f < 0.5):
round f down to nearest integer
result = ((x+1) * f) SHR r
case C (fractional part of f > 0.5):
round f up to nearest integer
result = (x * f) SHR r

Example:
Assume that you want to divide by 5.
5 = 101B.
b = (number of significant binary digits) - 1 = 2
r = 32+2 = 34
f = 234 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(hexadecimal)
The fractional part is greater than a half: use case C.
Round f up to 0CCCCCCCDH.
The following code divides EAX by 5 and returns the result in EDX:
[asm]
MOV EDX, 0CCCCCCCDh
MUL EDX
SHR EDX,2
[/asm]
After the multiplication, EDX contains the product shifted right 32 places. Since r = 34 you
have to shift 2 more places to get the result. To divide by 10, just change the last line to SHR
EDX,3.
In case B we would have:
[asm]
ADD EAX, 1
MOV EDX, f
MUL EDX
SHR EDX, b
[/asm]
This code works for all values of x except 0FFFFFFFFH which gives zero because of
overflow in the ADD EAX,1 instruction. If x = 0FFFFFFFFH is possible, then change the
code to:
[asm]
MOV EDX,f
ADD EAX,1
JC DOVERFL
MUL EDX
DOVERFL: SHR EDX,b
[/asm]
If the value of x is limited, then you may use a lower value of r, i.e. fewer digits. There can
be several reasons for using a lower value of r:

• you may set r = 32 to avoid the SHR EDX,b in the end.
• you may set r = 16+b and use a multiplication instruction that gives a 32-bit result

rather than 64 bits. This will free the EDX register:
[asm]
IMUL EAX,0CCCDh / SHR EAX,18
[/asm]
• you may choose a value of r that gives case C rather than case B in order to avoid
the ADD EAX,1 instruction
The maximum value for x in these cases is at least 2r-b, sometimes higher. You have to do
a systematic test if you want to know the exact maximum value of x for which the code
works correctly.
You may want to replace the slow multiplication instruction with faster instructions as
explained on page 114.
The following example divides EAX by 10 and returns the result in EAX. I have chosen r=17
rather than 19 because it happens to give a code that is easier to optimize, and covers the
same range for x. f = 217 / 10 = 3333h, case B: q = (x+1)*3333h:
[asm]
LEA EBX,[EAX+2*EAX+3]
LEA ECX,[EAX+2*EAX+3]
SHL EBX,4
MOV EAX,ECX
SHL ECX,8
ADD EAX,EBX
SHL EBX,8
ADD EAX,ECX
ADD EAX,EBX
SHR EAX,17
[/asm]
A systematic test shows that this code works correctly for all x < 10004H.

    Meep Meep

    0
  • ?

    Ahh ja, das ist alles äusserst interessant. Vielleicht könntest du nun auch noch dein Problem erklären... 🙄

    0
  • M

    re

    mein problem ist das ich das nicht recht verstehe. also die funktionsweise.
    hab nach dem beispiel ne division durch 10 probiert, aber da bekam ich immer falsche ergebnisse

    Meep Meep

    0
Anmelden zum Antworten