Algoritmus dělení - Division algorithm

A algoritmus dělení je algoritmus které, vzhledem k tomu, dvě celá čísla N a D, počítá jejich kvocient a / nebo zbytek, výsledek Euklidovské dělení. Některé jsou aplikovány ručně, zatímco jiné jsou využívány návrhy digitálních obvodů a softwarem.

Algoritmy dělení spadají do dvou hlavních kategorií: pomalé dělení a rychlé dělení. Algoritmy pomalého dělení vytvářejí jednu číslici konečného kvocientu na iteraci. Mezi příklady pomalého dělení patří obnovení, neprovedení obnovy, neobnovovat, a SRT divize. Metody rychlého dělení začínají těsnou aproximací konečného kvocientu a při každé iteraci produkují dvakrát tolik číslic konečného kvocientu. Newton – Raphson a Goldschmidt algoritmy spadají do této kategorie.

Varianty těchto algoritmů umožňují rychlé použití multiplikační algoritmy. Výsledkem je, že u velkých celých čísel počítačový čas potřebné pro dělení je stejné, až do konstantního faktoru, jako čas potřebný pro násobení, podle toho, který algoritmus násobení je použit.

Diskuse bude odkazovat na formulář ${ displaystyle N / D = (Q, R)}$, kde

• N = Čitatel (dividenda)
• D = Jmenovatel (dělitel)

je vstup a

• Q = Kvocient
• R = Zbývající část

je výstup.

Dělení opakovaným odečtením

Nejjednodušší algoritmus dělení, historicky začleněný do a největší společný dělitel algoritmus uvedený v Euklidova Elementy, Kniha VII, Proposition 1, najde zbytek daná dvě kladná celá čísla pouze pomocí odečtení a srovnání:

zatímco N ≥ D dělat  N := N − Dkonecvrátit se N

Důkaz, že podíl a zbytek existují a jsou jedinečné (popsáno na Euklidovské dělení ) dává vzniknout úplnému algoritmu dělení pomocí sčítání, odčítání a porovnávání:

funkce rozdělit(N, D)  -li D = 0 pak chyba(Dělení nulou) konec  -li D < 0 pak (Q, R) := rozdělit(N, −D); vrátit se (−Q, R) konec  -li N < 0 pak    (Q,R) := rozdělit(−N, D)    -li R = 0 pak vrátit se (−Q, 0)    jiný vrátit se (−Q − 1, D − R) konec  konec  - V tomto okamžiku N ≥ 0 a D> 0  vrátit se divide_unsigned(N, D)konec  funkce divide_unsigned(N, D)  Q := 0; R := N  zatímco R ≥ D dělat    Q := Q + 1    R := R − D  konec  vrátit se (Q, R)konec

Tento postup vždy produkuje R ≥ 0. I když je velmi jednoduchý, vyžaduje kroky Ω (Q), a je tedy exponenciálně pomalejší než dokonce i algoritmy pomalého dělení, jako je dlouhé dělení. Je užitečné, pokud je známo, že Q je malý (je to algoritmus citlivý na výstup ) a může sloužit jako spustitelná specifikace.

Dlouhé dělení

Dlouhé dělení je standardní algoritmus používaný pro dělení víceciferných čísel vyjádřených v desítkové soustavě perem a papírem. Postupně se posouvá z levého na pravý konec dividendy a v každé fázi odečte největší možný násobek dělitele (na úrovni číslic); násobky se pak stanou číslicemi kvocientu a konečný rozdíl je pak zbytek.

Při použití s ​​binárním radixem tvoří tato metoda základ pro (nepodepsané) celočíselné dělení s níže uvedeným algoritmem zbytku. Krátké dělení je zkrácená forma dlouhého dělení vhodná pro jednociferné dělitele. Kouskování - také známá jako metoda částečných kvocientů nebo metoda kata - je méně efektivní forma dlouhého dělení, která může být snáze srozumitelná. Tím, že umožníte jednomu odečíst více násobků, než jaké má aktuálně v každé fázi, lze také vyvinout volnější variantu dlouhého dělení^[1]

Celé dělení (bez znaménka) se zbytkem

Následující algoritmus, binární verze slavného dlouhé rozdělení, se rozdělí N podle D, umístění kvocientu dovnitř Q a zbytek v R. V následujícím kódu jsou všechny hodnoty považovány za celá čísla bez znaménka.

