Aktuální vydání

celé číslo

12

2020

Systémy DCS pro kontinuální a dávkové výrobní procesy

Provozní analytická technika

celé číslo

Integrační vyhledávání v prvočíslech

Petr Klán

 
Integrační složka (I) patří k základu regulace procesů s dynamikou. Samostatně ji však lze použít i v případě procesů, které jsou plně statické a nedochází v nich k žádným časovým změnám. Příkladem je vyhledávání v tabulkách prvočísel. Dále je ukázáno, že i při vyhledávání prvočísel lze využít obvyklé postupy známé z PID regulace a že dobře nastavený I algoritmus pracuje velmi efektivně – podobně jako v případě dynamických procesů.
Integral term (I) belongs to the basics terms of dynamic system control. However it is possible to use it separately for fully static processes, without any time changes. One example is a looking up in prime tables. Hereby it is shown that it is possible to use common methods known from PID control in case of primes searching too and that properly tuned I algorithm works very effective similar to dynamic processes.
 

1. Úvod

Integrační složka PID regulátoru náleží vzhledem ke své schopnosti odstraňovat regulační odchylku k nejčastěji používané složce v regulaci. Velká pozornost je proto věnována také jejímu nastavení. Činnost podobnou I algoritmu vyvíjí např. lidský mozek při řízení automobilu. Integrační algoritmus sám je zároveň modelem dynamického systému. V případě samotné I složky PID regulátoru lze říci, že jeden dynamický systém reguluje jiný dynamický systém. Dokáže však dynamický systém „regulovat“ (nastavit) systém statický?
 
Z principu by to neměl být problém. Opačně je to možné částečně. Jde o případ, kdy statický systém (P regulátor) reguluje dynamický systém. V případě neintegračních procesů je známo, že P regulátor sice zmenšuje regulační odchylku, její úplné odstranění je ale možné pouze v singulárním případě nekonečného zesílení regulátoru. Podobnou funkci plní i tzv. signálové sledovače. Když se však postaví I regulátor proti statickému procesu, může při dobrém nastavení rychle odstranit jakoukoliv regulační odchylku.
 
Prvočíslem je číslo větší než jedna, které nemá žádné dělitele kromě jedné a sebe samého. Například číslo 17 je prvočíslo, protože má pouze dva dělitele: čísla 1 a 17. Tabulek známých prvočísel existuje velmi mnoho. Dobře dostupné jsou např. The Prime Pages [4], kde lze kromě tabulek s prvními 50 miliony prvočísel získat i mnoho výsledků výzkumu z oboru teorie čísel.
 
K pokusům s I algoritmem bude dále použita tabulka s prvními 30 miliony prvočísel. „Regulační“ úlohou bude možné co nejrychleji a s minimem energie nalézt pořadí libovolně vybraného prvočísla.
 

2. Prvočíselný proces

Prvočísla jsou uspořádána do indexovatelného pole tvaru
 
y = p(u)          (1)
 
kde
u je vstupní index pořadí prvočísla od počátku (u = 1; 2... 30 000 000),
y prvočíslo s pořadím u.
 
Například platí, že 2 = p(1), 29 = p(10), 541 = p(100), 7 919 = p(1 000), 15 485 863 = p(1 000 000) atd. Pole y = p(u) bude v dalším nazýváno prvočíselným procesem.
 
V PID (nejen) regulaci je obvyklé nejprve se zabývat zesílením procesu K. Při zběžném pohledu na statickou charakteristiku prvočíselného procesu na obr. 1 se zdá, že jde o téměř lineární proces. Analýza uvedených hodnot však prokáže, že jde o omyl, neboť např. p(1)/1 = 2, p(10)/10 = 2,9, p(100)/100 = 5,41, p(1 000)/1 000 = 7,919, p(1 000 000)/1 000 000 = 15,485 863 atd. Zesílení trvale roste, i když od jednoho milionu velmi mírně. Skutečný průběh zesílení pro prvních 20 milionů prvočísel (další růst je nepatrný) ukazuje obr. 2.
 
Průměrné zesílení prvočíselného procesu je přibližně K = 18.
 
Z teorie čísel je zřejmé [5], že pro určité prvočíslo p(u) platí, že p(u) ~ u ln(u), a pro odpovídající zesílení tedy K(u) ~ ln(u), kde notace ~ představuje asymptotickou rovnost, tj.
 
