Division algoritme - Division algorithm

En divisionsalgoritme er en algoritme, der givet to heltal N og D beregner deres kvotient og/eller resten , resultatet af den euklidiske division . Nogle anvendes i hånden, mens andre er ansat ved design af digitale kredsløb og software.

Divisionsalgoritmer falder i to hovedkategorier: langsom division og hurtig division. Langsomme opdelingsalgoritmer producerer et ciffer af den endelige kvotient pr. Iteration. Eksempler på langsom opdeling omfatter restaurering , ikke-udførende restaurering, ikke-restaurering og SRT- division. Hurtige opdelingsmetoder starter med en tæt tilnærmelse til den endelige kvotient og producerer dobbelt så mange cifre i den endelige kvotient på hver iteration. Newton – Raphson og Goldschmidt -algoritmer falder ind under denne kategori.

Varianter af disse algoritmer tillader brug af hurtige multiplikationsalgoritmer . Det resulterer i, at computertiden, der er nødvendig for en division , for store heltal er den samme op til en konstant faktor som den tid, der er nødvendig for en multiplikation, alt efter hvilken multiplikationsalgoritme der bruges.

Diskussionen henviser til formularen , hvor ${\ displaystyle N/D = (Q, R)}$

• N = tæller (udbytte)
• D = nævner (divisor)

er input, og

• Q = kvotient
• R = resten

er output.

Division ved gentagen subtraktion

Den enkleste divisionsalgoritme, historisk indarbejdet i en største fælles divisoralgoritme præsenteret i Euclids elementer , Bog VII, proposition 1, finder resten givet to positive heltal ved kun at bruge subtraktioner og sammenligninger:

R := N
while R ≥ D do
  R := R − D
end
return R

Beviset for, at kvotienten og resten eksisterer og er unikke (beskrevet ved euklidisk division ) giver anledning til en komplet divisionsalgoritme ved hjælp af tilføjelser, subtraktioner og sammenligninger:

function divide(N, D)
  if D = 0 then error(DivisionByZero) end
  if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end
  if N < 0 then
    (Q,R) := divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- At this point, N ≥ 0 and D > 0
  return divide_unsigned(N, D)
end  
function divide_unsigned(N, D)
  Q := 0; R := N
  while R ≥ D do
    Q := Q + 1
    R := R − D
  end
  return (Q, R)
end

Denne procedure producerer altid R ≥ 0. Selvom det er meget simpelt, tager det Ω (Q) trin, og det er eksponentielt langsommere end endda langsomme divisionsalgoritmer som lang division. Det er nyttigt, hvis Q vides at være lille (er en outputfølsom algoritme ) og kan fungere som en eksekverbar specifikation.

Lang division

Lang division er standardalgoritmen, der bruges til pen-og-papir-division af flercifrede tal udtrykt i decimalnotation. Det skifter gradvist fra venstre til højre ende af udbyttet og trækker det størst mulige multiplum af divisoren (på cifferniveau) i hvert trin; multiplerne bliver derefter cifrene i kvoten, og den sidste forskel er derefter resten.

Når den bruges med en binær radix, danner denne metode grundlaget for (usigneret) heltal division med resten algoritme nedenfor. Kort division er en forkortet form for lang division, der er velegnet til etcifrede delere. Chunking  -også kendt som metoden for delkvotienter eller bøjlemetoden-er en mindre effektiv form for lang opdeling, som kan være lettere at forstå. Ved at tillade en at trække flere multipler, end hvad man i øjeblikket har på hvert trin, kan der også udvikles en mere friformsvariant af lang division

Heltal division (usigneret) med resten

Følgende algoritme, den binære version af den berømte lange division , vil splitte N ved D , anbringelse kvotienten i Q og resten i R . I den følgende pseudokode behandles alle værdier som usignerede heltal.

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

Eksempel

Hvis vi tager N = 1100 ₂ (12 ₁₀ ) og D = 100 ₂ (4 ₁₀ )