-li D = 0 pak chyba(DivisionByZeroException) konecQ := 0                  - Inicializujte kvocient a zbytek na nuluR := 0                     pro i := n − 1 .. 0 dělat  - Kde n je počet bitů v N  R := R << 1           - Levý posun R o 1 bit  R(0) := N(i)          - Nastavte nejméně významný bit R rovný bitu čitatele  -li R ≥ D pak    R := R − D    Q(i) := 1  koneckonec

Příklad

Vezmeme-li N = 1100₂ (12₁₀) a D = 100₂ (4₁₀)

Krok 1: Nastavte R = 0 a Q = 0
Krok 2: Vezměte i = 3 (jeden menší než počet bitů v N)
Krok 3: R = 00 (vlevo posunuto o 1)
Krok 4: R = 01 (nastavení R (0) až N (i))
Krok 5: R

Krok 2: Nastavit i = 2
Krok 3: R = 010
Krok 4: R = 011
Krok 5: R

Krok 2: Nastavit i = 1
Krok 3: R = 0110
Krok 4: R = 0110
Krok 5: R> = D, výpis zadán
Krok 5b: R = 10 (R − D)
Krok 5c: Q = 10 (nastavení Q (i) na 1)

Krok 2: Nastavit i = 0
Krok 3: R = 100
Krok 4: R = 100
Krok 5: R> = D, výpis zadán
Krok 5b: R = 0 (R − D)
Krok 5c: Q = 11 (nastavení Q (i) na 1)

konec
Q = 11₂ (3₁₀) a R = 0.

Metody pomalého dělení

Metody pomalého dělení jsou založeny na standardní rovnici opakování ^[2]

${ displaystyle R_ {j + 1} = B krát R_ {j} -q_ {n- (j + 1)} krát D ,}$,

kde:

• R_j je j-th částečný zbytek divize
• B je základ (základ, obvykle 2 interně v počítačích a kalkulačkách)
• q _{n − (j + 1)} je číslice kvocientu v poloze n− (j + 1), kde jsou pozice číslic očíslovány od nejméně významné 0 do nejvýznamnější n−1
• n je počet číslic v kvocientu
• D je dělitel

Obnovuje se rozdělení

Obnovující divize pokračuje pevný bod zlomková čísla a závisí na předpokladu 0 < D < N.^{[Citace je zapotřebí ]}

Číslice kvocientu q jsou tvořeny ze sady číslic {0,1}.

Základní algoritmus pro binární (radix 2) obnovující dělení je:

R := ND := D << n            - R a D potřebují dvojnásobnou šířku slova než N a Qpro i := n − 1 .. 0 dělat  - Například 31..0 pro 32 bitů  R := 2 * R − D          - Zkušební odčítání od posunuté hodnoty (násobení 2 je posun v binární reprezentaci)  -li R ≥ 0 pak    q(i) := 1          - Výsledkový bit 1  jiný    q(i) := 0          - Výsledný bit 0    R := R + D         - Nový částečný zbytek je (obnovená) posunutá hodnota  koneckonec- Kde: N = čitatel, D = jmenovatel, n = #bity, R = částečný zbytek, q (i) = bit #i kvocientu

Výše uvedený algoritmus obnovení dělení se může vyhnout kroku obnovení uložením posunuté hodnoty 2R před odečtením v dalším registru T (tj., T = R << 1) a kopírování registru T na R když je výsledek odečtení 2R − D je negativní.

Neprovádějící obnovovací dělení je podobné jako obnovení dělení kromě toho, že je uložena hodnota 2R, takže D není třeba přidávat zpět pro případ R <0.

Neobnovující se rozdělení

Neobnovující dělení používá pro číslice kvocientu místo {0, 1} sadu číslic {−1, 1}. Algoritmus je složitější, ale má tu výhodu, když je implementován do hardwaru, že existuje pouze jedno rozhodnutí a sčítání / odčítání na kvocientový bit; po odečtení neexistuje žádný krok obnovy, který potenciálně snižuje počet operací až o polovinu a umožňuje rychlejší provedení.^[3] Základní algoritmus pro binární (radix 2) neobnovující dělení nezáporných čísel je:

R := ND := D << n            - R a D potřebují dvojnásobnou šířku slova než N a Qpro i = n − 1 .. 0 dělat  - například 31..0 pro 32 bitů  -li R >= 0 pak    q[i] := +1    R := 2 * R − D  jiný    q[i] := −1    R := 2 * R + D  konec -likonec - Poznámka: N = čitatel, D = jmenovatel, n = # bitů, R = částečný zbytek, q (i) = bit #i kvocientu.

