Cesta do hlubin fraktálovy duše IX

9. 08. 2019 9:09:09
Kromě dalších obrázků se v tomto pokračování fraktální série podíváme na to, jak kalkulačky (některé) vlastně počítají funkci sinus. Podrobné studium tohoto algoritmu doporučuje devět z deseti guru jako ideální lehké čtení k vodě.

Dnes vám ukážu pár obrázků Juliovy množiny vytvořených pomocí goniometrických a hyperbolických funkcí namísto tradiční funkce kvadratické.

Galeje

Každý středoškolák ví, že sínus je "protilehlá ku přeponě", popřípadě y-ová souřadnice bodu rotujícího po kružnici, takže by se mohlo zdát, že pro kalkulačku to bude snadné sousto. Ale úplně triviální to není. Počítač nemůže jen tak popadnout úhloměr, vysmahnout příslušný trojúhelník a pravítkem změřit jeho strany.

Jak to tedy taková průměrně blbá kalkulačka zvládne?

Jednak si může pár hodnot předpočítat napevno (koneckonců možných úhlů je jen 360°), uložit je do paměti a zbytek odhadnout pomocí interpolace (ať lineární či nelineární), a jednak si může vypomoci rozvojem sínu do mocninných řad a prostě spočítat prvních pár členů (kolik? - to záleží na požadované přesnosti). Pokud vás zajímají jen určité speciální hodnoty, můžete nasadit standardní matematické triky a pokusit se hodnoty funkce sínus spočítat z různých goniometrických formulek.

Algoritmus, který vám chci představit, funguje trochu jinak. Jmenuje se CORDIC a v jeho dnešní podobě ho na svět uvedl jeden z inženýrů americké firmy Convair, Jack Volder, když v roce 1956 pracoval na zařízení umožňujícím rychlé měření rotace pro použití v avionice.

CORDIC má dvě základní ingredience.

Tou první je známá taktika ze školácké hry, ve které si váš spolužák myslí číslo a vy se snažíte ho uhodnout - přičemž váš protihráč odpovídá pouze "výš" nebo "níž". Je lehce ověřitelným faktem, že nejlepší strategií je půlit dohodnutý interval a přidávat nebo ubírat podle situace (na tomto principu je mimochodem založena i jedna z metod na hledání kořenů nelineárních rovnic - půlení intervalu).

Předpokládejme, že dohodnutý interval je 1:128 (aby se to dobře půlilo) a protihráč - říkejme mu Kuba - si myslí "37". Nejlepší první otázka je "64?" (tedy 128/2), kdy polovina možností leží "níž" a polovina "výš". Kuba odpoví "níž". Rozpůlíme tedy spodní interval (64/2=32) a náš druhý pokus bude "32?". Kuba řekne "výš", opět rozpůlíme interval (32/2=16) a těch 16 přihodíme ke spodní hranici (nebo odečteme od horní): "48?". Na Kubovo "níž" opět rozpůlíme interval (16/2=8) a dotážeme se "40?". Kuba nás dalším "níž" pošle do intervalu (32,40) a za chvíli jsme doma. Můžete samozřejmě střílet od boku a navrhovat i jiná "chytrá řešení", ale statisticky vzato vám půlení zaručí v průměru (tedy při mnoha opakováních) nejrychlejší úspěch.

Druhou ingrediencí je již zmíněná skutečnost, že sínus daného úhlu t je y-ová souřadnice odpovídajícího bodu na jednotkové kružnici (a protože s ním budeme mohutně rotovat, můžete si ho představit jako jednotkový vektor). Jako počáteční odhad si vezmeme vektor (1,0) a pokusíme se ho sérií otázek "níž nebo výš" dostrkat do pozice, kdy bude jeho úhel dostatečně přesně aproximovat zadanou hodnotu t. Tak jako jsme při hádání čísla přidávali nebo ubírali pevnou sekvenci (64,32,16,8,4,2,1), zde budeme při "hádání" úhlu t rotovat vektor po nebo proti směru hodinových ručiček o "pevnou" sekvenci úhlů u[i] (přesně vám ji prozradím za chvilku), která se v každém kroku bude zmenšovat zhruba o polovinu.

Celé kouzlo spočívá v tom, že během tohoto procesu si budeme "pamatovat" nejen náš momentální úhel, který jsme pomocí těchto "pevných" rotací vytvořili, ale také příslušný "narotovaný" vektor, který si označíme v[i]={x[i],y[i]}. Jakmile náš úhel dosáhne požadované přesnosti (tj. jakmile uhodneme Kubovo číslo), pošleme na výstup y-ovou složku tohoto vektoru a máme sínus úhlu t.

+++++++++

Nejprve si připomeneme rotační matici, odpovídající (zatím nespecifikovanému) úhlu u[i]

R[i] = {{cos(u[i]),-sin(u[i])},{sin(u[i]),cos(u[i])}}

