3.4. Diszkrét értékű függvények kiszámítása

Eddig olyan problémákat oldottunk meg, ahol igen-nem választ vártunk. Ebben a fejezetben olyan problémákat tekintünk, ahol valamit ki kell számítani (ahogy a Turing-gépek közt is vannak eldöntő és kiszámító Turing-gépek). Ehhez először szükségünk van egy olyan utasításra, amivel az intervallum-értékű számítás közben outputot tudunk generálni.

A számítás kezdetén az output még üres, vagyis a üres szó. Vegyük fel az operátorok közé az utasítást, amely a számítási sorozat egy korábbi intervallum-értékét kapja operandusként, és azt nem változtatja meg, viszont az outputhoz hozzáfűz egy -est, ha nemüres, illetve egy -t, ha . A számítás végére egy -beli outputot fog generálni a számítás.

Azt mondjuk, hogy egy diszkrét függvény hatékonyan kiszámítható intervallum-értékű számítással, ha van olyan rövid (logaritmikus tárigényű) algoritmus, ami minden lehetséges inputra megadja azt a számítási sorozatot, ami az output sorozatot generálja.

A fejezet alfejezeteiben a pozitív egész számok prímfaktorizációját, illetve a diszkrét logaritmus problémát tekintjük. A matematikai érdekességükön kívül mindkét problémának fontos szerepe van a gyakorlatban, pl. kriptográfiai algoritmusokkal kapcsolatosan.

3.4.1. Prímfaktorizáció

Közismert tény, hogy minden egynél nagyobb természetes szám egyértelműen felbontható prímtényezők szorzatára. Az is egyszerűen belátható, hogy a prímszámok száma végtelen, köztük viszont bármekkora méretű hézag lehet: vagyis minden természetes számhoz található olyan prímszám, hogy az ennél nagyobb prímszámok, mind nagyobbak -nél is. 2004-ben M. Agrawal, N. Kayal and N. Saxena bizonyították, hogy annak eldöntése hogy egy szám prím-e P-ben levő probléma. Ezzel szemben a prímtényezőkre bontás, illetve a prímfaktorizáció problémájára jelenleg nem ismert determinisztikus polinomiális idejű algoritmus hagyományos számítógépekre (illetve Turing-gépre). A prímfaktorizáció problémáját a következőképpen adjuk meg: adott egy természetes szám, adjuk meg egy valódi osztóját, illetve jelezzük, ha a szám prím. Világos, hogy a valódi osztóra, illetve az eredeti számot a valódi osztóval osztva az eredmény kisebb számra újra lefuttatva az algoritmust, a teljes prímtényezős felírás is megadható.

Most egy intervallum-értékű számítást adunk, ami az input hosszának négyzetével arányos lépésszám után az inputként adott természetes szám egy prímtényezőjét adja outputként, illetve -t ír ki, ha az szám prím. Legyen az input bináris kódban adva. Ekkor a hossza felfelé kerekítve, jelöljük -nel ezt, vagyis hogy hány biten írhatjuk le az inputot (az feltételnek megfelelően ). Ennek megfelelően legyen az input bináris alakja: . Az algoritmusunk outputként az legnagyobb (de saját magánál kisebb) osztóját fogja adni bináris kódban, jelöljük a számítás eredményét -el (ennek el kell férnie biten). A számítást egy példán, , is bemutatjuk. Ekkor , az input binárisan: .

A számítási sorozat első eleme most is . Először az input reprezentálásához legyártjuk a üres és a teljes intervallum-értékeket: Ehhez a -et saját magával eltoljuk jobbra, majd vesszük ennek (vagyis a -nek) és az eredeti -nek a diszjunkcióját, illetve a konjunkcióját. A számítási sorozat következő eleme, legyen az inputnak megfelelően:

Az input leírása a hosszával ( -nel) lineáris számú lépésben megtörténik. A 3.4. ábrán mutatjuk a példánkban az input reprezentációját.

3.4. ábra - Az Az input intervallum-értékű reprezentációja. input intervallum-értékű reprezentációja.

Az input intervallum-értékű reprezentációja.

Az input és az output, vagyis a számok reprezentációjának rögzítése után az algoritmusunk több egymást követő alprogramból áll, ezeket vesszük most sorra.

3.5. ábra - A A és intervallum-értékek esetre. és A és intervallum-értékek esetre. intervallum-értékek A és intervallum-értékek esetre. esetre.

A és intervallum-értékek esetre.