Podle tohoto algoritmu je kvocient v nestandardní formě skládající se z číslic −1 a +1. Tento formulář je třeba převést na binární, aby se vytvořil konečný kvocient. Příklad:

Převést následující kvocient na sadu číslic {0,1}:
Start:	${ displaystyle Q = 111 { bar {1}} 1 { bar {1}} 1 { bar {1}}}$
1. Vytvořte pozitivní termín:	${ displaystyle P = 11101010 ,}$
2. Zamaskujte negativní výraz *:	${ displaystyle M = 00010101 ,}$
3. Odečíst: ${ displaystyle P-M}$:	${ displaystyle Q = 11010101 ,}$
*. (Podepsaná binární notace s Jeden doplněk bez Doplněk dvou )

Pokud -1 číslice ${ displaystyle Q}$ jsou poté uloženy jako nuly (0) ${ displaystyle P}$ je ${ displaystyle Q}$ a výpočetní technika ${ displaystyle M}$ je triviální: provést něčí doplněk (kousek po kousku) na originálu ${ displaystyle Q}$.

Q := Q − bit.bnot(Q)      * Odpovídající -li −1 Číslice v Q jsou Zastoupeno tak jako nuly tak jako je běžný.

Nakonec jsou podíly vypočítané tímto algoritmem vždy liché a zbytek v R je v rozsahu −D ≤ R po Q se převede z nestandardního formuláře na standardní formulář:

-li R < 0 pak  Q := Q − 1  R := R + D  - Nutné pouze v případě, že je o Zájmena zájem.konec -li

Skutečný zbytek je R >> n. (Stejně jako u obnovovacího dělení jsou bity R řádu nižšího řádu spotřebovány stejnou rychlostí jako jsou vytvářeny bity kvocientu Q a pro oba je běžné používat jeden posuvný registr.)

SRT divize

Divize SRT, pojmenovaná pro své tvůrce (Sweeney, Robertson a Tocher), je populární metodou pro dělení v mnoha mikroprocesor implementace.^[4][5] SRT divize je podobná neobnovující divizi, ale používá a vyhledávací tabulka na základě dividendy a dělitele k určení každé číslice kvocientu.

Nejvýznamnějším rozdílem je, že a nadbytečné zastoupení se používá pro kvocient. Například při implementaci dělení radix-4 SRT se vybírá každá číslice kvocientu Pět možnosti: {−2, −1, 0, +1, +2}. Z tohoto důvodu nemusí být volba číslice kvocientu dokonalá; pozdější číslice kvocientu mohou opravit drobné chyby. (Například páry digitálních kvocientů (0, +2) a (1, −2) jsou ekvivalentní, protože 0 × 4 + 2 = 1 × 4-2.) Tato tolerance umožňuje vybrat číslice kvocientu pouze pomocí několika nejvýznamnější bity dividendy a dělitele, spíše než vyžadovat odečítání celé šířky. Toto zjednodušení zase umožňuje použít radix vyšší než 2.

Stejně jako neobnovující dělení jsou závěrečné kroky konečným odečtením celé šířky k vyřešení posledního kvocientu kvocientu a převodem kvocientu do standardní binární formy.

The Intel Pentium procesor je neslavný chyba dělení s plovoucí desetinnou čárkou byla způsobena nesprávně kódovanou vyhledávací tabulkou. Pět z 1066 záznamů bylo omylem vynecháno.^[6][7]

Metody rychlého dělení

Divize Newton – Raphson

Newton – Raphson používá Newtonova metoda najít reciproční z ${ displaystyle D}$ a vynásobte to vzájemně ${ displaystyle N}$ najít konečný kvocient ${ displaystyle Q}$.

Kroky divize Newton – Raphson jsou:

1. Vypočítejte odhad ${ displaystyle X_ {0}}$ pro reciproční ${ displaystyle 1 / D}$ dělitele ${ displaystyle D}$.
2. Postupně počítejte přesnější odhady ${ displaystyle X_ {1}, X_ {2}, ldots, X_ {S}}$ vzájemnosti. Zde se používá metoda Newton – Raphson jako taková.
3. Vypočítejte kvocient vynásobením dividendy převrácenou hodnotou dělitele: ${ displaystyle Q = NX_ {S}}$.