Protože se ale chceme vyhnout použití sínu a kosínu (ty přece počítáme), vytkneme z celé matice kosínus a dostaneme

R[i] = {{1,-tan(u[i])},{tan(u[i]),1}} * cos(u[i])

Počítání posloupnosti vektorů bude probíhat podle tradičního schematu

{x[i+1],y[i+1]} = R[i]. {x[i],y[i]}

Aby se nám to dobře počítalo, budeme v i-tém kroku rotovat o úhel splňující

tan(u[i]) = 1/2^i

To znamená, že příslušná matice bude (až na ten kosínus) vypadat takto

R[i] = {{1,-1/2^i},{1/2^i,1}}

a počítačům se s ní bude dobře počítat, protože tak jako se lidem dobře dělí mocninami deseti (jsme zvyklí na desítkovou soustavu), počítačům se dobře dělí mocninami dvojky (počítají binárně).

Když si ty rotované vektory rozepíšeme do složek, dostaneme poměrně snesitelné iterační schema, obsahující pouze algebraické operace (všechny goniometrické funkce jsme už vyhubili)

x[i+1] = x[i] - p[i]*y[i]/2^i
y[i+1] = y[i] + p[i]*x[i]/2^i

kde hodnota p[i] je 1 nebo -1, podle toho zda jsme "níž" nebo "výš" než zadaný úhel t. To p[i] nám de facto říká, zda máme ten úhel u[i] přičíst nebo odečíst (tj. zda ten úhel bereme v kladném či záporném smyslu).

Abyste si udělali obrázek, jak velké ty "pevné" rotace jsou, tady je první pětice úhlů

u[0] = arctan(1/2^0) = arctan(1) = 0.785 radiánů (tj. 45°)
u[1] = arctan(1/2^1) = arctan(1/2) = 0.464 (26.56°)
u[2] = arctan(1/2^2) = arctan(1/4) = 0.245 (14.04°)
u[3]= arctan(1/2^3) = arctan(1/8) = 0.124 (7.12°)
u[4]= arctan(1/2^4) = arctan(1/16) = 0.062 (3.57°)

Vidíte, že s výjimkou úvodu ty úhly prakticky půlíme - to je proto, že pro malé hodnoty přibližně platí tan(x)~x. Kdybychom je půlili natvrdo, tak už by nesplňovaly ty definiční tangensové rovnice a nám by se nepodařilo z těch iteračních formulek vyštípat goniometrické funkce.

Možná vám neuniklo, že v původní formulce pro matici R[i] jsem zapomněl na ten vytknutý cos(u[i]). On není pro rotaci podstatný - je to pouze skalární faktor, který v každém kroku násobí celou matici a protože máme konstantní sekvenci úhlů (mění se jen jejich znaménko), můžeme si všechny ty kosíny vynásobit předem (kosínus je vůči znaménku imunní: cos(u) = cos(-u)) a touto konstantou nakonec pronásobit výsledek.

Abych to shrnul: v tom "školáckém příkladu" jsme se snažili vyjádřit "hádané číslo" pomocí zmenšujících se mocnin dvojky (jako kdybychom hledali jeho binární rozvoj). Podobně se při algoritmu CORDIC snažíme "slepit" zadaný úhel t pomocí pevných úhlů u[i] a tím dostat iterační schema, které je jednoduché a hardwarově výhodné (protože používá mocniny dvojky). Zhruba platí, že na každé desetinné číslo výsledku musíme udělat jednu iteraci.

Pokud si s tím chcete hrát, tady najdete příklad ve formátu pdf.

+++++++++

Galerie

Nejprve pár kapradin z goniometrického zátiší.

(tohle byl detail předchozího obrázku, abyste viděli jak jsou ty "provázky" jemné)

Vidíte, že na rozdíl od polynomiálních funkcí, jejichž Juliova množina byla omezená, jsou tyto výtvory donekonečna se opakujícím "nátiskem" téhož vzorku, což je způsobeno periodicitou goniometrických a hyperbolických funkcí.

+++++++++

Předchozí díly série "Cesta do hlubin fraktálovy duše"

Autor: Jan Řeháček | pátek 9.8.2019 9:09 | karma článku: 18.76 | přečteno: 642x

Další články blogera

Jan Řeháček

Impresionisté na hladině

Když se na podzim objevily barvy na stromech, všiml jsem si, že se občas zrcadlí v našem potoce či rybníčku. Tak jsem na ně zamířil objektiv a vyšly z toho roztěkané výtvarné kreace, za které by se nemusel stydět ani Claude Monet.

9.3.2024 v 9:09 | Karma článku: 20.40 | Přečteno: 204 | Diskuse

Jan Řeháček

AI Art: co už umí a co ještě ne