vztah          (2)
 
Jinými slovy, pro velká u je možné zaměnit K(u) za odhad ln(u). V případě u = 30 000 000 je hodnota
 
vztah          (2a)
 
a
ln(30 000 000) = 17,2, což představuje přibližně desetiprocentní chybu.
 
Podle zpřesněného asymptotického odhadu p(u) ~ u ln(u) + u(ln(ln(u)) – 1           (3)
je
 
K(u) ~ ln(u) + ln(ln(u)) – 1          (3a)
 
a tomu odpovídá zpřesněný odhad pro K(30 000 000)
 
K(30 000 000) = ln(30 000 000) + ln(ln(30 000 000)) – 1 = 19,06          (3b)
 
Dalším obvyklým a potřebným parametrem procesu je časová konstanta procesu. Prvočíselný proces je statický, a proto je časová konstanta nulová.
 

3. Použití I algoritmu

Úloha je prostá: k dopředu známému prvočíslu potřebujeme co nejrychleji a s co nejmenším množstvím úsilí nalézt jeho pořadí. Pro ověření, že nejde o triviální úlohu, je možné vyzkoušet i ruční hledání. Buď známým prvočíslem, např. y = 141 661 147 = p(ux). Ručním řešením může být např. následující posloupnost deseti kroků (počátek představuje stav u0 = 1 a y0 = 2):
  • u1 = 10 000 000, y1 = 179 424 673
  • u2 = 9 000 000, y2 = 160 481 183
  • u3 = 8 000 000, y3 = 141 650 939
  • u4 = 8 000 200, y4 = 141 654 581
  • u5 = 8 000 400, y5 = 141 658 373
  • u6 = 8 000 500, y6 = 141 660 191
  • u7 = 8 000 550, y7 = 141 661 081
  • u8 = 8 000 553, y8 = 141 661 129
  • u9 = 8 000 554, y9 = 141 661 139
  • u10 = 8 000 555, y10 = 141 661 147
 
Výsledek hledání ukazuje, že dané prvočíslo má pořadí u = 8 000 555, platí tedy, že 141 661 147 = p(8 000 555). Ruční hledání je namáhavé již jen porovnáváním velkých čísel a velmi záleží na prvním odhadu pořadí u1. Jistě, lze tady využít i informaci o průměrném zesílení v prvočíselném procesu K = 18.
 
Stejnou úlohu je možné řešit automaticky s použitím I algoritmu. Základní uspořádání ukazuje obr. 3. Schematicky jde o obdobu klasické zpětnovazební regulace s procesem a regulátorem. Žádanou hodnotou w je prvočíslo, jehož pořadí se zjišťuje. Výstupem I regulátoru bude v případě rovnosti y = w přímo pořadí prvočísla.
 
Vzhledem k tomu, že výstupem I regulátoru mohou být reálná čísla a vstupem procesu jsou přirozená čísla, je na výstupu regulátoru použito zaokrouhlení známé jako u = floor(x), které x zaokrouhluje k nejbližšímu přirozenému číslu, které je nižší nebo rovné x. Například floor(3,71) = 3 apod. V matematické sazbě se funkce floor značí také jako └x.
 
Použití I regulátoru vychází ze spojitého případu [1]. Jestliže má statický proces zesílení K a integrační regulátor je určen přenosem Kc/(TIs), kde Kc je zesílení regulátoru a TI integrační časová konstanta, přenos zpětnovazebního uspořádání podle obr. 3 bude
 
vztah         (4)
 
s žádoucím zesílením 1 a možností urychlit proces vyhledání prvočísel snižováním integrační konstanty TI (pro zjednodušení Kc = 1). Integrační algoritmus je použit v běžném přírůstkovém tvaru
 
vztah          (5)
 
kde
e(k) = w y(k)
a k označuje krok. Vstupem prvočíselného procesu je └u(k), výstupem
 
y = pu(k)
 
v každém kroku k. Úloha je vyřešena v případě, že y(k) = w, kdy výstup regulátoru └u(k) určuje pořadí prvočísla.
 
V programu Matlab (obdobně Scilab) může být odpovídající kód jednoho kroku:
y = p(floor(u));
e = w – y;
u = u + (1/TI)*e;
 
Při přetečení výstupu integračního regulátoru u je nutné vypnout integraci (tzv. antiwindup). To zabezpečí následující jednoduché omezení pro případ práce se souborem s 30 miliony prvočísel:
if (u > 30000000) u = 30000000; end
if (u < 1) u = 1; end
 
 

4. Nastavení I algoritmu

Přirozeným nastavením integrační časové konstanty (něco jako vyvážené nastavení v případě PI regulátoru [2]) je
 
TI = K          (6)
 
Nastavení zabezpečuje vyhledání pořadí prvočísla v podstatě ve třech krocích, jak lze ověřit na obr. 4 pro různá prvočísla: w = 86 028 121, w = 141 650 939 a w = 533 000 389. Označení vodorovné osy k znamená krok. Dynamika průběhu se mírně liší vzhledem k měnícímu se zesílení. Odpovídající průběh vývoje prvočíselného pořadí u je na obr. 5. Při porovnání s ručním vyhledáváním autora tu je zřejmé více než trojnásobné zrychlení vyhledávacího procesu. Navíc jde o předvídatelné průběhy s ohledem na počet kroků, což je v případě ručního vyhledávání téměř nedosažitelné. V případě uvedeného odhadu a pro velká
prvočísla lze s výhodou použít nastavení integrační časové konstanty ve tvaru
 
TI = ln w          (7),
 
neboť w = p(u) je hledané u-té prvočíslo a vzhledem k ln w = ln u + ln ln u
 
tedy odhad K(u) plus malé číslo dané dvojitým logaritmem, který roste velmi pomalu, bude odhad integrační časové konstanty vždy o něco málo vyšší než skutečné zesílení, což zlepšuje bezpečnost I algoritmu vzhledem k nestabilitě a přitom zpomaluje vyhledávání v prvočíselném procesu jen nepatrně.
 

5. Závěr

Článek ukazuje, jak je možné použít integrační algoritmus k řešení problému tak vzdáleného běžné regulaci, jakým je vyhledávání v prvočíslech nebo relačních databázích. Takové vyhledávání přitom funguje efektivně a s minimálním množstvím úsilí. Odpovídá tzv. dobrému nastavení regulátoru [3].
 
Názorně je zde ukázán přínos automatického vyhledávání, kdy velmi jednoduchý gradientní algoritmus, na rozdíl od ručního vyhledávání, poskytuje předvídatelné výsledky bez ohledu na velikost prvočísel, a to v rozsahu použitých velikostí.
 
Článek navrhuje nastavení použitého regulátoru. Z teorie čísel je známo, že předpovědi, které se týkají prvočísel, bývají zrádné.
 
Určitá vlastnost např. platí pro prvních n prvočísel a potom náhle ztratí platnost. Vyvstává tady proto otázka: funguje navržený I regulátor s nastavením (7) pro každé prvočíslo větší než 30 milionů?
 
Literatura:
[1] KLÁN, P. – GOREZ, R.: Process Control. Praha, FCC Public, 2011.
[2] KLÁN, P. – GOREZ, R.: Nastavení regulátorů chránící akční členy. Automa, 2005, č. 2, s. 50–52.
[3] KLÁN, P.: PI regulátory s dobrým nastavením. Automa, 2005, č. 6, s. 50–51.
[4] CALDWELL, CH.: The Prime Pages (The First 50 000 000 Primes) [online]. [cit. 2. 1. 2016]. Dostupné z: <primes.utm.edu>.
[5] KLÁN, P.: Čísla: Vztahy, vhledy a věčné inspirace. Praha, Academia, 2014.
 
Petr Klán, VŠE v Praze
 
 
Obr. 1. Statická charakteristika prvočíselného procesu
Obr. 2. Průběh zesílení prvočíselného procesu
Obr. 3. Vyhledávání v prvočíslech s použitím I algoritmu
Obr. 4. Průběh automatického vyhledávání prvočísel y pro w = 86 028 121, w = 141 650 939 a w = 533 000 389
Obr. 5. Vývoj prvočíselného pořadí u při vyhledávání prvočísel pro w = 86 028 121, w = 141 650 939 a w = 533 000 389