Aby bylo možné použít Newtonovu metodu k nalezení převrácené hodnoty ${ displaystyle D}$, je nutné najít funkci ${ displaystyle f (X)}$ který má nulu na ${ displaystyle X = 1 / D}$. Zřejmá taková funkce je ${ displaystyle f (X) = DX-1}$, ale Newton-Raphsonova iterace pro toto je neužitečná, protože ji nelze vypočítat, aniž bychom již neznali převrácenou hodnotu ${ displaystyle D}$ (navíc se pokouší spočítat přesný reciproční v jednom kroku, místo aby umožnil iterativní vylepšení). Funkce, která funguje, je ${ displaystyle f (X) = (1 / X) -D}$, což dává iterace Newton – Raphson

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

ze kterého lze vypočítat ${ displaystyle X_ {i}}$ pomocí pouze násobení a odčítání nebo pomocí dvou fúzované násobení - dodává.

Z hlediska výpočtu výrazy ${ displaystyle X_ {i + 1} = X_ {i} + X_ {i} (1-DX_ {i})}$ a ${ displaystyle X_ {i + 1} = X_ {i} (2-DX_ {i})}$ nejsou ekvivalentní. Získání výsledku s přesností 2n bitů při použití druhého výrazu je třeba vypočítat součin mezi ${ displaystyle X_ {i}}$ a ${ displaystyle (2-DX_ {i})}$ s dvojnásobnou přesností ${ displaystyle X_ {i}}$(n bitů).^{[Citace je zapotřebí ]} Naproti tomu produkt mezi ${ displaystyle X_ {i}}$ a ${ displaystyle (1-DX_ {i})}$ je třeba počítat pouze s přesností n bity, protože vedoucí n bitů (za binárním bodem) ${ displaystyle (1-DX_ {i})}$ jsou nuly.

Pokud je chyba definována jako ${ displaystyle varepsilon _ {i} = 1-DX_ {i}}$, pak:

${ displaystyle { begin {aligned} 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}. end {zarovnáno}}}$

Toto druhou mocninu chyby v každém iteračním kroku - tzv kvadratická konvergence Newton - Raphsonova metoda - má za následek, že počet správných číslic ve výsledku zhruba zdvojnásobí pro každou iteraci, vlastnost, která se stává nesmírně cennou, když mají zúčastněná čísla mnoho číslic (např. v doméně velkých celých čísel). Znamená to však také, že počáteční konvergence metody může být poměrně pomalá, zejména pokud se jedná o počáteční odhad ${ displaystyle X_ {0}}$ je špatně vybrán.

Pro dílčí problém výběru počátečního odhadu ${ displaystyle X_ {0}}$, je vhodné použít na dělitele bitový posun D měřítko tak, aby 0,5 ≤D ≤ 1; použitím stejného bitového posunu v čitateli N, jeden zajistí, že kvocient se nezmění. Pak by se dalo použít lineární přiblížení ve formě

${ displaystyle X_ {0} = T_ {1} + T_ {2} D přibližně { frac {1} {D}} ,}$

inicializovat Newton – Raphson. Minimalizovat maximum absolutní hodnoty chyby této aproximace na intervalu ${ displaystyle [0,5,1]}$, jeden by měl použít

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

Koeficienty lineární aproximace se stanoví následovně. Absolutní hodnota chyby je ${ displaystyle | varepsilon _ {0} | = | 1-D (T_ {1} + T_ {2} D) |}$. Minimum maximální absolutní hodnoty chyby je určeno pomocí Čebyševova ekvioscilační věta aplikován na ${ displaystyle F (D) = 1-D (T_ {1} + T_ {2} D)}$. Místní minimum ${ displaystyle F (D)}$ nastane, když ${ displaystyle F '(D) = 0}$, který má řešení ${ displaystyle D = -T_ {1} / (2T_ {2})}$. Funkce na tomto minimu musí mít opačné znaménko jako funkce v koncových bodech, jmenovitě, ${ displaystyle F (1/2) = F (1) = - F (-T_ {1} / (2T_ {2}))}$. Dvě rovnice ve dvou neznámých mají jedinečné řešení ${ displaystyle T_ {1} = 48/17}$ a ${ displaystyle T_ {2} = - 32/17}$a maximální chyba je ${ displaystyle F (1) = 1/17}$. Při použití této aproximace je absolutní hodnota chyby počáteční hodnoty menší než

${ displaystyle vert varepsilon _ {0} vert leq {1 nad 17} přibližně 0,059. ,}$

Je možné vygenerovat polynomiální přizpůsobení stupně většího než 1, výpočet koeficientů pomocí Remezův algoritmus. Kompromisem je, že počáteční odhad vyžaduje více výpočetních cyklů, ale doufejme, že výměnou za méně iterací Newton – Raphson.

Protože pro tuto metodu konvergence je přesně kvadratický, z toho vyplývá

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

kroky stačí k výpočtu hodnoty až ${ displaystyle P ,}$ binární místa. To odpovídá hodnotám 3 pro IEEE jediná přesnost a 4 pro oba dvojnásobná přesnost a dvojité prodloužení formáty.

Pseudo kód

Následující výpočet kvocientu N a D s přesností na P binární místa:

Express D jako M × 2E kde 1 ≤ M <2 (standardní reprezentace s plovoucí desetinnou čárkou) D ': = D / 2e + 1   // měřítko mezi 0,5 a 1, lze provést s bitovým posunem / odečtením exponentuN ': = N / 2e + 1X: = 48/17 - 32/17 × D ' // předpočítá konstanty se stejnou přesností jako D.opakovat ${ displaystyle  left  lceil  log _ {2} { frac {P + 1} { log _ {2} 17}}  right  rceil ,}$ krát   // lze předpočítat na základě pevného P    X: = X + X × (1 - D '× X)konecvrátit se N '× X