Ezután a párhuzamos számítás elvégzéséhez ugyanolyan intervallum értékeket állítunk elő, mint a SAT problémánál is tettük (lásd a 3.1. ábrát), most darabot, az első darabot -vel, a második darabot pedig -vel jelöljük. Legyen így

ahol és

ahol . Ezen intervallum-értékek előállítása az input hosszával lineáris számú lépésben történik. A példánkra ennek a résznek az eredményét a 3.5. ábrán mutatjuk.

3.6. ábra - A A és intervallum-értékek és a értékek által reprezentált egészek. és A és intervallum-értékek és a értékek által reprezentált egészek. intervallum-értékek és a A és intervallum-értékek és a értékek által reprezentált egészek. értékek által reprezentált egészek.

A és intervallum-értékek és a értékek által reprezentált egészek.

3.7. ábra - A A és intervallum-értékek és az általuk reprezentált egészek. és A és intervallum-értékek és az általuk reprezentált egészek. intervallum-értékek és az általuk reprezentált egészek.

A és intervallum-értékek és az általuk reprezentált egészek.

A és értékek binárisan kódolnak egészeket (minden olyan egészet, ami biten ábrázolható), ahogy a 3.6. és 3.7. ábrák is mutatják.

3.8. ábra - A A és intervallum-értékek által reprezentált számok szorzatai. és A és intervallum-értékek által reprezentált számok szorzatai. intervallum-értékek által reprezentált számok szorzatai.

A és intervallum-értékek által reprezentált számok szorzatai.

Az algoritmusunk folytatásaként ezeket a binárisan kódolt egészeket szorozzuk össze. A -k által kódolt első tényezőt a -k által kódolt második tényezővel. Figyeljük meg, hogy minden lehetséges első tényező minden lehetséges második tényezővel „párban” előfordul az intervallum-értékeink valamely részén. A bináris szorzás megvalósítható logikai áramkörökkel, így az intervallum-értékű számításunkban logikai műveletekkel elvégezhető. Ehhez legfeljebb az input-hosszal négyzetes számú lépésre van szükség. Jelölje a szorzás eredményét intervallum-értékekkel (a szorzatnak el kell férnie biten). A példánkra ezt a 3.8. ábrán mutatjuk (az ábrán logikai képlettel is mutatjuk a kiszámítás egy lehetséges módját).

3.9. ábra - A A és intervallum-értékek egyenlőségének vizsgálata. és A és intervallum-értékek egyenlőségének vizsgálata. intervallum-értékek egyenlőségének vizsgálata.

A és intervallum-értékek egyenlőségének vizsgálata.

Az algoritmus következő lépése az egyenlőség tesztje, vagyis annak vizsgálata, hogy a szorzat hol egyezik meg az inputként megadott számmal. Az input értékét a szorzat utolsó értékéhez hasonlítjuk, a szorzat többi értékét az üres intervallumhoz (mintha az inputot több biten vezető -kal ábrázolnánk). Két intervallum-érték összehasonlítása a logikai ekvivalencia operátorral történik, végül a páronként kapott összehasonlítások konjunkciója adja meg azt az intervallum-értéket, ami azt mutatja meg, hogy az ábrázolt számok hol egyeznek meg. Tehát legyen értéke , és értéke ha . Az ezt követő darab érték pedig legyen ahol . Végül legyen az intervallum-érték értéke . Az algoritmusnak ez a része is lineárisan sok lépést tartalmaz az input hosszának függvényében. A példánkban ezt a 3.9. ábrán mutatjuk.

Világos, hogy az értéke pontosan akkor üres, ha az input prímszám. Ha az nem prímszám, akkor az nem üres. Továbbá, a feltételünknek megfelelően, az biten ábrázolható legnagyobb szám négyzete, ami a értékek legelső részén van kódolva, biztosan nagyobb, mint az biten leírható . Ennek megfelelően az biztosan olyan, hogy nincs alakú komponense.

3.10. ábra - A kódolt szorzótényező értéke.

A kódolt szorzótényező értéke.

Már csak annyi maradt, hogy dekódoljuk az osztót és kiírjuk az outputra. Ehhez tekintsük a értékekkel reprezentált szorzótényezőket, és állapítsuk meg a kódolt értéket az által adott első helyen. A példában ezt a 3.10. ábra illusztrálja.

3.11. ábra - Az output meghatározása.

Az output meghatározása.

