Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–1
Przybli anie ilorazu wymiernego jego sko czonym rozwini ciem
∏
∏
∏
=
=
=
≈
=
=
⇒
→
=
∃
⇒
≠
m
i
i
m
i
i
m
m
i
i
m
i
R
X
R
D
X
D
X
Q
R
D
D
R
D
0
0
0
1
:
}
{
0
•
dokładno ilorazu – okre lona precyzj wyznaczenia liczby
m
R
R
R
...
1
0
standaryzacja: (ujemny dzielnik
→
zmieni znaki D oraz X)
D
X
X
D
D
D
sgn
:
,
sgn
:
=
=
normalizacja:
m
m
m
m
X
x
D
d
D
−
−
−
−
=
<
=
≤
⇒
<
≤
β
β
β
β
β
&
1
1
1
1
)
1
(
)
1
)...(
1
)(
1
)(
1
)(
1
(
1
0
1
2
2
4
2
≅
−
=
+
+
+
+
−
⇒
<
<
+
n
n
q
q
q
q
q
q
q
procedura:
)
2
(
)
1
(
)
1
(
1
2
1
i
i
i
i
i
d
d
z
z
d
d
z
d
−
=
−
=
+
=
⇒
−
=
+
zbie no procedury – kwadratowa
s
i
s
i
z
d
z
d
2
2
1
1
1
−
+
−
<
=
−
⇒
<
=
−
β
β
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–2
Przybli anie ilorazu sko czonym rozwini ciem w systemie dwójkowym
U2
3
2
1
0
1
2
U2
3
2
1
0
1
2
U2
2
1
0
1
2
,...}
,
,
,
1
,
0
,
0
{
,...}
,
,
,
1
,
1
,
1
{
,...}
0
,
0
,
0
,
1
,
0
{
−
−
−
−
−
−
−
−
=
+
x
x
x
x
x
x
D > 0 ⇒
NB
3
2
1
U2
3
2
1
,...}
,
,
,
1
{
,...}
,
,
,
1
{
2
−
−
−
−
−
−
=
+
x
x
x
x
x
x
Procedura
0
o
X
R
Q
D
R
D
R
s
0
1
0
1
0
,
1
2
1
:
=
<
=
≤
−
−
(np. R
0
=2
–m
: 1–2
–s
≤
2
–m
D
≤
1)
1
o
obliczaj
i
i
D
R
−
=
2
oraz
i
i
i
R
Q
Q
=
+
1
a
1
2
1
1
≤
=
<
−
+
−
i
i
i
n
R
D
D
•
liczba wiod cych jedynek liczb D
i
zostaje podwojona w ka dej iteracji
1
2
1
1
2
1
1
2
<
≤
−
⇒
<
≤
−
+
−
−
i
p
i
p
D
D
•
1
2
1
1
<
≤
−
−
D
s
⇒ wzgl dn dokładno 2
–n
ilorazu
...
1
0
R
R
X
Q
≈
zapewnia
1
/
log
2
+
=
s
n
m
iteracji
⇒ pierwszy mno nik R
0
– wyznaczony z dokładno ci s+log
2
s bitów
)
(
0
D
f
R
=
– z matrycy ROM o rozmiarze 2
s
×( s+log
2
s) bitów
•
przy pieszenie mno enia
→
u ycie krótszych mno ników R
i
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–3
Obliczanie odwrotno ci dzielnika
metoda iteracyjna Newtona-Raphsona
x
x
i+2
x
i+1
x
i
y=f
’
(x
i
)(x–x
i
)+f (x
i
)
y=f
’
(x
i+1
)(x–x
i+1
)+f (x
i+1
)
y = f (x
i
)
y
kolejne przybli enia miejsca zerowego f(x) okre la równanie rekurencyjne
)
(
)
(
1
i
i
i
i
x
f
x
f
x
x
′
−
=
+
,
w odniesieniu do funkcji
D
x
x
f
−
=
−
1
)
(
przybiera posta
)
2
(
1
i
i
i
x
D
x
x
−
=
+
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–4
Zbie no metody mno enia przez odwrotno dzielnika
Niech
a
x
=
0
oraz Da = 1
−
q ⇒
)
1
(
)
1
(
)
1
(
2
1
1
q
q
a
q
a
x
−
−
=
+
=
−
)
1
(
)
1
(
)
1
(
...
)
1
(
2
1
2
1
i
i
q
q
a
q
q
a
x
i
−
−
=
+
+
=
−
−
)
1
(
)
1
(
)
1
(
)]}
1
(
...
)
1
[(
2
){
1
(
)
1
(
2
2
1
2
2
1
1
1
i
i
i
i
q
q
q
a
q
q
Da
q
q
a
x
i
+
−
−
=
+
+
−
−
−
=
−
−
+
−
1
1
2
1
)
1
(
)
1
(
)
1
(
lim
lim
1
|
|
−
−
−
∞
→
∞
→
=
−
=
−
−
=
⇒
<
D
q
a
q
q
a
x
q
i
i
i
i
•
dzielnik znormalizowany
1
|
|
2
1
<
≤
D
⇒ zbie no , je eli |a| < 2 i aD > 0.
•
zbie no kwadratowa – je li
i
i
x
D
−
=
−
1
δ
, to
2
2
1
1
1
1
1
1
)]
(
2
)[
(
i
i
i
i
i
i
D
D
D
D
D
x
D
δ
δ
δ
δ
δ
<
=
−
−
−
−
=
−
=
−
−
−
+
−
+
•
szybko zbie no ci zale y od dokładno ci pierwszego przybli enia
j
j
k
D
k
−
−
<
≤
−
2
2
)
1
(
⇒ optymalne
1
2
1
1
0
]
2
[
2
)
(
−
+
−
+
=
k
k
x
j
j
wada – mniejsza dokładno ni uzyskiwana w dzieleniu sekwencyjnym
niezb dna korekcja wyniku
→
dodatkowe działania arytmetyczne
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–5
Obliczanie pierwiastka i odwrotno ci pierwiastka kwadratowego
Liczba pierwiastkowana jest znormalizowana
1
4
1
<
≤
A
.
metoda iteracyjna Newtona – równanie rekurencyjne:
)
(
)
(
1
i
i
i
i
x
f
x
f
x
x
′
−
=
+
Obliczanie pierwiastka kwadratowego:
Je li f(x) = x
2
–A, to x = sqrt(A) (
√
A) i wtedy f
′
(x) = 2x, wi c
i
i
i
i
i
i
x
A
x
x
A
x
x
x
2
1
2
1
2
1
2
+
=
−
−
=
+
wada: konieczno dzielenia
Obliczanie odwrotno pierwiastka kwadratowego:
A
x
x
f
−
=
−
2
i wtedy
3
−
−
=
′
x
x
f
oraz
2
2
1
3
2
1
A
x
x
x
A
x
x
x
i
i
i
i
i
i
−
=
−
−
−
=
−
−
+
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–6
Obliczanie odwrotno ci pierwiastków wy szych stopni
Je eli
A
x
x
f
k
−
=
−
)
(
, to
k
A
x
1
−
=
Poniewa wtedy
1
−
−
−
=
′
k
kx
x
f
, wi c otrzymujemy
1
1
1
A
x
k
x
kx
A
x
x
x
k
i
i
k
k
i
k
i
i
i
−
+
=
−
−
−
=
−
−
−
+
Obliczenia wymagaj wielokrotnego mno enia / pot gowania je li k > 2.
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–7
CORDIC – algorytm Voldera (1)
Obrót wektora zaczepionego w punkcie (0,0) przestrzeni kartezja skiej
δ
α
x
y
x
b
x
a
y
a
y
b
(x
a
= R cos
α
,
y
a
= R sin
α
)
(x
b
= R cos (
α
+
δ
)
,
y
b
= R sin (
α
+
δ
)
Z to samo ci trygonometrycznych
cos (
α
+
β
) = cos
α
cos
β
– sin
α
sin
β
sin (
α
+
β
) = sin
α
cos
β
+
cos
α
sin
β
wynika, e:
x
b
= R cos (
α
+
δ
)
=
R cos
α
cos
δ
−
R sin
α
sin
δ
=
x
a
cos
δ
−
y
a
sin
δ
y
b
= R sin (
α
+
δ
)
=
R sin
α
cos
δ
+
R cos
α
sin
δ
=
y
a
cos
δ
+
x
a
sin
δ
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–8
CORDIC – algorytm Voldera (2)
J.Volder (1956, sterowanie samolotu B-58)
Podstawiaj c t
=
tg
δ
(cos
–2
δ
=
1
+
t
2
)
, otrzymamy dla k tów w I wiartce:
α
α
α
sin
cos
)
arctg
cos(
)
1
(
1
2
R
t
R
t
R
t
−
=
+
+
−
α
α
α
cos
sin
)
arctg
sin(
)
1
(
1
2
R
t
R
t
R
t
+
=
+
+
−
W krokach iteracji, to wynikiem obrotu wektora (x
i
, y
i
) o k t arctg t
i
jest:
i
i
i
i
i
y
t
x
x
t
−
=
+
+
−
1
1
2
)
1
(
, i = 0, 1, …
i
i
i
i
i
x
t
y
y
t
+
=
+
+
−
1
1
2
)
1
(
, i = 0, 1, …
Obie współrz dne s jednakowo skalowane, wi c w pojedynczym kroku mo na
zignorowa wydłu enie wektora, dokonuj c korekty w ostatnim kroku oblicze
*
*
*
1
i
i
i
i
y
t
x
x
−
=
+
oraz
*
*
*
1
i
i
i
i
x
t
y
y
+
=
+
gdzie
0
*
0
x
x
=
,
0
*
0
y
y
=
oraz
∏
∏
−
=
−
=
+
=
+
=
1
0
2
*
1
0
2
*
1
,
1
n
i
i
n
n
n
i
i
n
n
t
y
y
t
x
x
.
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–9
CORDIC – algorytm Voldera (3)
Podobne to samo ci dotycz funkcji hiperbolicznych sinh i cosh (wzór Eulera)
cosh (
α
+
δ
) = cosh
α
cosh
δ−
sinh
α
sinh
δ
sinh (
α
+
δ
) = sinh
α
cosh
δ
+
cosh
α
sinh
δ
gdzie (wzór Eulera: exp
i x
=
cos
x
+
i sin x )
)
exp(
exp
sin
2
sinh
2
x
x
x
i
x
−
−
=
−
=
)
exp(
exp
cos
2
cosh
2
x
x
x
x
−
+
=
=
x
x
x
sinh
cosh
exp
+
=
Warto ci t
=
tg
δ
=±
2
–n
, mo na łatwo tablicowa i wtedy wszystkie obliczenia
mo na wykona za pomoc dodawania, odejmowania i przesuni cia.
Zale nie od znaku k ta wyró nia si obliczenia
•
w
trybie obrotu (rotation mode), gdy k t jest dodatni,
•
w
trybie normowania (vectoring mode), gdy k t jest ujemny
– jego wynikiem jest obliczenie długo ci wektora
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–10
CORDIC – algorytm Voldera (4)
Uogólnienie dla funkcji trygonometrycznych i hiperbolicznych.
trzecia zmienna –
z
i
odległo k towa wektora od osi [0,
x):
i
i
i
i
i
y
t
m
x
x
σ
+
=
+
1
i
i
i
i
i
x
t
y
y
σ
−
=
+
1
i
i
i
i
t
m
m
z
z
arctg
)
/
1
(
1
σ
+
=
+
gdzie
t
i
= 2
–S(m,i)
– przyj ta sekwencja iteracji przyrostów
tryb obrotu (z
i
→
0)
tryb normowania (y
i
→
0)
σ
i
=−
sign
z
i
σ
i
= sign (
x
i
y
i
)
x
n
→
K(x
0
cos
z
0
–
y
0
sin
z
0
)
x
n
→
K
2
0
2
0
y
x
+
m=1
arctg2
–k
y
n
→
K(y
0
cos
z
0
–
x
0
sin
z
0
)
y
n
→
0
tr
y
g
o
n
o
m
e
tr
.
z
n
→
0
z
n
→
z
0
–arctg2(
y
0
/
x
0
)
x
n
→
K(x
0
cosh
z
0
–
y
0
sinh
z
0
) x
n
→
K
2
0
2
0
y
x
−
m=–1 tanh
–1
2
–k
y
n
→
K(y
0
cosh
z
0
–
x
0
sinh
z
0
)
y
n
→
0
h
ip
e
rb
o
li
c
z
n
y
z
n
→
0
z
n
→
z
0
–tanh
–1
2(
y
0
/
x
0
)
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–11
CORDIC – realizacja układowa
x
y
z
LUT
Zalety algorytmu CORDIC
obliczanie funkcji elementarnych za pomoc prostych działa arytmetycznych
prosta implementacja układowa algorytmu (Cyrix, procesory DSP)
Wada – wolna zbie no , konieczno wykonania du ej liczby oblicze ,
→
→
wersja ulepszona CORDIC–2.
Algorytmy obliczeniowe
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–12
Inne metody obliczania warto ci funkcji przest pnych
tablica odniesie (look-up table)
•
zapami tanie warto ci funkcji jednej zmiennej z dokładno ci do
n bitów
– matryca ROM o rozmiarze
n
n 2
×
bitów (dla
n > 23 rozmiar > 128 Mb)
rozwini cie w szereg Taylora
•
ró ne algorytmy dla poszczególnych funkcji
•
wolna zbie no szeregu Taylora (zale y silnie od warto ci argumentu)
rozwini cia funkcji przest pnych w postaci ułamków wymiernych
•
powszechnie stosowane w implementacjach programowych
•
mog by bardzo skuteczne w realizacjach sprz towych, je li w dyspozycji
s szybkie zmiennoprzecinkowe sumatory i układy mno
ce
algorytmy oparte na przybli eniach wielomianowych z u yciem tablic odniesie
•
domena argumentu funkcji
f(x) podzielona na przedziały równej długo ci
•
warto ci graniczne
)
(
i
x
f
w punktach podziału
i
x s w tablicy odniesie
•
warto ci wewn trz przedziałów obliczane na podstawie aproksymacji
wielomianowej
)
(
i
x
x
p
−
funkcji
)
(
i
x
x
f
−
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–13
Procedura normalizacji addytywnej
F – obliczana funkcja,
i
i
i
b
x
x
−
=
+
1
)}
(
)
(
)
(
{
0
}
{
0
1
0
0
1
0
0
x
F
b
F
x
x
F
y
b
x
x
i
j
j
i
i
i
j
j
i
→
=
−
=
⇒
→
−
=
∑
∑
−
=
−
=
,
lub
)}
(
)
)
(
(
{
0
}
)
(
{
0
1
0
1
0
1
0
0
x
F
b
b
g
F
y
b
g
x
x
i
j
j
i
j
j
i
i
j
j
i
→
=
=
⇒
→
−
=
∏
∑
∑
−
=
−
=
−
=
,
•
rozwini cie w szereg Taylora funkcji g(x) wokół punktu x
0
)
(
|
d
)
(
d
|
d
)
(
d
)
(
)
(
2
2
2
2
0
0
0
0
ε
ε
ε
ε
o
x
x
F
x
x
F
x
F
x
F
x
x
+
+
−
=
−
•
ε
=
−
=
∑
−
=
1
0
0
m
j
j
m
b
x
x
⇒ bł d przybli enia F(x
0
) przez
)
(
1
0
∑
−
=
=
m
j
j
m
b
F
y
0
|
d
)
(
d
)
(
)
(
0
0
x
x
x
F
x
F
x
F
ε
ε
δ
≈
−
−
=
•
ε
→
0 ⇒
δ
→
0 (
δ
zale y od pochodnej funkcji F w punkcie
0
x )
•
{b
i
} – tak dobra aby w m krokach uzyska
δ
< 2
–n
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–14
Procedura normalizacji multyplikatywnej
F – obliczana funkcja,
i
i
i
b
x
x
=
+
1
)}
(
)
(
)
(
{
1
}
{
0
1
0
1
1
0
1
0
0
x
F
b
F
x
x
F
y
b
x
x
i
j
j
i
i
i
j
j
i
→
=
=
⇒
→
=
∏
∏
−
=
−
−
−
=
•
∏
−
=
=
−
1
0
0
1
m
j
j
b
x
ε
⇒
)
)
1
(
(
)
(
1
0
1
0
1
−
−
=
−
−
=
∏
ε
x
F
b
F
m
j
j
•
ε
→
0 ⇒
)
(
)
)
1
(
(
0
0
1
0
x
x
F
x
F
ε
ε
+
≈
−
−
•
bł d przybli enia
)
(
0
x
F
→
rozwini cie w szereg Taylora dla x= x
0
( 1 –
ε
)
–1
)
(
|
d
)
(
d
)
(
)
(
)
(
)
)
1
(
(
0
0
0
0
0
0
1
0
ε
ε
ε
ε
δ
o
x
x
F
x
x
F
x
x
F
x
F
x
F
x
+
=
−
+
≅
−
−
=
−
•
ε
→
0 ⇒
δ
→
0 (
δ
zale y od
0
x i pochodnej funkcji F w punkcie
0
x )
•
{b
i
} – tak dobra aby w m krokach uzyska
δ
< 2
–n
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–15
Funkcja wykładnicza
•
)
2
1
(
i
i
i
s
b
−
+
=
,
}
1
,
0
,
1
{
∈
i
s
(prostsze mno enie)
)}
exp(
)
ln
exp(
)
{exp(
0
}
ln
{
0
1
0
1
0
0
1
0
0
x
b
b
x
x
b
x
x
i
j
j
i
j
j
i
i
j
j
i
→
=
=
−
⇒
→
−
=
∏
∑
∑
−
=
−
=
−
=
,
•
∑
∑
−
=
−
−
=
−
+
≤
≤
−
1
1
0
1
1
)
2
1
ln(
)
2
1
ln(
m
j
j
m
j
j
x
⇒ istnieje ci g
}
{
i
s taki, e
m
x
→
0
0
}
{
0
)
2
1
ln(
0
)
2
1
ln(
gdy
gdy
,
1
,
0
1
0
0
→
⇒
≥
+
−
<
+
−
=
⇒
<
<
−
−
i
i
i
i
i
i
x
x
x
s
x
i
1+2
–i
ln(1+2
–i
)
1–2
–i
ln(1–2
–i
)
0
10,00000 00000
0,10110 00110
0
—
1
1,10000 00000
0,01100 11111
0,10000 00000
– 0,10110 00110
2
1,01000 00000
0,00111 00100
0,11000 00000
– 0,01001 00111
3
1,00100 00000
0,00011 11001
0,11100 00000
– 0,00100 01001
4
1,00010 00000
0,00001 11110
0,11110 00000
– 0,00010 00010
5
1,00001 00000
0,00001 00000
0,11111 00000
– 0,00001 00001
6
1,00000 10000
0,00000 10000
0,11111 10000
– 0,00000 10000
7
1,00000 01000
0,00000 01000
0,11111 11000
– 0,00000 01000
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–16
Funkcja wykładnicza (2)
•
zapami tanie
)
2
1
ln(
i
−
±
z dokładno ci 2
–n
– matryca ROM 2n
×
n
•
n
n
x
−
<
2
→
exp(x
0
) – exp(x
0
– x
n
) <
1
2
ln
2
e
2
+
−
−
=
n
n
•
dla argumentu spoza przedziału (0,1)
2
ln
e)
log
(x
x
=
→
2
ln
)
e
log
e
log
(
0
x
x
x
−
=
oraz
0
0
e
2
e
e
e
e
log
2
ln
e
log
e
log
x
x
x
x
x
x
=
=
=
+
→
wystarczaj cym zakresem wykładnika jest
2
ln
0
0
<
≤
x
reguła wyboru, nie wymagaj ca cz stego odejmowania
•
rozwini cie ln(1+z) w szereg Taylora wokół warto ci
i
i
s
z
−
=
2
...
2
)
(
2
)
(
2
)
(
2
)
2
1
ln(
4
4
4
1
3
3
3
1
2
2
2
1
+
−
+
−
=
+
−
−
−
−
−
i
i
i
i
i
i
i
i
i
i
s
s
s
s
s
→
w i-tym kroku procedury przy odejmowaniu
)
2
1
ln(
i
i
s
−
+
jest zerowany bit o wadze
i
−
2
→
zbie no jest liniowa
odejmowanie
)
2
1
ln(
i
i
x
−
+
−
potrzebne gdy i-ty bit przybli enia
i
x jest 1
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–17
Funkcja logarytmiczna
procedura normalizacji multyplikatywnej
)}
ln(
)
ln(
)
ln(
{
1
}
{
0
1
0
1
1
0
1
0
0
x
b
x
x
y
b
x
x
i
j
j
i
i
i
j
j
i
→
=
=
⇒
→
=
∏
∏
−
=
−
−
−
=
•
i
i
i
s
b
−
+
=
2
1
, gdzie
}
1
,
0
,
1
{
∈
i
s
umo liwiaj uproszczenie mno enia
77
,
4
)
2
1
(
)
2
1
(
)
2
1
(
29
,
0
1
0
1
0
1
0
1
0
≤
+
≤
−
=
≤
−
≤
∏
∏
∏
−
=
−
−
=
−
−
−
=
−
m
j
j
m
j
j
j
m
j
j
s
x
,
•
znormalizowane ułamki dodatnie nale
do dziedziny
•
0
x nie spełnia ograniczenia
→
przeskalowanie
2
ln
ln
)
2
ln(
0
0
x
E
E
x
x
x
+
=
•
77
,
4
1
}
1
,
0
{
1
0
≤
≤
⇒
∈
−
x
s
i
→
prosta reguła wyboru
i
s
)
0
:
1
(
)
1
(
2
1
2
1
)
1
(
=
−
≤
≤
∀
∧
=
⇒
−
≤
≤
−
+
−
−
l
j
j
i
j
s
j
l
i
s
x
→
je li
i
x ma j
≥
i wiod cych jedynek (
j
j
i
x
−
≤
−
≥
2
1
), to
1
=
i
s
, wi c
j
j
j
j
i
j
x
x
2
1
2
1
)
2
1
)(
2
1
(
)
2
1
(
−
−
−
−
+
−
=
+
−
≥
+
=
•
1
0
0
|
d
ln
d
−
=
x
x
x
x
→
bł d przybli enia ln x jest równy bł dowi
ε
= 1 – x
m
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–18
Metody przy pieszania oblicze
•
rozwini cie funkcji ln(1+x) w szereg Taylora dla
i
i
s
x
−
=
2 daje
)
2
(
2
)
2
1
ln(
1
2
−
−
−
−
+
=
+
i
i
i
i
i
o
s
s
→
dla i > n/2
i
i
i
i
s
s
−
−
=
+
2
)
2
1
ln(
z dokładno ci nie gorsz ni 2
–n
•
przy obliczaniu warto ci funkcji wykładniczej
...
0
...
0
,
0
1
+
=
i
i
i
z
z
x
,
→
z dokładno ci 2
–n
dla m > i > n/2 oraz s
i
= z
i
mamy
∑
∏
−
=
−
−
−
−
=
−
+
+
=
+
=
1
1
2
1
)]
2
(
2
1
[
)
2
1
(
m
i
j
j
j
j
i
m
i
j
j
j
i
m
o
z
y
z
y
y
.
→
n/2 ostatnich kroków mo na zast pi mno eniem
)
1
(
i
i
m
x
y
y
+
=
.
•
przy obliczaniu funkcji logarytmicznej
...
0
...
0
,
0
1
1
+
≥
=
−
j
i
j
i
z
z
x
.
→
z dokładno ci 2
–n
dla m > i > n/2 oraz s
i
= z
i
mamy (szereg Taylora)
)
1
(
2
)
2
1
ln(
1
1
i
i
m
i
j
j
j
i
m
i
j
j
j
i
m
x
y
z
y
z
y
y
−
−
=
−
≈
+
−
=
∑
∑
−
=
−
−
=
−
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–19
Funkcje hiperboliczne (1)
)
e
(e
sinh
2
1
x
x
x
−
−
=
,
)
e
(e
cosh
2
1
x
x
x
−
+
=
procedura normalizacji addytywnej
)
(
1
i
i
i
b
g
x
x
−
=
+
,
i
i
i
b
y
y
=
+
1
•
na podstawie to samo ci
)
tgh
exp(
1
1
1
2
x
x
x
−
−
=
+
dla |x|
≠
1 mamy
)
)
2
(
tgh
exp(
)
2
(
1
)
2
1
(
1
1
1
1
1
2
1
1
∑
∏
∏
−
=
−
−
−
=
−
−
=
−
−
=
+
m
i
i
i
m
i
i
i
m
i
i
i
s
s
s
.
•
je li
i
i
i
s
b
−
+
=
2
1
oraz
)
2
(
tgh
)
(
1
i
i
i
s
b
g
−
−
=
, to (s
0
= 0)
)
exp(
)
2
1
(
)
2
(
tgh
0
0
1
0
0
1
1
1
0
m
m
m
i
i
i
m
m
i
i
i
m
x
x
K
y
s
y
y
s
x
x
−
=
+
=
→
−
=
∏
∑
−
=
−
−
=
−
−
•
}
1
,
1
{
∈
i
s
⇒
∏
−
=
−
−
=
1
1
2
2
1
m
i
i
m
K
oraz
205136
,
1
1
1
20
=
≅
−
−
>
K
K
m
±
2
–40
)
exp(
)
2
1
(
0
0
1
0
0
x
K
y
s
K
y
y
m
i
i
i
m
∏
−
=
−
≅
+
=
.
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–20
Funkcje hiperboliczne (2)
Niech
)
2
1
(
1
i
i
i
i
s
t
t
−
+
−
=
•
i
y i
i
t s zbie ne przy
0
→
i
x
,
•
zbie ne s wi c
)
(
2
1
i
i
i
t
y
z
+
=
i
)
(
2
1
i
i
i
t
y
w
−
=
i
i
i
i
i
w
s
z
z
−
+
+
=
2
1
,
i
i
i
i
i
z
s
w
w
−
+
+
=
2
1
•
granicami zbie no ci s
0
0
0
2
1
0
0
0
2
1
0
2
1
0
2
1
1
sinh
)
(
cosh
)
(
0
0
x
t
y
x
t
y
e
t
e
y
K
z
x
x
m
−
+
+
=
+
→
−
,
0
0
0
2
1
0
0
0
2
1
0
2
1
0
2
1
1
cosh
)
(
sinh
)
(
0
0
x
t
y
x
t
y
e
t
e
y
K
w
x
x
m
−
+
+
=
−
→
−
.
•
1
0
0
−
=
=
K
t
y
⇒
0
cosh x
z
m
→
oraz
0
sinh x
w
m
→
•
zbie no bezwzgl dna ci gu
}
{
i
x do zera nie jest jednostajna
•
)
2
(
tgh
)
2
(
tgh
1
2
1
)
1
(
1
i
i
−
−
+
−
−
<
⇒ niektóre kroki musz by powtórzone
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–21
Funkcje trygonometryczne (1)
algorytmy oparte na wzorze Eulera
1
i
,
sin
i
cos
e
i
−
=
+
=
x
x
x
procedura normalizacji addytywnej
)
(
1
i
i
i
b
g
x
x
−
=
+
,
i
i
i
b
y
y
=
+
1
e
ix
przybiera warto ci zespolone
→
b
i
zespolone:
i
i
i
s
b
−
+
=
2
i
1
, wtedy
+
=
+
=
∑
∏
∏
−
=
−
−
=
−
−
=
−
1
0
1
0
2
0
1
0
0
2
tg
arc
i
exp
)
2
(
1
)
2
i
1
(
m
i
i
i
m
i
i
i
m
i
i
i
m
s
s
y
s
y
y
→
m
m
i
i
i
i
i
i
x
x
s
s
b
g
−
=
⇒
=
∑
−
=
−
−
0
1
0
)
2
tg(
arc
)
2
tg(
arc
)
(
(arctg 2
–i
w matrycy ROM)
•
arctg jest funkcj monotonicznie rosn c
→
0
)
2
tg(
arc
1
→
−
=
−
+
i
i
i
i
s
x
x
( )
0
0
1
0
1
0
2
0
i
exp
2
tg
arc
i
exp
)
2
(
1
x
K
y
s
s
y
y
m
m
i
m
i
i
i
i
i
m
→
+
=
∏
∑
−
=
−
=
−
−
•
obszar zbie no ci metody –
∑
−
=
−
=
≤
1
0
0
)
2
tg(
arc
|
|
m
i
i
m
x
ω
,
π
ω
2
1
20
743
,
1
>
≅
>
m
→
u yteczna domena
π
2
1
0
0
≤
≤
x
jest zawarta w przedziale zbie no ci
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–22
Funkcje trygonometryczne (2)
i
i
i
z
w
y
i
+
=
→
reguły iteracji dla cz ci rzeczywistej w
i
i urojonej z
i
)
2
i(
)
2
(
)
2
i
1
)(
i
(
i
1
1
i
i
i
i
i
i
i
i
i
i
i
i
i
i
w
s
z
z
s
w
s
z
w
z
w
−
−
−
+
+
+
+
−
=
+
+
=
+
•
szybka zbie no metody, ale zmienne K
m
−
<
≤
>
=
−
−
−
).
2
tg(
arc
),
2
tg(
arc
|
|
),
2
tg(
arc
gdy
gdy
gdy
,
1
,
0
,
1
i
i
i
i
i
i
i
x
x
x
s
⇒
)
,...,
,
(
2
1
m
m
m
s
s
s
K
K
=
•
zbie no wolniejsza, ale stałe K
m
(
π
2
1
16
6468
,
1
>
≅
>
m
K
)
<
≥
=
.
0
,
0
gdy
gdy
,
1
,
1
i
i
i
x
x
s
⇒
∏
−
=
−
+
=
1
0
2
2
1
m
i
i
m
K
•
m
K
y
/
1
0
=
⇒
0
0
sin
oraz
cos
x
z
x
w
m
m
=
=
•
liniowa zbie no metody
•
wyrazy rozwini cia arctg w szereg Taylora dla i > n/3 s rz du < o(2
–n
)
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–23
Odwrotne funkcje trygonometryczne (1)
procedura normalizacji multyplikatywnej
i
i
i
b
x
x
=
+
1
,
)
(
1
i
i
i
b
g
y
y
+
=
+
.
i
i
i
s
b
−
+
=
2
i
1
)
2
tg(
arc
)
(
i
i
i
s
b
g
−
=
(jak w obliczaniu funkcji sin i cos)
i
y – rzeczywiste,
i
i
i
v
u
x
i
+
=
– warto ci zespolone, przy tym
i
i
i
i
i
v
s
u
u
−
+
−
=
2
1
,
i
i
i
i
i
u
s
v
v
−
+
+
=
2
1
,
)
2
tg(
arc
1
i
i
i
i
s
y
y
−
+
+
=
.
po m krokach algorytmu mamy
( )
m
m
m
i
i
i
m
K
x
s
x
x
θ
i
exp
)
(
)
2
i
1
(
0
1
0
0
s
=
+
=
∏
−
=
−
,
∏
−
=
−
+
=
1
0
2
)
2
(
1
)
(
m
i
i
i
m
s
K
s
m
m
i
K
K
s
=
⇒
∈
)
(
}
1
,
1
{
s
i wtedy w m krokach iteracji
( )
]
sin
i
[cos
)
i
(
i
exp
0
0
0
θ
θ
θ
+
+
=
→
m
m
m
K
v
u
K
x
x
θ
θ
+
→
+
=
+
=
∑
−
=
−
0
0
1
0
0
)
2
tg(
arc
y
y
s
y
y
m
m
j
i
i
m
.
Algorytmy obliczeniowe*
© Janusz Biernat,
07-06-Obliczenia numer.doc, 27 grudnia 2004
NUM–24
Odwrotne funkcje trygonometryczne (2)
Wynika st d, e
m
m
m
m
v
u
K
u
θ
θ
sin
cos
0
0
1
−
=
−
,
m
m
m
m
u
v
K
v
θ
θ
sin
cos
0
0
1
+
=
−
.
Aby wyznaczy arcus tangens nale y zapewni zbie no
m
u do zera.
Zbie no procedur jest zapewniona przy
1
0
=
v
. Wówczas przy
θ
tg
0
=
=
c
u
oraz
0
0
=
y
warto
m
y d
y do
c
tg
arc
=
θ
.
Zapewnienie dobrych warunków zbie no ci dla pozostałych odwrotnych
funkcji trygonometrycznych jest znacznie trudniejsze.
I tak, dla obliczenia warto ci funkcji arcsin c nale y tak dobra wektor
s, aby
m
u d
yło do sin
θ
, podobnie dla funkcji arccos c nale y znale
wektor
s
zapewniaj cy zbie no
m
v do cos
θ
.