Například pro dělení s plovoucí desetinnou čárkou s dvojitou přesností používá tato metoda 10 násobení, 9 přidání a 2 posuny.

Varianta Newton – Raphsonova divize

Metodu dělení Newton-Raphson lze upravit tak, aby byla mírně rychlejší, a to následujícím způsobem. Po přeřazení N a D aby D je v [0,5, 1,0], inicializujte pomocí

${ displaystyle X: = { frac {140} {33}} + D cdot vlevo ({ frac {-64} {11}} + D cdot { frac {256} {99}} vpravo ).}$

Toto je nejlepší kvadratické přizpůsobení 1 /D a udává absolutní hodnotu chyby menší nebo rovnou 1/99. Je vybráno tak, aby se chyba rovnala změněnému třetímu řádu Čebyševův polynom prvního druhu. Koeficienty by měly být předem vypočítány a pevně zakódovány.

Pak ve smyčce použijte iteraci, která krychli chybu.

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

${ displaystyle Y: = X cdot E}$

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

The Y·E termín je nový.

Pokud je smyčka provedena, dokud X nesouhlasí s 1 /D na jeho čele P bitů, pak počet iterací nebude větší než

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

což je počet, kolikrát 99 musí být krychlový, aby se dostal na 2^P+1. Pak

${ displaystyle Q: = N cdot X}$

je podíl k P bity.

Použití polynomů vyššího stupně při inicializaci nebo iteraci vede ke snížení výkonu, protože potřebné vícenásobné násobení by bylo lépe vynaloženo na provádění více iterací.

Divize Goldschmidt

Divize Goldschmidt^[8] (po Robertu Elliottu Goldschmidtovi^[9]) používá iterativní proces opakovaného vynásobení dividendy i dělitele společným faktorem F_i, zvoleno tak, že dělitel konverguje k 1. To způsobí, že dividenda konverguje k hledanému kvocientu Q:

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

Kroky pro divizi Goldschmidt jsou:

1. Vygenerujte odhad multiplikačního faktoru F_i .
2. Vynásobte dividendu a dělitele F_i .
3. Pokud je dělitel dostatečně blízko 1, vraťte dividendu, jinak proveďte smyčku ke kroku 1.

Za předpokladu N/D byl změněn tak, aby 0 <D <1, každý F_i je založeno na D:

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

Vynásobením dividendy a dělitele výnosy faktoru:

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

Po dostatečném počtu k iterací ${ displaystyle Q = N_ {k}}$.

Metoda Goldschmidt se používá v AMD CPU Athlon a novější modely.^[10][11] Je také známý jako algoritmus Anderson Earle Goldschmidt Powers (AEGP) a je implementován různými procesory IBM.^[12][13]

Binomická věta

Metodu Goldschmidt lze použít s faktory, které umožňují zjednodušení pomocí binomická věta Předpokládejme, že měřítko N / D bylo změněno a síla dvou takhle ${ displaystyle D in ({ tfrac {1} {2}}, 1]}$.Vybíráme si ${ displaystyle D = 1-x}$ a ${ displaystyle F_ {i} = 1 + x ^ {2 ^ {i}}}$.To je výnos

${ 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}} přibližně 1} }}$.

