Dalybos metodas paremtas liestinių metodu

Dalybos metodas paremtas liestinių metodu

• https://en.wikipedia.org/wiki/Division_algorithm#Newton–Raphson_division
• https://lt.wikibooks.org/wiki/Apytikslis_šaknų_skaičiavimas_(stygų_ir_liestinių_metodai)
• https://lt.wikibooks.org/wiki/Matematika/Išvestinė#Liestinės_lygtis

Funkcijos $y=f(x)$ liestinės lygtis taške $x_0$ yra tokia:

$y=f(x_0)+f^{\prime }(x_0)(x-x_0).$

Arba

$y-f(x_0)=f^{\prime }(x_0)(x-x_0).(1)$

Įstatydami čia koordinates (d, 0) susikirtimo taško liestinės su ašimi x, gausime:

$0-f(x_0)=f^{\prime }(x_0)(d-x_0),$

iš kur

$d=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}.(2)$

Kad skaičiuoti šituo metodu, reikia iš pradžių žinoti apytikslę reikšmę 1/D funkcijos $f(x)=1/x.$ Šis metodas suranda kam lygu 1/D.

Kad panaudoti liestinių metodą reikia pažymėti $X=1/D$ ir sukūrti funkciją $f(X)=\frac{1}{X}-D.$ Taigi, reikia žinoti apytikslią 1/D reikšmę, kuri suteikiama $X_0\approx 1/D$ reikšmei.

Funkcijos f(X) išvestinė yra tokia:

$f^{\prime }(X)={(\frac{1}{X}-D)}^{\prime }=-\frac{1}{X^2}.$

Tada pagal (2) formulę

$X_1=X_0-\frac{f(X_0)}{f^{\prime }(X_0)}=X_0-\frac{\frac{1}{X_0}-D}{-\frac{1}{X_0^2}}=X_0+\frac{X_0-D{X}_0^2}{1}=X_0+X_0(1-D{X}_0)=X_0(2-D{X}_0).(3)$

Dabar reikšmė $X_1$ labiau atitinką ieškomą reikšmę 1/D. Toliau,

$X_2=X_1(2-D{X}_1),(4)$

$X_3=X_2(2-D{X}_2),(5)$

$X_{i+1}=X_i(2-D{X}_i).(6)$

Pavyzdžiai

• Reikia apskaičiuoti N/D = 1.7890625/1.3984375. Čia N = 1.7890625, D = 1.3984375.

Paimama apytiksli 1/D reikšmė. Kadangi tiksli 1/D reikšmė yra

1/1.3984375 = 0.71508379888268156424581005586592, tai paėmus $X_0=0.715$ galima pradėti skaičiavimus. Taigi, pagal (3) formulę,

$X_1=X_0(2-D{X}_0)=0.715\cdot (2-1.3984375\cdot 0.715)=$

= 0.715 * (2 - 1.3984375 * 0.715) = 0.7150837890625.

Jau gauti 7 pirmi teisingi 1/D = 1/1.3984375 skaitmenys.

Toliau atliekama antra iteracija:

$X_2=X_1(2-D{X}_1)=0.7150837890625\cdot (2-1.3984375\cdot 0.7150837890625)=$

= 0.7150837890625 * (2 - 1.3984375 * 0.7150837890625) = 0.71508379888268142938613891601563.

Dabar gauta 15 pirmų teisingų skaitmenų (po kablelio).

Toliau atliekama trečia iteracija:

$X_3=X_2(2-D{X}_2)=$

= 0.71508379888268142938613891601563 * (2 - 1.3984375 * 0.71508379888268142938613891601563) =

= 0.7150837988826815642458100558659.

Dabar gauti 31 pirmi teisingi skaitmenys (po kablelio).

Tada

$N/D=N\cdot X_3=$

= 1.7890625 * 0.7150837988826815642458100558659 = 1.2793296089385474860335195530726.

Dalyba su dvejetainiais skaičiais

1 pav. Dalyba dvejetainėje sistemoje.

2 pav. Slankaus kablelio skaičių dalyba.

Pirmas paveikslėlis parodo sveikujų skaičių dalybą. Ten 8 bitų skaičius 01000011 yra dalinys (dividend), 4 bitų skaičius 1001 yra daliklis (divisor), 4 bitų skaičius 0100 yra liekana (remainder) ir 4 bitų skaičius 0111 yra dalmuo (quotient). Kiti tarpiniai skaičiai 10000111, 0011111, 01101 yra dalinės liekanos (partial remainder).

Čia [ https://www.righto.com/2023/04/reverse-engineering-8086-divide-microcode.html ] aprašyta kaip sveikus skaičius dvejetainėje sistemoje dalina intel 8086 procesorius.

Dalijimo esmė dvejetainėje sistemoje yra atimti daliklį (divisor) iš dalinio (dividend). Jeigu atimties rezultatas teigiamas, tada pirmas dalmens (quotient) bitas yra 1, o jeigu rezultatas neigiamas, tada pirmas dalmens bitas yra 0. Toliau gaunamas partial remainder, kuris yra per vieną bitą kairiau nuo daliklio padauginto iš 0 arba 1. Jeigu atėmus daliklį iš partial remainder gaunamas neigiamas rezultatas (yra borrow, kas atrodo yra carry flag), tai antras dalmens (quotient) bitas yra 0, o jeigu gaunamas teigiamas rezultatas, tai antras dalmens bitas yra 1. Toliau antras partial remainder esantis viena bito pozicija į kairę nuo atimamo dalmens nustato trečią bitą. Jeigu dabar atimties rezultatas yra neigiamas, tai trečias dalmens (quotient) bitas yra 0, o jeigu – teigiamas, tai trečias bitas yra 1. Ir t. t.

Taip dalinant nereikia spelioti dalmens bitų, kaip dalinant dešimtainėje sistemoje reikia spelioti dalmens skaitmenys. 8086 iš tikro dalmenį (quotient) gauna su apverstais bitais (detaliau paaiškinta toje nuorodoje), o paskui pabaigoje visus quotient bitus apverčia į priešingus (tas pats kas quotient XOR 1111...111).

1 paveiksle skaičius 67 dalinamas iš 9 ir gaunamas dalmuo 7 ir liekana 4. Ir 9*7+4=67.

Antrame paveikslėlyje dalybos tikslumas yra mažas, nes yra mažai mantisos bitų. Pavyzdžiui,

1.1111111 = 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 = 1.9921875,

o

1.111111111111 = 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 + 1/512 + 1/1024 + 1/2048 + 1/4096 = 1.999755859375.

Su labai daug vienetų po kablelio turėtų gautis skaičius dešimtainėje sistemoje 1.999999999999999999...

Taip kaip parodyta 2 pav. dalino visi FPU x87 coprocesor'iai. Nuo 8087 iki 486 FPU. O Pentium procesoriaus FPU naudoja SRT dalybą, kai kažkokiu budu kaskart gaunamas ne vienas quotient bitas, o iškart du bitai. Todėl tokia dalyba teoriškai yra apie 2 kartus greitesnė, bet kuri privedė prie Pentium FDIV bug. Daugiau apie tai čia [ https://www.righto.com/2024/12/this-die-photo-of-pentium-shows.html ].

Čia [ https://www.ece.ucdavis.edu/~vojin/CLASSES/EPFL/Papers/4-Fandrianto_division_ARITH8.pdf ] aprašytas SRT algoritmas.