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
θ
.
Wyszukiwarka
Podobne podstrony:
Obliczenia trakcyjne id 327729 Nieznany
Numeryka id 325239 Nieznany
Obliczenia osi id 327524 Nieznany
Obliczenia 14 id 327535 Nieznany
Przodek obliczen wiezby id 4074 Nieznany
Cwiczenia obliczenia 2014 id 12 Nieznany
OBLICZENIA CHEMICZNE 2 id 32760 Nieznany
OBLICZENIA PODN id 437364 Nieznany
Marerialy do obliczen Cw2 id 27 Nieznany
obliczniaKBI TT id 327842 Nieznany
numeryczne id 325226 Nieznany
obliczenia 10 id 327531 Nieznany
Obliczenia chemiczne id 327600 Nieznany
obliczenia wiezby id 327756 Nieznany
obliczanie L 02 id 327419 Nieznany
Lab 05 Obliczenia w C id 257534 Nieznany
Algorytmy obliczen id 57749 Nieznany
Obliczenie czasu operacji id 32 Nieznany
Oblicz (2) id 327340 Nieznany
więcej podobnych podstron