Trin 1 : Indstil R = 0 og Q = 0
Trin 2 : Tag i = 3 (en mindre end antallet af bits i N)
Trin 3 : R = 00 (venstre forskudt med 1)
Trin 4 : R = 01 (indstilling R (0) til N (i))
Trin 5 : R <D, så spring sætningen over

Trin 2 : Indstil i = 2
Trin 3 : R = 010
Trin 4 : R = 011
Trin 5 : R <D, sætning sprunget over

Trin 2 : Indstil i = 1
Trin 3 : R = 0110
Trin 4 : R = 0110
Trin 5 : R> = D, angivelse angivet
Trin 5b : R = 10 (R − D)
Trin 5c : Q = 10 (indstilling Q ( i) til 1)

Trin 2 : Indstil i = 0
Trin 3 : R = 100
Trin 4 : R = 100
Trin 5 : R> = D, indtastet sætning
Trin 5b : R = 0 (R − D)
Trin 5c : Q = 11 (indstilling Q ( i) til 1)

ende
Q = 11 ₂ (3 ₁₀ ) og R = 0.

Langsom opdelingsmetoder

Langsomme opdelingsmetoder er alle baseret på en standard recurrence ligning

${\ displaystyle R_ {j+1} = B \ gange R_ {j} -q_ {n- (j+1)} \ gange D,}$

hvor:

• R _j er den j -th delvise rest af divisionen
• B er radix (basis, normalt 2 internt i computere og lommeregnere)
• q _{n- ( j + 1)} er cifret i kvoten i position n- ( j +1), hvor cifferpositionerne er nummereret fra mindst signifikant 0 til mest signifikante n −1
• n er antallet af cifre i kvoten
• D er divisoren

Gendanner division

Gendannelsesdivisionen opererer på brækketal med fast punkt og afhænger af antagelsen 0 < D < N .

Kvotientcifrene q dannes ud fra cifersættet {0,1}.

Den grundlæggende algoritme til binær (radix 2) gendannelse af division er:

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R ≥ 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient

Ikke-udførende gendannelsesdivision svarer til gendannelsesdivision bortset fra at værdien af ​​2R gemmes, så D behøver ikke at tilføjes igen for R <0.

Ikke-restaurerende division

Ikke-gendannende division bruger cifrets sæt {−1, 1} til kvotientcifrene i stedet for {0, 1}. Algoritmen er mere kompleks, men har den fordel, når den implementeres i hardware, at der kun er én beslutning og addition/subtraktion pr. Kvotbit; der er ikke noget genoprettelsestrin efter subtraktionen, som potentielt reducerer antallet af operationer med op til halvdelen og lader det udføres hurtigere. Den grundlæggende algoritme for binær (radix 2) ikke-gendannende division af ikke-negative tal er:

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bits
  if R >= 0 then
    q[i] := +1
    R := 2 * R − D
  else
    q[i] := −1
    R := 2 * R + D
  end if
end
 
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

Efter denne algoritme er kvotienten i en ikke-standardform bestående af cifre på -1 og +1. Denne form skal konverteres til binær for at danne den endelige kvotient. Eksempel:

Konverter følgende kvotient til cifersættet {0,1}:
Start:	${\ displaystyle Q = 111 {\ bar {1}} 1 {\ bar {1}} 1 {\ bar {1}}}$
1. Form det positive udtryk:	${\ displaystyle P = 11101010 \,}$
2. Masker det negative udtryk*:	${\ displaystyle M = 00010101 \,}$
3. Træk ::${\ displaystyle PM}$	${\ displaystyle Q = 11010101 \,}$
*. (Signeret binær notation med ens komplement uden tos komplement )

Hvis −1 cifrene i er gemt som nuller (0) som det er almindeligt, så er og computing trivielt: udfør ens komplement (bit for bit komplement) på originalen . ${\ displaystyle Q}$${\ displaystyle P}$ ${\ displaystyle Q}$${\ displaystyle M}$${\ displaystyle Q}$