Loni jsem trochu experimentoval s malířskými schopnostmi tehdy nastupující generativní AI Art. Letos, za dlouhých zimních večerů jsem si na to vzpomněl a napadlo mne podívat se, jak moc za ten rok AI pokročila. Nu, posuďte sami.

15.2.2024 v 9:09 | Karma článku: 16.53 | Přečteno: 278 | Diskuse

Jan Řeháček

Není větvička jako větvička

Stromy a jejich rozeklaná větvoví jsou sochařská díla. V létě to ale nepoznáte, protože přírodní majstrštyky zakrývá koruna. Jakmile ale podzim povolá svá vojska zpět do zálohy, ladná elegance dřevěných křivek vystoupí do popředí.

9.2.2024 v 9:09 | Karma článku: 19.25 | Přečteno: 337 | Diskuse

Jan Řeháček

Co rok dal

Začátek nového roku je tradičně příležitostí k ohlédnutí za rokem starým, takže jsem prohrábl archív a vylovil z něho pár fotografií z našeho parku, které si nenalezly cestu do některého z předchozích tématických blogů.

9.1.2024 v 9:09 | Karma článku: 16.65 | Přečteno: 166 | Diskuse

Další články z rubriky Věda

Dana Tenzler

Barvy v kuchyni (3) - přírodní červená

Blíží se Velikonoce. Napadlo vás někdy, čím se vlastně barví velikonoční vajíčka? Jakými přírodními nebo umělými barvivy se dá jídlo barvit dnes a jak tomu bylo v minulosti? (délka blogu 3 min.)

28.3.2024 v 8:00 | Karma článku: 11.91 | Přečteno: 114 | Diskuse

Zdenek Slanina

Problém co začal už Arrhenius: Kysličník uhličitý a doba ledová - a teď i sopečné aktivity

Už S. Arrhenius řešil vztah obsahu CO2 v atmosféře i k době ledové. Tehdy hlavně ukázal, že jeho navyšování v atmosféře povede k nárůstu její teploty. Nyní výzkumy z univerzity v Sydney ukazují na roli sopek v nástupu ochlazování.

26.3.2024 v 5:22 | Karma článku: 24.04 | Přečteno: 511 |

Martin Tuma

Berte Viagru, dokud si na to vzpomenete

Rozsáhlá studie odhalila významné snížení výskytu Alzheimerovi nemoci u pravidelkných uživatelů Viagry

25.3.2024 v 14:17 | Karma článku: 13.60 | Přečteno: 303 | Diskuse

Dana Tenzler

Barvy v kuchyni (2) - průmyslová žlutá

Blíží se Velikonoce. Napadlo vás někdy, čím se vlastně barví velikonoční vajíčka? Jakými přírodními nebo umělými barvivy se dá jídlo barvit dnes a jak tomu bylo v minulosti? (délka blogu 3 min.)

25.3.2024 v 8:00 | Karma článku: 14.43 | Přečteno: 188 | Diskuse

Dana Tenzler

Barvy v kuchyni (1) - přírodní žlutá

Blíží se Velikonoce. Napadlo vás někdy, čím se vlastně barví velikonoční vajíčka? Jakými přírodními barvivy se dá jídlo barvit dnes a jak tomu bylo v minulosti? První díl seriálu o barvách.

21.3.2024 v 8:00 | Karma článku: 18.10 | Přečteno: 289 | Diskuse
VIP
Počet článků 400 Celková karma 18.67 Průměrná čtenost 922

Devátý nejhorší kuchař na světě, odpůrce politické překorektnělosti, začínající marťan, neúnavný konzument točeného kyslíku a jazykový dobrodruh ab incunabulis. Člen Analytického piva a Gustavu pro jazyk český. Správce Vojensko-českého slovníku.

Rána pro britskou monarchii. Princezna Kate má rakovinu, chodí na chemoterapii

Britská princezna z Walesu Kate (42) se léčí s rakovinou. Oznámila to sama ve videu na sociálních sítích poté, co se...

Smoljak nechtěl Sobotu v Jáchymovi. Zničil jsi nám film, řekl mu

Příběh naivního vesnického mladíka Františka, který získá v Praze díky kondiciogramu nejen pracovní místo, ale i...

Rejžo, jdu do naha! Balzerová vzpomínala na nahou scénu v Zlatých úhořích

Eliška Balzerová (74) v 7 pádech Honzy Dědka přiznala, že dodnes neví, ve který den se narodila. Kromě toho, že...

Pliveme vám do piva. Centrum Málagy zaplavily nenávistné vzkazy turistům

Mezi turisticky oblíbené destinace se dlouhá léta řadí i španělská Málaga. Přístavní město na jihu země láká na...

Kam pro filmy bez Ulož.to? Přinášíme další várku streamovacích služeb do TV

S vhodnou aplikací na vás mohou v televizoru na stisk tlačítka čekat tisíce filmů, seriálů nebo divadelních...