A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Ha , a rutin -ba értékétől függetlenül -et ír. Különben -en addig végez -vel való egész osztást, amíg az -ra csökken. Közben minden lépésben aktuális tartalmát négyzetre emeli. Ha tehát , akkor a program lépést végez, és végül is -be az eredeti érték -edik hatványa kerül. Vizsgáljuk meg, mi történik közben -val. Valahányszor aktuális értéke páratlan, megszorzódik aktuális értékével. Az eljárás tehát az 1734. gyakorlat szorzására emlékeztet, csak most összeadás helyett szorzás az elemi lépés. Ennek megfelelően az eredmény eredeti értékének -edik hatványa (-ben is az eredeti értéket véve). A bizonyítás lényegében ugyanaz, mint a gyakorlat esetében, így nem részletezzük. Azt, hogy a program azt számolja-e ki, amit kell, nyilván csak a készítője mondhatja meg. Nem valószínű azonban, hogy szükség van és értékének megváltoztatására. Szerencsésebb megoldásnak tűnik, ha az első sort a következő háromra cseréljük:
Sali Attila (Budapest, Fazekas M. Gyak. Gimn., IV. o. t.)
Megjegyzés. A program aránylag kevés művelettel állítja elő -edik hatványát. Mint láttuk, ehhez szorzás helyett legfeljebb műveletre van szüksége. Hasonló feladat az (, , , , , ) vektorokból a | |
vektor előállítása (ez lényegében hosszú számok szorzásának felel meg). Itt is van a triviális lépésnél lényegesen gazdaságosabb megoldás: nagyságrendileg lépés is elegendő. Nem tudjuk azonban, hogy ennél lényegesen kevesebb lépés nem elegendő-e a művelet végrehajtásához.
|