Ehhez az eltolás operátorok kombinált alkalmazásával kivágjuk a kódolt szám jelentette bit értékét. Először toljuk el balra a intervallum-értékeket a intervallum-értékkel (lásd a 3.11. ábrát). Az így kapott értékekben a válaszbitek az intervallum elején jelennek meg. (Figyeljük meg, hogy esetén, azaz, ha prímszám, a balra tolással minden értéke az üres intervallum lesz.) Legyen , vagyis a kiindulási intervallumunkat magával szorozzuk össze annyiszor, hogy a szorzat felírásában -szer szerepeljen. Ekkor éppen olyan hosszú, mint a (ez az intervallum-érték a „legfinomabb felbontású” a számítás során) komponenseinek hossza (külön-külön). Tulajdonképpen ez a „bitek” hossza a számításunknak abban a részében, amikor a legsűrűbb az információtartalma egy intervallum-értéknek. Ezután legyen . A példában ez a 3.11. ábrán látható. Végül az algoritmus kiírja az outputot a alapján bitenként. Esetünkben ez , ami a bináris kódja. És valóban a a legnagyobb valódi osztója. Az output meghatározása és kiírása is lineáris lépésszámot igényel az input hosszának függvényében.

Az algoritmus legtöbb lépése a szorzás művelet megvalósításához kellett, ez alapján a teljes algoritmus lépésszámigénye négyzetes az input hosszának függvényében. Az algoritmus uniform abban az értelemben, hogy a lehetséges bites tényezők szorzását elég egyszer elvégezni, több lehetséges input faktorizációjához is felhasználhatóak ezek az intervallum-értékek. Ráadásul, ha egyszer már elvégeztük ezt a szorzást, akkor tetszőleges további biten ábrázolható szám faktorizációja már lineáris lépésszámmal megy az függvényében.

3.4.2. Diszkrét logaritmus probléma megoldása

A diszkrét logaritmus probléma megfogalmazásával kezdjük ezt az alfejezetet. Legyen adott . A feladat az, hogy adjunk meg olyan kitevőt, amelyre teljesül az, hogy és ugyanazt a maradékot adja -vel osztva (matematikai jelöléssel: ). Az általánosság csorbítása nélkül feltehetjük, hogy . Hagyományos számítógépen (illetve Turing-gépen) nem ismert olyan determinisztikus algoritmus, amely polinomiális lépésszámmal megoldaná a problémát általánosan (tetszőleges input és értékre). Sokszor a értéke prímszám.

A következőkben egy olyan intervallum-értékű algoritmust adunk meg, amely az input hosszának köbével arányos lépésszámban oldja meg a feladatot. Az algoritmus működését grafikusan az , és példán szemléltetjük.

Az számítási sorozat most is a értékkel indul. Az algoritmus most is több alrészből áll. Az első részben itt is előállítjuk az és a intervallum-értékeket, valamint az inputot reprezentáljuk hasonlóan a prímfaktorizációs algoritmushoz. Mivel a értéke a legnagyobb, ez szabja meg, hogy hány biten tudjuk és fogjuk ábrázolni az input értékeket. Legyen most az az érték, ahány bitet foglal a szokásos bináris reprezentációja ( a kettes alapú logaritmusának felfele kerekített értéke). Az , a ás a értékét is biten, és ennek megfelelően ennyi intervallum-értéken jelenítjük meg. Mivel a ciklikus csoport (a maradékok csak értéket vehetnek fel, így ismétlődnek), lennie kell megoldásnak a tartományban, ennek megfelelően az output megadásához is elegendő lesz bit. A példánkban , így minden input értéket ennyi intervallum-értékkel reprezentálunk, ahogy a 3.12. ábra mutatja.

3.12. ábra - Az input kódolása intervallum-értékekkel (Az input kódolása intervallum-értékekkel ( ). ).

Az input kódolása intervallum-értékekkel ( ).

Az algoritmus alapötlete hasonlít a prímfaktorizáció alapötletére, itt is legyártjuk az összes lehetséges kitevőt (a tartományban legalábbis), elvégezzük a hatványozást a maradékosztályban, és ellenőrizzük az eredményt. Ki fogjuk használni a szorzáshoz hasonlóan az osztás, illetve a maradék meghatározása is kiszámítható négyzetes lépésszámú algoritmussal (vagy áramköri elemekkel).

Tehát állítsuk elő a lehetséges értékeket, konstruáljuk meg az intervallum-értékeket -nek megfelelően, ahogy korábban is tettük már. A példánk esetén ( ) ez a 3.13. ábrán látható.

3.13. ábra - A lehetséges kitevők intervallum-értékekkel és jelentésük.

