Division

Den division er en matematisk operation, som, med to tal en og b, associerer et tredje tal ( lov af intern sammensætning ), kaldet kvotient eller forhold , og som kan skrives:

a : b ;
a ÷ b ( obelus );
a / b ( skråstreg , stregfraktion );
${\ frac {a} {b}}$ ( brøkdel ).

I en første tilgang kan vi se størrelsen a ÷ b som en adskillelse af størrelsen a i b lige store dele. Men denne tilgang er især velegnet til opdelingen mellem heltal, hvor begrebet mængde er ret intuitivt. Vi skelner ofte den "nøjagtige" opdeling (den, vi taler om her) fra "med resten" -delingen (den euklidiske division ). Fra et praktisk synspunkt kan vi se division som produkt af det første ved det omvendte af det andet. Hvis et tal ikke er nul, er funktionen "division med dette tal" den gensidige funktion af funktionen " multiplikation med dette tal". Dette gør det muligt at bestemme et antal egenskaber ved operationen.

Mere generelt kan vi definere kvotienten y = a / b som værende løsningen af ligningen b × y = a . Dette gør det muligt at udvide definitionen til andre matematiske objekter end tal til alle elementerne i en ring .

Problematisk

Divisionen tjener:

at foretage en ligelig opdeling mellem et antal enheder, der er bestemt på forhånd og derfor at bestemme størrelsen på en enhed. For eksempel :

Spørgsmål: Hvis vi fordeler 500 gram perlimpimpinpulver ligeligt mellem otte personer, hvor meget får hver af dem? Svar : hver får 62,5 gram perlimpimpinpulver

{\ dfrac {500} {8}} = 62.5

at bestemme det mulige antal aktier af en størrelse, der er bestemt på forhånd. For eksempel :

Spørgsmål: Hvis vi distribuerer 500 gram perlimpimpinpulver pr. 70 g skive , hvor mange mennesker kan vi da servere? Svar :, vi kan tjene 7 personer, og der vil være nok til at tjene 1/7 af en person (≈ 0,14).

{\ dfrac {500} {70}} = 7,14 \ ldots

Multiplikation er også udtryk for en proportional lov . Opdelingen gør det derfor muligt at "vende om" denne lov. For eksempel ved vi, at vægten P (kraft, der trækker et objekt nedad, udtrykt i newton) på et givet sted er proportional med massen m (fast mængde, udtrykt i kg), idet proportionalitetskoefficienten kaldes "Gravity" g:

P = m × g

En badeværelsesvægt måler den kraft, der udøves på den, derfor P; når tyngdekraften er kendt, kan vi udlede massen af en person ved at invertere loven ved en division:

m = P / g.

I samme rækkefølge af ideer, i tilfælde af en ensartet retlinet bevægelse , er den tilbagelagte afstand d (i kilometer) proportional med tiden t (i timer), hvor koefficienten er den gennemsnitlige hastighed v (i kilometer i timen):

d = v × t .

Vi kan vende denne lov for at bestemme den tid, det tager at køre en given afstand med en given gennemsnitshastighed:

t = d / v .

Mere generelt griber inddelingen i inversionen af en affin lov , det vil sige af typen

y = økse + b

hvilket giver, hvis a er ikke-nul

x = ( y - b ) / a

Derudover kan vi nærme os de fleste af lovene ved hjælp af en affin lov ved at gøre en udvidelse begrænset til rækkefølge 1. Opdelingen gør det således muligt at invertere en lov på en omtrentlig måde: hvis vi kender værdien af ƒ og dens afledte ved en punkt x 0 , kan vi skrive "omkring dette punkt"

y = ƒ ( x ) ≈ ƒ ( x 0 ) + ƒ '( x 0 ) × ( x - x 0 )

og omvendt loven:

x \ simeq x_ {0} + {\ frac {f (x) -f (x_ {0})} {f '(x_ {0})}}

f ^ {{- 1}} (y) \ simeq x_ {0} + {\ frac {yf (x_ {0})} {f '(x_ {0})}}

Dette bruges for eksempel i Newtons algoritme , der søger efter nuller til en funktion:

f ^ {{- 1}} (0) \ simeq x_ {0} - {\ frac {f (x_ {0})} {f '(x_ {0})}}

Ordforråd og notationer. Historisk

Det aktuelle symbol for divisionen er en vandret linje, der adskiller tælleren ( udbyttet ) fra nævneren ( divisoren ). For eksempel er en divideret med b nedskrevet . ${\ dfrac ab}$

Den nævneren giver pålydende og de tæller lister: angiver, at disse er kvartaler , og at der er tre → tre fjerdedele . ${\ dfrac 34}$

Diofant og romerne , den IV th århundrede allerede skriver fraktioner i lignende form, de indianere også den XII th århundrede og moderne notation blev vedtaget af araberne .

Symbolet " : " blev senere brugt af Leibniz .

Lommeregnerproducenter udskriver obele ÷ eller skråstreg / på “division operator” -tasten. Brugen af disse symboler er mere tvetydig end fraktionsbjælken, da det kræver indstilling af prioriteter, men det er nyttigt til "online" -skrivning, der bruges til udskrivning eller på en skærm.

I videnskabelige publikationer anvendes brøknotationer lettere. Colon notation bruges ofte til at repræsentere et forhold mellem hele mængder eller længder.

I dag i Frankrig, klasse 6 th college, ratings ÷ , : og / anvendes som divisionen for studerende driftstilstand. En nuance af mening er almindeligt accepteret:

a ÷ b og a : b betegner en operation (ikke udført), og det passende ordforråd er udbytte for a og divisor for b ;
${\ dfrac {a} {b}}$ og a / b betegner brøkdelen af resultatet af denne operation, og det relevante ordforråd er tæller for a og nævneren for b .

Matematik og fransk sprog

Vi kan opdele en enhed i et antal dele, hvis tilføjelse giver denne enhed på en implicit eller eksplicit måde.

Således kan vi:

del en kage i to dele med et stik
del bare en kage i to [skiver, på nogen måde]
del 1 i 2 halvdele ved den matematiske mentale repræsentation, vi har
del blot 1 i 36 th
etc.

Vi kan også dele ved dikotomi eller ondskab , men at dividere med 2 er et matematisk begreb:

{\ dfrac ab} = c

: " A divideret med b er lig med c ".

Definition

Grundlæggende tilgang

Vi starter med at definere inddelingen "med resten" mellem hele tal . Denne opdeling kan tilgås intuitivt ved begrebet "deling, retfærdig fordeling" og giver en beregningsprocedure.

Denne forestilling gør det allerede muligt at fremhæve problemet med division med nul : hvordan man deler en størrelse i 0 dele? Det giver ikke mening, du har brug for mindst en del.

Derefter definerer vi begrebet decimaltal , og vi udvider beregningsproceduren ved at anvende den rekursivt på resten, se afsnittet nedenfor Ikke-forkortet division . Dette gør det muligt at definere begrebet rationelt tal .

Begrebet deling er stadig passende, men er sværere at forstå. Vi kan forestille os dele af en del, så divider med blandede tal: divider en mængde med 0,1 (1/10), det betyder, at den oprindelige mængde repræsenterer 1/10 del, og derfor finder størrelsen på en fuld andel. For at dele en størrelse med et negativt tal, svarer det til at beregne størrelsen på en del, som man fjerner.

De reelle tal er konstrueret ud fra rationelle. Et irrationelt tal kan ikke opfattes som en størrelse; på den anden side kan det ses som et forhold: forholdet mellem diagonalen af en firkant og dens side, forholdet mellem omkredsen af en cirkel og dens diameter. Fra da af kan division ikke længere defineres som deling, men som den gensidige af multiplikation.

Med denne definition kan vi stadig ikke dele med 0: da 0 × a = 0 for et hvilket som helst tal, er der en uendelig række gensidige. Vi kan også - da vi dividerer med et tal svarer til at multiplicere med dets inverse - se dette problem som grænsen ved 0 for den inverse funktion ƒ ( x ) = 1 / x : den har to grænser, $-\infty$ til venstre og $+ \infty$ højre.

At "udvide" de reelle tal ved at medtage "uendelige pseudotal", $+ \infty$ og $-\infty$ ( afsluttet ægte linje ) løser ikke problemet, da der stadig er problemet med tegnet.

Begrebet opdeling er derfor grundlæggende i algebra og i analyse .

Fuld definition

Givet en integreret ring (A, +, ×), er opdeling af A sammensætningsloven : betegnet f.eks. "÷" som , ${\ mathrm {A}} \ times {\ mathrm {A}} \ til {\ mathrm {A}}$ $\ forall (a, b, c) \ i {\ mathrm {A}} \ times {\ mathrm {A}} \ times {\ mathrm {A}}$

a ÷ b = c hvis og kun hvis b × c = a .

Ringens integritet sikrer, at divisionen har et unikt resultat. På den anden side defineres det kun på hvis og kun hvis A er et kommutativt felt og under ingen omstændigheder defineret for b = 0 . ${\ mathrm {A}} \ times ({\ mathrm {A}} - \ {0 \})$

Hvis divisionen ikke er defineret overalt, kan vi sammen udvide divisionen og sæt A: i kommutativt tilfælde definerer vi en ækvivalensrelation ved ${\ mathrm {A}} \ times {\ mathrm {A}}$ $\ sim$

(a, b) \ sim (a ', b') \ iff a \ times b '= a' \ times b

og vi skriver

a ÷ b klassen i kvotientringen.

(a, b)

Denne kvotientring er et felt, hvis neutral er klasse 1 ÷ 1. Sådan konstruerer vi ved symmetriering til multiplikationen (eller fra ved symmetriering af tilføjelsen). $\ mathbb {Q}$ $\ mathbb {Z}$ $\ mathbb {Z}$ $\ mathbb {N}$

Denne definition dækker ikke definitionen af euklidisk opdeling , der opstår på en lignende måde, men hvis betydning er radikalt anderledes.

I ideen bruges den også til at vende multiplikationen (i a , hvor mange gange b ).

Problemet med definition ikke opstår nogen mere, da , er en del af ikke tom og øget, hvilket dermed indrømmer en større element. $\ forall (a, b) \ i {\ mathbb {N}} \ gange ({\ mathbb {N}} - \ {0 \})$ $\ {n \ i {\ mathbb {N}} \ | \ b \ gange n \ leqslant a \}$ $\ mathbb {N}$

Denne opdeling, grundlæggende i aritmetik, introducerer forestillingen om resten . Som med alle divisioner kan b i definitionen imidlertid ikke være nul .

Ejendomme

Opdelingen var ikke strengt taget en operation ( intern lov om sammensætning , defineret overalt), dens "egenskaber" har ingen strukturelle konsekvenser for sæt af tal og skal forstås som egenskaber ved tal skriftligt.

Ikke-ejendomme

ikke- kommutativ fordi $5 \ div 3 \ neq 3 \ div 5$
ikke- associerende fordi $12 \ div (4 \ div 3) \ neq (12 \ div 4) \ div 3$

Bemærkninger

pseudo- neutralt element til højre: 1 ${\ dfrac a1} = a$
pseudoabsorberende element til venstre: 0 ${\ mbox {si}} b \ neq 0, {\ dfrac 0b} = 0$
ligestilling af fraktioner
- med samme nævneren ${\ mbox {si}} b \ neq 0, {\ dfrac ab} = {\ dfrac cb} \ iff a = c$
- generelt (som opstår ved opførelsen af ) $\ mathbb {Q}$ ${\ mbox {si}} b \ neq 0 \ wedge d \ neq 0, {\ dfrac ab} = {\ dfrac cd} \ iff ad = bc \, {\ text {(cross product)}}$
bestille ${\ mbox {si}} b> 0, {\ dfrac ab}$ og er i samme rækkefølge som a og c ${\ dfrac cb}$

Algoritmer til opdeling af decimaler

Ikke-forkortet division

Den ikke-forkortede delingsalgoritme, også kaldet lang division, bruges til at bestemme en decimalskrivning af kvotienten af to heltal . Det er en udvidelse af den euklidiske division (se At stille en division> Generalisering i aritmetik ). Fra et praktisk synspunkt består det i at fortsætte proceduren ved "faldende nuller", hvor de nye beregnede cifre tilføjes efter decimaltegnet. Dette er berettiget af

{\ frac {a} {b}} \ times 10 ^ {n} = {\ frac {a \ times 10 ^ {n}} {b}} \ Longrightarrow {\ frac {a} {b}} = {\ frac {a \ times 10 ^ {n}} {b}} \ div 10 ^ {n}

hvor n er antallet af decimaler, vi ønsker. Således har vi tilføje n nuller til højre for tælleren, vi udfører en klassisk euklidisk division, så på kvotienten opnået, de sidste n cifre er efter kommaet.

Bemærk, at vi har interesse i at beregne n + 1 - decimalen for at vide, i hvilken retning vi skal afrunde .

For eksempel for at beregne 23 ÷ 6 med to decimaler svarer proceduren til beregning af 2300 ÷ 6 (= 383, resten 2) og derefter dividere resultatet med 100 (hvilket giver 3,83).

Denne procedure er generaliseret til kvotienten med to decimaltal ; dette er begrundet med:

{\ frac {a} {b}} = {\ frac {a \ times 10 ^ {n}} {b \ times 10 ^ {n}}}

hvor n er et positivt heltal, således at a × 10 n og b × 10 n er heltal; man kan f.eks. tage det største antal decimaler i tallene a og b .

To situationer kan opstå:

man ender med at have en nul rest: man får således et decimaltal;
man ender med at falde tilbage af en rest, som allerede har dukket op før: divisionen "slutter ikke", den sløjfer til uendelig; i dette tilfælde er kvotienten en ikke-decimal rationel, og vi kan bevise, at dens decimalekspansion tillader en periode, hvis længde er strengt mindre end skillelinjen.

I et ikke-eksakt division $et \div b$ , ( $en$ og $b$ være to heltal, $b$ ikke er nul), hvis vi skriver ned , og henholdsvis kvotienten og resten opnået ved at skubbe iterationer indtil der opnås p cifre efter kommaet af kvotienten , vi får en ramme eller en lighed: $q_p$ $r_ {p}$

{\ dfrac ab} \ approx q_ {p}

at lukke eller

10 ^ {{- p}}

q_ {p} <{\ dfrac ab} <q_ {p} +10 ^ {{- p}}

{\ dfrac ab} = q_ {p} + {\ dfrac {r_ {p} \ cdot 10 ^ {{- p}}} {b}}

Et irrationelt tal (reelt uden at være rationelt) kan pr. Definition ikke skrives som en brøkdel. På den anden side er det grænsen for en række rationelle tal (se Konstruktion af reelle tal ).

Opdeling af binære kodede tal

Opdelingen i et binært system er en grundlæggende operation for datalogi.

Binær euklidisk division

Vi overvejer først naturlige tal (positive). Opdelingen sker på samme måde som den euklidiske division.

Lad være to tal a og b på n bits. Notationen a ( i ) Betegner det i- th bit (startende fra højre, betegnet fra 0 til n - 1), en ( i : j ) angiver bittene placeret mellem positionerne I og j . Den følgende funktion beregner kvotienten Q og resten R i pseudokode:

fonction [Q, R] = diviser(a, b) si b == 0 alors génère l'exception "division par zéro" ; fin Q := 0 ; R := a ; // initialisation pour i = n-1 → 0 si a(n:i) >= b alors Q(i) = 1 ; // i-ème bit du quotient R = a(n:i) - b ; // reste fin fin retourne [Q, R] ; fin

Vi leder efter en del af "stærke bits" (venstre cifre) af a, der er større end b ; hvis man ikke finder nogen, beholder kvotienten værdien 0, og resten R tager værdien a (da den til sidst består af alle cifrene i a ). Hvis vi ved en bestemt rang i har a ( n : i ) ≥ b , så svaret på grund af det binære system

i a ( n : i ) hvor mange gange b

er nødvendigvis "en gang": i base 10 er svaret mellem 1 og 9 = 10 - 1; her er det mellem 1 og 1 = 2 - 1. Vi har derfor den i- bit af kvotienten, der er lig med 1; resten R på dette trin er forskellen.

Dette pseudoprogram er ikke optimeret til klarhed; en mere effektiv version ville være:

fonction [Q, R] = diviser(a, b) si b == 0 alors génère l'exception "division par zéro" ; fin Q := 0 ; R := 0 ; // initialisation pour i = n-1 → 0 R = décalage_à_gauche_de_bits(R, 1) ; // équivaut à rajouter un 0 à droite R(1) = a(i) ; // le bit de poids faible de R est le i-ème bit du numérateur si R >= b alors Q(i) = 1 ; // i-ème bit du quotient R = R - b ; // reste fin fin retourne [Q, R] ; fin

Denne algoritme fungerer også med decimaltal kodet i fast punkt .

For kodede decimaler med flydende punkt skal du bare se:

{\ frac {a \ cdot 2 ^ {m}} {b \ cdot 2 ^ {n}}} = {\ frac {a} {b}} \ cdot 2 ^ {{mn}}

så vi uddeler mantissas (som er decimaler kodet i fast punkt) på den ene side og forskellen mellem eksponenterne (som er heltal).

Vi ser, at vi kun bruger elementære funktioner - sammenligning, skift, tildeling, subtraktion - hvilket gør det muligt at implementere det på en enkel måde i en mikroprocessor.

Langsomme metoder

I den euklidiske deling af a ved b , for tal repræsenteret i base B (B = 2 i binær), i trin i :

vi betragter resten af det forrige trin, R i - 1 ;
vi bestemmer det i- ciffer i kvotienten startende fra venstre , derfor cifret j = n - i starter fra højre: Q n - i ;
den nye rest er værd

R i = B × R i - 1 - Q n - i × b .

Denne konstruktion ved induktion udgør grundlaget for de såkaldte langsomme metoder.

Når vi kender R i - 1 , antager vi, at Q n - i = 1, har vi så

R i = 2 × R i - 1 - b .

Hvis den fundne værdi er negativ, skyldes det, at Q n - i = 0. I forhold til den euklidiske procedure snarere end at tage cifrene til venstre for tælleren, tilføjer vi 0 til højre for nævneren. I det første trin tilføjer vi så mange som antallet af bits n, der bruges til at kode tallene (så det er nødvendigt med dobbelt hukommelsesplads), så ganger vi tælleren med 2, indtil tilstanden er bekræftet. Dette giver i pseudokode (vi udelader divisionen med nul test):

fonction [Q, R] = diviser(a, b) R := a // valeur initiale du reste b := décalage_à_gauche_de_bits(b, n) pour i = n-1 → 0 R := décalage_à_gauche_de_bits(b, 1) si R >= b alors Q(i) := 1 // le i-ème bit de i est 1 R = R - b sinon Q(i) := 0 // le i-ème bit de i est 0 fin fin fin

Når vi optimerer algoritmen for at reducere antallet af operationer, opnår vi følgende pseudokode.

fonction [Q, R] = diviser(a, b) R := a // valeur initiale du reste b := décalage_à_gauche_de_bits(b, n) pour i = n-1 → 0 R := 2*R - b // le reste décalé est-il supérieur à b ? si R >= 0 alors Q(i) := 1 // le i-ème bit de i est 1 sinon Q(i) := 0 // le i-ème bit de i est 0 R := R + b // on restaure la valeur du reste en gardant le décalage fin fin retourner[Q, R] fin

På grund af den sidste sætning i sløjfen kaldes denne metode "division med restaurering".

Metoden kan forbedres ved at generere en kvotient ved hjælp af tallene +1 og -1. For eksempel antallet kodet af bitene

11101010

svarer faktisk til antallet

11111111

dvs. ved 11101010 -00010101 --------- 11010101 Metoden siges at være "uden gendannelse" og dens pseudokode er:

fonction [Q, R] = diviser(a, b) R[0] := a i := 0 tant que i < n si R[i] >= 0 alors Q[n-(i+1)] := 1 R[i+1] := 2*R[i] - b sinon Q[n-(i+1)] := -1 R[i+1] := 2*R[i] + b fin i := i + 1 fin Q = transforme(Q) retourner[Q, R] fin

SRT-opdelingsmetoden - opkaldt efter dens opfindere, Sweeney, Robertson og Tocher - er en ikke-gendannelsesmetode, men bestemmelsen af kvotientbitene udføres ved hjælp af en opslagstabel med input a og b . Det er en algoritme, der bruges i mange mikroprocessorer . Mens de traditionelle ikke-genoprette fremgangsmåde kun genererer en bit pr klokcyklus , SRT metode genererer to bit per cyklus.

Den Pentium division fejl skyldtes en fejl i oprettelse af korrespondance bordet.

Hurtige metoder

De hurtige metoder er at evaluere x = 1 / b og derefter beregne Q = a × x .

Newton-Raphson-metoden består i at bestemme 1 / b ved Newton-metoden .

Newtons metode gør det muligt at finde nul for en funktion ved at kende dens værdi og værdien af dens afledte på hvert punkt. Vi skal derfor finde en funktion ƒ b ( x ), der opfylder

f_ {b} (x) = 0 \ Lang venstre pil x = 1 / b

og sådan, at vi kan udføre iterationen

x_ {i} = x _ {{i-1}} - {\ frac {f_ {b} (x _ {{i-1}})} {f '_ {b} (x _ {{i-1 }})}}

uden at skulle kende 1 / b . For eksempel kan vi bruge

ƒ b ( x ) = 1 / x - b

Hvilke giver

x i = x i - 1 (2 - b · x i - 1 )

Af hensyn til beregningsøkonomi er det dog bedre at bruge skrivningen

x i = x i - 1 + x i - 1 (1 - b · x i - 1 )

For at initialisere proceduren skal vi finde en tilnærmelse på 1 / b . Til dette normaliserer vi skift af a og b for at få b inkluderet i [0,5; 1]. Vi kan derefter tage en vilkårlig værdi i dette interval - for eksempel b ≈ 0,75 derfor 1 / b ≈ 1,3 3 … eller endda 1 ≤ 1 / b ≤ 2 derfor 1 / b ≈ 1,5 -, ellers gør den begrænsede udvidelse på 1 / x ved et punkt - for eksempel i 0,75 (1 / b ≈ 2,6 6 … - 1,7 7 … × b ) eller i 1 / 1,5 (1 / b ≈ 3 - 2,25 × b ). Vi bruger ofte den affine tilnærmelse

x_ {0} = {\ frac {48} {17}} - {\ frac {32} {17}} b \ (\ simeq 2.82-1.88b)

værdierne på 48/17 og 32/17 er forudberegnede (lagret “hårdt”).

Denne metode konvergerer på en kvadratisk måde . For en præcision på p bits har vi derfor brug for et antal trin s :

s = \ log _ {2} \ venstre ({\ frac {p + 1} {\ log _ {2} 17}} \ højre)

(afrundet), dvs. tre trin til enkelt præcisionskodning og fire trin til dobbelt præcision og udvidet dobbelt præcision (i henhold til IEEE 754 ).

Her er algoritmens pseudokode.

fonction [Q] = diviser(a, b) e := exposant(b) // b = M*2^e (représentation en virgule flottante) b' := b/2^{e + 1} // normalisation ; peut se faire par un décalage de e+1 bits à droite a' := a/2^{e + 1} // 0.5 <= b <= 1 ; a'/b' = a/b X := 48/17 - 32/17*b' // initialisation de la méthode de Newton pour i = 1 → s // s précalculé en fonction du nombre p de bits de la mantisse X := X + X*(1 - b*X) fin Q := a'*X retourne[Q] fin

Goldschmidts metode er baseret på følgende overvejelser:

{\ frac {{\ mathrm {Q}}} {1}} = {\ frac {a} {b}}

derfor findes der en faktor F, således at b × F = 1, og dermed en × F = Q. Bemærk, at F = 1 / b .

Faktoren F evalueres ved en sekvens ( Fk ):

F k = f k × f k - 1 ×… × f 1 = ∏ ( f i )

sådan at sekvensen ( b k ) = F k × b konvergerer til 1. For det normaliserer vi fraktionen, så b er i] 0; 1], og vi definerer

f i + 1 = 2 - b i .

Den endelige kvotient er

Q = F k × a .

Bemærk, at vi har

F i + 1 = f i + 1 × F i ; b i + 1 = f i + 1 × b i .

Denne metode bruges især på AMD Athlon og senere mikroprocessorer .

Binomialmetoden svarer til Goldschmidt-metoden, men består i at tage en sekvens af faktorer f i = 1 + x 2 i med x = 1 - b . Faktisk har vi:

{\ mathrm {Q}} = {\ frac {a} {1-x}} = {\ frac {a (1 + x)} {(1-x) (1 + x)}} = {\ frac { a (1 + x)} {1-x ^ {2}}}

{\ mathrm {Q}} = {\ frac {a (1 + x) (1 + x ^ {2})} {1-x ^ {4}}} = {\ frac {a (1 + x) ( 1 + x ^ {2}) (1 + x ^ {4})} {1-x ^ {8}}} = \ cdots

ifølge Newtons binomeformel .

Hvis vi normaliserer b, så det er i [0,5; 1], så er x i [0; 0.5] og i trin n er nævneren 1 - x 2 n lig med 1 med en fejl på mindre end 2 - n , hvilket garanterer 2 n signifikante cifre.

Denne metode kaldes undertiden "IBM-metoden".

Opdeling af andre objekter end reelle tal

Vi kan derfor definere division x = a / b for ethvert sæt udstyret med en multiplikation som værende løsningen af ligningen.

x × b = a

Vi vil se eksemplet på komplekse tal, polynomer og matricer.

Kompleks opdeling

Lad os starte med den polære notation. Lad være to komplekse tal z 1 = r 1 e iθ 1 , z 2 = r 2 e iθ 2 . Den komplekse opdeling

x = z 1 / z 2

er derfor defineret af

x × z 2 = z 1

Hvis vi betegner med x = r e iθ , bliver ligningen

r e iθ × r 2 e iθ 2 = r 1 e iθ 1

rr 2 e i (θ + θ 2 ) = r 1 e iθ 1

derfor

\ left \ {{\ begin {align} rr_ {2} = \ & r_ {1} \\\ theta + \ theta _ {2} = \ & \ theta _ {1} \ end {align}} \ højre. \ Longrightarrow \ left \ {{\ begin {align} r = \ & {\ frac {r_ {1}} {r_ {2}}} \\\ theta = \ & \ theta _ {1} - \ theta _ { 2} \ end {justeret}} \ højre.

Dette defineres kun, hvis r 2 ≠ 0 dvs. z 2 ≠ 0

Vi kan derfor skrive

{\ frac {r_ {1} {\ mathrm {e}} ^ {{{\ mathrm {i}} \ theta _ {1}}}} {r_ {2} {\ mathrm {e}} ^ {{{ \ mathrm {i}} \ theta _ {2}}}}} = {\ frac {r_ {1}} {r_ {2}}} {\ mathrm {e}} ^ {{{\ mathrm {i}} (\ theta _ {1} - \ theta _ {2})}}

Lad os nu se kartesisk notation. Vi har z 1 = a + b × i og z 2 = c + d × i, og x = e + f × i. Den definerende ligning

x × z 2 = z 1

bliver til

( e + f × i) × ( c + d × i) = a + b × i ec - fd + ( de + cf ) i = a + b × i

\ left \ {{\ begin {align} ec-fd = \ & a \\ de + cf = \ & b \ end {align}} \ right. \ Longrightarrow \ left \ {{\ begin {align} e = \ & {\ frac {ac + bd} {c ^ {2} + d ^ {2}}} \\ f = \ & {\ frac {bc-ad} {c ^ {2} + d ^ {2}} } \ end {justeret}} \ højre.

som er defineret hvis c 2 + d 2 ≠ 0, dvs. hvis | z 2 | ≠ 0, hvilket svarer til at sige, at z 2 ikke er nul.

Vi kan derfor skrive

{\ frac {a + b \ times {\ mathrm {i}}} {c + d \ times {\ mathrm {i}}}} = {\ frac {ac + bd} {c ^ {2} + d ^ {2}}} + {\ frac {bc-ad} {c ^ {2} + d ^ {2}}} {\ mathrm {i}}

En ”rå” computerisering af beregningsmetoden kan føre til problematiske resultater.

I en computer er talernes præcision begrænset af repræsentationsmetoden. Hvis dobbeltpræcision anvendes i henhold til IEEE 754 , er den absolutte værdi af tallene begrænset til ca. [ 10-307 ; 10 308 ]. Hvis beregningen genererer en absolut værdi større end 10 308 , betragtes resultatet som "uendelig" ( Inf, overløbsfejl ); og hvis den absolutte værdi er mindre end 10-307 , betragtes resultatet som nul ( underflow ).

Imidlertid kan ovenstående formel, der involverer produkter og firkanter, have en beregningsformidler, der overskrider repræsentationskapaciteterne, mens det endelige resultat (tallene e og f ) kan repræsenteres. Bemærk, at IEEE 754-standarden 1/0giver Inf(+ ∞) og -1/0giver -Inf(-∞), men med et flag, der angiver fejlen "division med nul"; computing 1/Infgiver 0.

Hvis for eksempel denne formel bruges til at beregne

(1 + i) / (1 + 10-307 i), får vi 0, mens resultatet er ca. 10-307 - 10-307 i (hvilket er repræsentativt); (1 + i) / (10 -307 + 10 -307 i), vi opnår NaN(resultat af en operation 0/0), mens resultatet er 10 307 (repræsenteres);

Disse fejl skyldes beregningen af (10 307 ) 2 og (10 -307 ) 2 .

For at begrænse disse fejl kan vi bruge Smiths metode, der består i factoring på en relevant måde:

{\ frac {a + b \ times {\ mathrm {i}}} {c + d \ times {\ mathrm {i}}}} = \ venstre \ {{\ begynder {justeret} {\ text {si}} | d | \ ll | c | {\ text {:}} & {\ frac {a + b (d / c)} {c + d (d / c)}} + {\ frac {ba (d / c )} {c + d (d / c)}} {\ mathrm {i}} \\ {\ text {si}} | d | \ gg | c | {\ text {:}} & {\ frac {a (c / d) + b} {c (c / d) + d}} + {\ frac {b (c / d) -a} {c (c / d) + d}} {\ mathrm {i} } \\\ ende {justeret}} \ højre.

Faktisk i det første tilfælde | d / c | <1 derfor | x ( d / c ) | < x ( x = a , b , d ), så metoden er mindre følsom over for overskridelser.

Matrix division

Den matrix multiplikation ikke er kommutativ, definerer vi to matrix divisioner.

Højre opdeling

Lad A være en matrix med dimension m × n og B en matrix med dimension n × p , så kalder vi "højre division af A med B" og vi betegner

X = A / B

matrixen for dimensionen m × p, der tilfredsstiller ligningen:

XB = A

Sætning - Hvis B er en regelmæssig matrix (invertibel firkantet matrix), så

X = A / B

svarer til

X = AB -1 Demonstration

Det kommer straks fra

XB = A

end

(XB) B- 1 = AB- 1

hvilket giver resultatet ved associativitet.

Venstre division

Lad A være en matrix med dimension m × n og B en matrix med dimension m × p , så kalder vi "division til venstre for A med B" og vi betegner

X = A \ B

matrixen for dimension n × p, der tilfredsstiller ligningen:

AX = B

Hvis matrix A ikke har maksimal rang , er løsningen ikke unik. A + B- matrixen , hvor A + betegner den pseudo-inverse matrix , er den mindste normløsning .

Sætning - Hvis A er en almindelig matrix (invertibel firkantet matrix), så

X = A \ B

svarer til

X = A -1 B Demonstration

Det kommer straks fra

AX = B

end

A -1 (AX) = A -1 B

hvilket giver resultatet ved associativitet.

Vi har også:

B / A = t ( t A \ t B).

Opdeling af polynomer

Vi kan definere delingen af polynomer på samme måde som den euklidiske division:

{\ mathrm {A}} = {\ mathrm {B}} \ times {\ mathrm {Q}} + {\ mathrm {R}}

grader (R) <grader (B)

hvor Q og R er polynomer; Q er kvotienten og R er resten.

Vi kan også anvende metoden til konstruktion af rationelle tal til polynomier, som gør det muligt formelt at definere en brøkdel af polynomier. Men dette er ikke en "beregning" af division, det er et spørgsmål om at definere et nyt matematisk objekt, et nyt værktøj.

Noter og referencer

[ Pentium® Processor Opdel algoritme ]
[ Statistisk analyse af flydende punktfejl ] , Intel Corporation, 1994
Robert Elliot Goldschmidt , " Applications of Division by Convergence ", MSc-afhandling , MIT,1964
(i) Stuart F. Oberman , "kommatalsdivisioner og kvadratrod Algoritmer og Gennemførelse i de AMD-K7 Microprocessor" i Proc. IEEE Symposium om Computer Aritmetic ,1999, s. 106–115
(i) Peter SODERQUIST og Miriam Leeser , " Division og kvadratrod: Valg af det rigtige Implementation " , IEEE Micro , vol. 17, nr . 4,Juli / august 1997, s. 56–66
Paul Molitor, [ (de) Entwurf digitaler Systeme mit VHDL ]
[ (da) Scilab er ikke naiv ]
(i) Robert L. Smith , " Algoritme 116: Kompleks division " , Communications of the ACM , New York, Association for Computing Machinery, vol. 5, n o 8,August 1962, s. 435 ( DOI 10.1145 / 368637.368661 , læs online )

Se også

Relaterede artikler