Q := Q − bit.bnot(Q)      -- Appropriate if −1 digits in Q are represented as zeros as is common.

Endelig er kvotienter beregnet af denne algoritme altid ulige, og resten i R er i området −D ≤ R <D. F.eks. 5 /2 = 3 R −1. For at konvertere til en positiv rest skal du udføre et enkelt gendannelsestrin, efter at Q er konverteret fra ikke-standardform til standardform:

if R < 0 then
  Q := Q − 1
  R := R + D  -- Needed only if the remainder is of interest.
end if

Den faktiske rest er R >> n. (Som med gendannelse af division, bruges lavordensbiterne af R i samme hastighed, som bits i kvotienten Q produceres, og det er almindeligt at bruge et enkelt skiftregister for begge.)

SRT division

SRT -division er opkaldt efter sine skabere (Sweeney, Robertson og Tocher) og er en populær metode til division i mange mikroprocessorimplementeringer . SRT-division ligner ikke-gendannende division, men den bruger en opslagstabel baseret på udbyttet og divisoren til at bestemme hvert kvotientciffer.

Den væsentligste forskel er, at der bruges en redundant repræsentation for kvotienten. For eksempel ved implementering af radix-4 SRT-division vælges hvert kvotientciffer blandt fem muligheder: {−2, −1, 0, +1, +2}. På grund af dette behøver valget af et kvoteciffer ikke at være perfekt; senere kvotientcifre kan rette for små fejl. (Eksempelvis er kvotcifferparene (0, +2) og (1, −2) ækvivalente, da 0 × 4 +2 = 1 × 4−2.) Denne tolerance gør det muligt at vælge kvotientcifre ved hjælp af kun få mest betydningsfulde dele af udbyttet og divisoren, snarere end at kræve en subtraktion i fuld bredde. Denne forenkling giver igen mulighed for at bruge en radix højere end 2.

Ligesom ikke-gendannende division er de sidste trin en sidste subtraktion i fuld bredde for at løse den sidste kvotientbit og konvertering af kvotienten til standard binær form.

Den Intel Pentium processorens berygtede floating-point division bug var forårsaget af en forkert kodet opslagstabel. Fem af de 1066 poster var fejlagtigt udeladt.

Hurtige opdelingsmetoder

Newton – Raphson division

Newton-Raphsons bruger Newtons metode til at finde den reciprokke af og formere at gensidig ved at finde den endelige kvotient .${\ displaystyle D}$${\ displaystyle N}$${\ displaystyle Q}$

Trinnene i Newton – Raphson division er:

1. Beregn et skøn for den gensidige afdeleren .${\ displaystyle X_ {0}}$${\ displaystyle 1/D}$${\ displaystyle D}$
2. Beregn successivt mere præcise skøn over det gensidige. Det er her, man anvender Newton – Raphson -metoden som sådan.${\ displaystyle X_ {1}, X_ {2}, \ ldots, X_ {S}}$
3. Beregn kvotienten ved at gange udbyttet ved den reciprokke værdi af divisor: .${\ displaystyle Q = NX_ {S}}$

For at anvende Newtons metode til at finde det gensidige af , er det nødvendigt at finde en funktion, der har et nul på . Den oplagte sådan funktion er , men Newton – Raphson -iterationen for dette er uhjælpsom, da den ikke kan beregnes uden allerede at kende det gensidige (den forsøger desuden at beregne den nøjagtige gensidige i et trin i stedet for at give mulighed for iterative forbedringer). En funktion, der virker, er , som Newton – Raphson -iterationen giver ${\ displaystyle D}$${\ displaystyle f (X)}$${\ displaystyle X = 1/D}$${\ displaystyle f (X) = DX-1}$${\ displaystyle D}$${\ displaystyle f (X) = (1/X) -D}$