Po ${ displaystyle n}$ kroky ${ displaystyle (x v [0, { tfrac {1} {2}}))}$, jmenovatel ${ displaystyle 1-x ^ {2 ^ {n}}}$ lze zaokrouhlit na ${ displaystyle 1}$ s relativní chyba

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

což je maximum na ${ displaystyle 2 ^ {- 2 ^ {n}}}$ když ${ displaystyle x = {1 nad 2}}$, čímž poskytuje minimální přesnost ${ displaystyle 2 ^ {n}}$ binární číslice.

Metody velkých celých čísel

Metody navržené pro implementaci hardwaru se obecně nezmění na celá čísla s tisíci nebo miliony desetinných míst; ty se často vyskytují například v modulární snížení v kryptografie. U těchto velkých celých čísel efektivnější dělící algoritmy transformují problém tak, aby používal malý počet násobení, které lze poté provést pomocí asymptoticky účinného multiplikační algoritmus tak jako Algoritmus Karatsuba, Násobení Toom – Cook nebo Schönhage – Strassenův algoritmus. Výsledkem je, že výpočetní složitost dělení je stejného řádu (až do multiplikativní konstanty) jako násobení. Mezi příklady patří redukce na násobení pomocí Newtonova metoda tak jako popsáno výše,^[14] stejně jako o něco rychlejší Barrettova redukce a Montgomeryho redukce algoritmy.^{[15][je nutné ověření ]} Newtonova metoda je obzvláště účinná ve scénářích, kdy je třeba mnohokrát dělit stejným dělitelem, protože po počáteční Newtonově inverzi je pro každé dělení potřeba pouze jedno (zkrácené) násobení.

Dělení konstantou

Dělení konstantou D je ekvivalentní násobení jeho reciproční. Jelikož je jmenovatel konstantní, je i jeho reciproční (1 /D). Je tedy možné vypočítat hodnotu (1 /D) jednou v době kompilace a v době běhu proveďte násobení N·(1/D) spíše než rozdělení N / D. v plovoucí bod aritmetika použití (1 /D) představuje malý problém, ale v celé číslo aritmetika bude reciproční vždy vyhodnocovat na nulu (za předpokladu |D| > 1).

Není nutné používat konkrétně (1 /D); libovolná hodnota (X/Y), která se sníží na (1 /D) může být použit. Například pro dělení 3 lze použít faktory 1/3, 2/6, 3/9 nebo 194/582. V důsledku toho, pokud Y byla síla dvou, krok dělení by se snížil na rychlý posun bitů doprava. Účinek výpočtu N/D tak jako (N·X)/Y nahradí divizi násobením a posunem. Všimněte si, že závorky jsou důležité, protože N·(X/Y) vyhodnotí na nulu.

Nicméně pokud D sama o sobě je síla dvou, není X a Y který splňuje výše uvedené podmínky. Naštěstí, (N·X)/Y dává přesně stejný výsledek jako N/D v celočíselné aritmetice, i když (X/Y) není přesně rovno 1 /D, ale „dostatečně blízko“, že chyba zavedená aproximací je v bitech, které jsou zahozeny operací posunu.^[16][17][18]

Jako beton aritmetika s pevným bodem například pro 32bitová celá čísla bez znaménka lze dělení 3 nahradit násobením 2863311531/2³³, násobení 2863311531 (hexadecimální 0xAAAAAAAB) následovaný 33bitovým posunem doprava. Hodnota 2863311531 se počítá jako 2³³/3, pak zaokrouhleno nahoru.

Podobně dělení 10 lze vyjádřit jako násobení 3435973837 (0xCCCCCCCD) následované dělením 2³⁵ (nebo 35 pravý bitový posun).

V některých případech lze dělení konstantou dosáhnout za ještě kratší dobu převedením „násobení konstantou“ na série posunů a sčítání nebo odčítání.^[19] Zvláště zajímavé je dělení 10, pro které se získá přesný kvocient, se zbytkem v případě potřeby.^[20]

Chyba zaokrouhlování

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Září 2012)

Chyba zaokrouhlování mohou být zavedeny divizními operacemi kvůli omezenému přesnost.

Viz také

• Divize kuchyně
• Algoritmus násobení
• Chyba Pentium FDIV

Reference

Další čtení

• Warren Jr., Henry S. (2013). Hacker's Delight (2. vyd.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8.
• Savard, John J. G. (2018) [2006]. „Pokročilé aritmetické techniky“. quadibloc. Archivováno z původního dne 2018-07-03. Citováno 2018-07-16.