A lehetséges kitevők intervallum-értékekkel és jelentésük.

A számítás lépésszáma eddig az input hosszának lineáris függvényével adható meg. Most jön a számítás legbonyolultabb része: a hatványozás a maradékosztályban.

Most legyen három szám és adott - intervallum-értéken (bináris reprezentációban). Ekkor kiszámítható az a darab intervallum-érték, ami minden esetén az pontban az értéket kódolja (ahol az és karakterisztikus függvényei kódolják az , illetve értékeket az pontban). Ez a számítás logikai áramkörökkel megvalósítható, és mind a szorzás, az osztás, illetve a maradék képzés művelete a -tel arányos lépésszámban kiszámítható.

Először kiszámoljuk az , , , , értékeket, mindegyik ábrázolható darab intervallum-értéken, az -edik az értékeken. A példánkban ez a 3.14. ábrán látható eredményt adja.

3.14. ábra - Hatványozás (5 maradékosztályában).

Hatványozás (5 maradékosztályában).

Tetszőleges szóba jövő kitevőt bináris számként írva a hatványozás a következő szorzat alakba írható a modulo osztályban is. E technikai ötlet segítségével az előzőekben kiszámolt 2 hatványok (modulo ) értékeiből bármely hatványozott érték meghatározható. Legyen az értéke a következőképpen adott: , és ha (a segítségükkel azt tudjuk megmondani, hogy utolsó bitről lesz-e szó). Számoljuk most ki a értékeket (ehhez az előzőekben kiszámolt értékek kellenek, illetve az ugyancsak megkonstruált intervallum-értékei). A példánkban ezek az intervallum-értékek a 3.15. ábrán láthatóak.

3.15. ábra - A A és a értékek meghatározása a példában. és a A és a értékek meghatározása a példában. értékek meghatározása a példában.

A és a értékek meghatározása a példában.

A számítási sorozat ekkor a következőképpen folytatódik Legyen ( intervallum-értéken), továbbá legyen . Ezeket az értékeket is mutatja a 3.15. ábra. A értékek ekkor éppen a értékeket kódolják, a példánkban a a értékeket, a számokat. Az algoritmus következő része az egyenlőség tesztelés, hasonlóan a prímfaktorizációnál látott lépésekhez. A intervallum-értékeit az inputként adott intervallum-értékeihez hasonlítjuk a logikai ekvivalencia operátorral, végül az összehasonlítások konjunkcióját vesszük. Tehát legyen értéke ( ), valamint legyen a a értékek konjunkciója. Az így kapott intervallum-érték mutatja, hogy mely érték oldja meg a feladatot. A példánkban ezek az intervallum-értékek a 3.16. ábrán láthatóak.

3.16. ábra - Egyenlőség tesztelése a példában.

Egyenlőség tesztelése a példában.

Tudva, hogy a megfelelő értékek ott vannak kódolva ahol a jelzi, következhet az eredmény kiírása. Ellenőrizhető, hogy a következő számítási sorozatrész a első komponensét választja ki. Legyen a számítási sorozatban annak az intervallum-értéknek az indexe, amely -t adja meg. Ekkor a következő elemek:

  • .

Tudjuk, hogy az megoldás esetén másik megoldás is van a vizsgált intervallumban, sőt ez a megoldás megelőzi az intervallumos kódolásban az -t, hiszen az az intervallum-értékek legvégén van kódolva. Ezért nem vész el a megoldásunk, ha az aktuális intervallum-értéket, -et eltoljuk jobbra -val (vagyis a számítás során használt „bithosszal”, valójában -nal) oly módon, hogy a kitolt rész eltűnjön (ehhez előbb jobbra, majd balra, majd megint jobbra tolunk). Ez három lépés. Ezzel elértük, hogy az aktuális intervallumunk mindenképpen üres résszel kezdődjön. Ezután

adja a hosszúságú egykomponensű intervallum-értéket, amely pont az első helyen kódolt megoldás helyét jelöli. Legyen

  • (ahol ).

Ezután már ezt csak ki kell íratni, vagyis legyen

  • (ahol ).

Ellenőrizhető, hogy a kiírt bináris kód egy olyan értéket ad, amelyre , az intervallum-értékekkel számoló algoritmus ezt a bemenet hosszának köbével arányos lépésszámban produkálja. A példánkban az eredmény ami a számot kódolja három biten, , ami 5-tel osztva tényleg 2 maradékot ad, ahogy vártuk.