${\ displaystyle X_ {i+1} = X_ {i}-{f (X_ {i}) \ over f '(X_ {i})} = X_ {i}-{1/X_ {i} -D \ over -1/X_ {i}^{2}} = X_ {i}+X_ {i} (1-DX_ {i}) = X_ {i} (2-DX_ {i}),}$

som kan beregnes ud fra kun at bruge multiplikation og subtraktion, eller ved hjælp af to fusionerede multiplier – tilføjelser . ${\ displaystyle X_ {i}}$

Fra et beregningsmæssigt synspunkt er udtrykkene og ikke ækvivalente. For at opnå et resultat med en præcision på 2 n bits, mens man gør brug af det andet udtryk, skal man beregne produktet mellem og med dobbelt den givne præcision på ( n bits). I modsætning hertil skal produktet mellem og kun beregnes med en præcision på n bits, fordi de førende n bits (efter det binære punkt) er nuller. ${\ displaystyle X_ {i+1} = X_ {i}+X_ {i} (1-DX_ {i})}$${\ displaystyle X_ {i+1} = X_ {i} (2-DX_ {i})}$${\ displaystyle X_ {i}}$${\ displaystyle (2-DX_ {i})}$${\ displaystyle X_ {i}}$${\ displaystyle X_ {i}}$${\ displaystyle (1-DX_ {i})}$${\ displaystyle (1-DX_ {i})}$

Hvis fejlen er defineret som , så: ${\ displaystyle \ varepsilon _ {i} = 1-DX_ {i}}$

${\ displaystyle {\ begin {align} \ varepsilon _ {i+1} & = 1-DX_ {i+1} \\ & = 1-D (X_ {i} (2-DX_ {i})) \\ & = 1-2DX_ {i}+D^{2} X_ {i}^{2} \\ & = (1-DX_ {i})^{2} \\ & = {\ varepsilon _ {i}} ^{2}. \\\ ende {tilpasset}}}$

Denne kvadrering af fejlen ved hvert iterationstrin-den såkaldte kvadratiske konvergens af Newton-Raphsons metode-har den virkning, at antallet af korrekte cifre i resultatet groft fordobles for hver iteration , en egenskab, der bliver ekstremt værdifuld, når de involverede tal har mange cifre (f.eks. i det store heltaldomæne). Men det betyder også, at den indledende konvergens af metoden kan være forholdsvis langsom, især hvis det oprindelige skøn er dårligt valgt. ${\ displaystyle X_ {0}}$

For delproblemet med at vælge et indledende skøn er det praktisk at anvende et bitskift på divisoren D for at skalere det, så 0,5 ≤  D  ≤ 1; ved at anvende det samme bitskift på tælleren N , sikrer man, at kvotienten ikke ændres. Så kunne man bruge en lineær tilnærmelse i formen ${\ displaystyle X_ {0}}$

${\ displaystyle X_ {0} = T_ {1}+T_ {2} D \ approx {\ frac {1} {D}} \,}$

at initialisere Newton – Raphson. For at minimere maksimumet af den absolutte værdi af fejlen ved denne tilnærmelse på interval , bør man bruge ${\ displaystyle [0.5,1]}$

${\ displaystyle X_ {0} = {48 \ over 17}-{32 \ over 17} D. \,}$

Koefficienterne for den lineære tilnærmelse bestemmes som følger. Fejlens absolutte værdi er . Minimumet af fejlens maksimale absolutte værdi bestemmes af Chebyshev -ækvivalenssætningen, der anvendes på . Det lokale minimum forekommer når , som har løsning . Funktionen på dette minimum skal være af modsat fortegn som funktion ved endepunkterne, nemlig, . De to ligninger i de to ukendte har en unik løsning og , og den maksimale fejl er . Ved hjælp af denne tilnærmelse er den absolutte værdi af fejlen i den oprindelige værdi mindre end ${\ displaystyle | \ varepsilon _ {0} | = | 1-D (T_ {1}+T_ {2} D) |}$${\ displaystyle F (D) = 1-D (T_ {1}+T_ {2} D)}$${\ displaystyle F (D)}$${\ displaystyle F '(D) = 0}$${\ displaystyle D = -T_ {1}/(2T_ {2})}$${\ displaystyle F (1/2) = F (1) =-F (-T_ {1}/(2T_ {2})))}$${\ displaystyle T_ {1} = 48/17}$${\ displaystyle T_ {2} =-32/17}$${\ displaystyle F (1) = 1/17}$

${\ displaystyle \ vert \ varepsilon _ {0} \ vert \ leq {1 \ over 17} \ ca. 0,059. \,}$

Det er muligt at generere en polynomisk tilpasning af graden større end 1, beregning af koefficienterne ved hjælp af Remez -algoritmen . Afvejningen er, at det første gæt kræver flere beregningscyklusser, men forhåbentlig i bytte for færre iterationer af Newton – Raphson.

Da konvergensen for denne metode er præcis kvadratisk, følger det

${\ displaystyle S = \ left \ lceil \ log _ {2} {\ frac {P+1} {\ log _ {2} 17}} \ right \ rceil \,}$

trin er nok til at beregne værdien op til binære steder. Dette vurderes til 3 for IEEE enkeltpræcision og 4 for både dobbelt præcision og dobbelt udvidede formater. ${\ displaystyle P \,}$

Pseudokode

Følgende beregner kvotienten af N og D med en præcision på P binære steder:

Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)
D' := D / 2e+1   // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2e+1
X := 48/17 − 32/17 × D'   // precompute constants with same precision as D
repeat ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$ times   // can be precomputed based on fixed P
    X := X + X × (1 - D' × X)
end
return N' × X

For eksempel, ved en dobbeltpræcision floating-point division, bruger denne metode 10 gange, 9 tilføjelser og 2 skift.

Variant Newton – Raphson division

Newton-Raphson-opdelingsmetoden kan ændres til at være lidt hurtigere som følger. Efter at have forskudt N og D, så D er i [0,5, 1,0], initialiseres med

${\ displaystyle X: = {\ frac {140} {33}}+D \ cdot \ venstre ({\ frac {-64} {11}}+D \ cdot {\ frac {256} {99}} \ højre ).}$

Dette er den bedste kvadratiske tilpasning til 1/ D og giver en absolut værdi af fejlen mindre end eller lig med 1/99. Det vælges at gøre fejlen lig med et omskaleret tredje ordens Chebyshev-polynom af den første slags. Koefficienterne skal være forudberegnede og hårdkodede.

Brug derefter en iteration i sløjfen, som kugler fejlen.

${\ displaystyle E: = 1-D \ cdot X}$

${\ displaystyle Y: = X \ cdot E}$

${\ displaystyle X: = X+Y+Y \ cdot E.}$

Den Y · E sigt er nyt.

Hvis sløjfen udføres, indtil X er enig med 1/ D på dens førende P -bits, vil antallet af iterationer ikke være mere end

${\ displaystyle \ left \ lceil \ log _ {3} \ left ({\ frac {P+1} {\ log _ {2} 99}} \ right) \ right \ rceil}$

hvilket er antallet af gange 99 skal kubes for at komme til 2 ^{P +1} . Derefter

${\ displaystyle Q: = N \ cdot X}$

er kvotienten til P bits.

Brug af polynom af højere grad i enten initialiseringen eller iterationen resulterer i en forringelse af ydeevnen, fordi de krævede ekstra multiplikationer ville blive brugt bedre på at udføre flere iterationer.

Goldschmidt division

Goldschmidt -divisionen (efter Robert Elliott Goldschmidt) bruger en iterativ proces med gentagne gange at multiplicere både udbytte og divisor med en fælles faktor F _i , valgt således, at divisoren konvergerer til 1. Dette får udbyttet til at konvergere til den efterspurgte kvotient Q :

${\ displaystyle Q = {\ frac {N} {D}} {\ frac {F_ {1}} {F_ {1}}} {\ frac {F_ {2}} {F_ {2}}} {\ frac {F _ {\ ldots}} {F _ {\ ldots}}}.}$

Trinene for Goldschmidt division er:

1. Generer et estimat for multiplikationsfaktoren F _i .
2. Multiplicer udbyttet og divisoren med F _i .
3. Hvis divisoren er tilstrækkeligt tæt på 1, returneres udbyttet, ellers går du videre til trin 1.

Forudsat at N / D er blevet skaleret, så 0 <  D  <1, er hver F _i baseret på D :

${\ displaystyle F_ {i+1} = 2-D_ {i}.}$

Multiplicering af udbytte og divisor med faktorudbyttet:

${\ displaystyle {\ frac {N_ {i+1}} {D_ {i+1}}} = {\ frac {N_ {i}} {D_ {i}}} {\ frac {F_ {i+1} } {F_ {i+1}}}.}$

Efter et tilstrækkeligt antal k iterationer . ${\ displaystyle Q = N_ {k}}$

Goldschmidt -metoden bruges i AMD Athlon CPU'er og senere modeller. Det er også kendt som Anderson Earle Goldschmidt Powers (AEGP) algoritme og implementeres af forskellige IBM -processorer. Selvom den konvergerer i samme hastighed som en Newton – Raphson -implementering, er en fordel ved Goldschmidt -metoden, at multiplikationerne i tælleren og i nævneren kan udføres parallelt.

Binomial sætning

Goldschmidt -metoden kan bruges med faktorer, der tillader forenklinger ved hjælp af binomial sætningen . Antag, at N/D er blevet skaleret med en styrke på to, således at . Vi vælger og . Dette giver ${\ displaystyle D \ in ({\ tfrac {1} {2}}, 1]}$${\ displaystyle D = 1-x}$${\ displaystyle F_ {i} = 1+x^{2^{i}}}$

${\ displaystyle {\ frac {N} {1-x}} = {\ frac {N \ cdot (1+x)} {1-x^{2}}} = {\ frac {N \ cdot (1+ x) \ cdot (1+x^{2})} {1-x^{4}}} = \ cdots = Q '= {\ frac {N' = N \ cdot (1+x) \ cdot (1 +x^{2}) \ cdot \ cdot \ cdot (1+x^{2^{(n-1)}})} {D '= 1-x^{2^{n}} \ ca. 1} }}$.

Efter trin kan nævneren afrundes til med en relativ fejl${\ displaystyle n}$${\ displaystyle (x \ in [0, {\ tfrac {1} {2}}))}$${\ displaystyle 1-x^{2^{n}}}$${\ displaystyle 1}$

${\ displaystyle \ varepsilon _ {n} = {\ frac {Q'-N '} {Q'}} = x^{2^{n}}}$

hvilket er maksimalt når , hvilket giver en minimumspræcision af binære cifre. ${\ displaystyle 2^{-2^{n}}}$${\ displaystyle x = {1 \ over 2}}$${\ displaystyle 2^{n}}$

Stort heltal metoder

Metoder designet til hardwareimplementering skalerer generelt ikke til heltal med tusinder eller millioner af decimalcifre; disse forekommer ofte f.eks. i modulære reduktioner i kryptografi . For disse store heltal transformerer mere effektive divisionsalgoritmer problemet til at bruge et lille antal multiplikationer, som derefter kan udføres ved hjælp af en asymptotisk effektiv multiplikationsalgoritme, såsom Karatsuba -algoritmen , Toom – Cook -multiplikation eller Schönhage – Strassen -algoritmen . Resultatet er, at opdelingens kompleksitet er af samme rækkefølge (op til en multiplikativ konstant) som multiplikationens. Eksempler omfatter reduktion til multiplikation ved Newtons metode som beskrevet ovenfor , samt den lidt hurtigere Burnikel-Ziegler-division , Barrett-reduktion og Montgomery-reduktionsalgoritmer . Newtons metode er særlig effektiv i scenarier, hvor man skal dividere med den samme divisor mange gange, da der efter den første Newton -inversion kun er nødvendig en (afkortet) multiplikation for hver division.

Division med en konstant

Delingen med en konstant D svarer til multiplikationen med dens gensidige . Da nævneren er konstant, er dens gensidige (1/ D ) det samme. Det er således muligt at beregne værdien af (1 / D ) en gang påkompileringstidspunktet, og under kørslen udføre multiplikation N · (1 / D ) snarere end division N / D . I floating-point aritmetik giver brugen af ​​(1/ D ) lidt problemer, men i heltal aritmetik vil det gensidige altid evaluere til nul (forudsat | D |> 1).

Det er ikke nødvendigt at bruge specifikt (1/ D ); enhver værdi ( X / Y ), der reducerer til (1 / D ), kan bruges. For eksempel ved division med 3 kan faktorerne 1/3, 2/6, 3/9 eller 194/582 bruges. Følgelig, hvis Y var en effekt på to, ville divisionstrinnet reducere til et hurtigt højre bitskift. Effekten af ​​at beregne N / D som ( N · X ) / Y erstatter en division med en multiplikation og et skift. Bemærk, at parenteserne er vigtige, da N · ( X / Y ) evalueres til nul.

Medmindre D selv er en power på to, er der imidlertid ikke X og Y, der opfylder betingelserne ovenfor. Heldigvis giver ( N · X ) / Y nøjagtig det samme resultat som N / D i heltal aritmetik, selv når ( X / Y ) ikke ligefrem er lig med 1 / D , men "tæt nok" til, at fejlen, der indføres ved tilnærmelsen, er i de bits, der kasseres ved skiftoperationen.

Som et konkret aritmetisk eksempel med fast punkt kan 32-bit usignerede heltal divideres med 3 erstattes med en gange med2863311531/2 ³³, en multiplikation med 2863311531 ( hexadecimal 0xAAAAAAAB) efterfulgt af et 33 bit bit skift. Værdien af ​​2863311531 er beregnet som2 ³³/3, derefter afrundet. Ligeledes kan division med 10 udtrykkes som en multiplikation med 3435973837 (0xCCCCCCCD) efterfulgt af division med 2 ³⁵ (eller 35 højre bitskift ). OEIS leverer sekvenser af konstanterne til multiplikation som A346495 og til højre skift som A346496 .

For generel -bit usigneret heltal division, hvor divisoren ikke er en effekt på 2, konverterer den følgende identitet divisionen til to -bit addition/subtraktion, en -bit ved -bit multiplikation (hvor kun den øverste halvdel af resultatet bruges) og flere skift efter forberegning og : ${\ displaystyle x}$${\ displaystyle D}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle k = x+\ lceil \ log _ {2} {D} \ rceil}$${\ displaystyle a = \ left \ lceil {\ frac {2^{k}} {D}} \ right \ rceil -2^{x}}$

${\ displaystyle \ left \ lfloor {\ frac {N} {D}} \ right \ rfloor = \ left \ lfloor {\ frac {\ left \ lfloor {\ frac {Nb} {2}} \ right \ rfloor +b } {2^{kx-1}}} \ right \ rfloor}$ hvor ${\ displaystyle b = \ left \ lfloor {\ frac {Na} {2^{x}}} \ right \ rfloor}$

I nogle tilfælde kan division med en konstant opnås på endnu kortere tid ved at konvertere "multiplicere med en konstant" til en række skift og tilføjer eller trækker fra . Af særlig interesse er division med 10, for hvilken den nøjagtige kvotient opnås, med resten om nødvendigt.

Afrundingsfejl

Afrundingsfejl kan indføres ved divisionsoperationer på grund af begrænset præcision .

Se også

• Bygning division
• Multiplikationsalgoritme
• Pentium FDIV fejl

Noter

Referencer

Yderligere læsning

• Savard, John JG (2018) [2006]. "Avancerede aritmetiske teknikker" . quadibloc . Arkiveret fra originalen 2018-07-03 . Hentet 2018-07-16 .