Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 21. 07. 2017 18:11 — Editoval sio (21. 07. 2017 18:12)
N-tá mocnina
Chcel by som sa opýtať ako sa dá efektívne vyriešiť takýto problém:
máme funkciu f(N) = 
+ 
+ 
+ 
+...+ 
.
Máme dané čísla N a M.
Našou úlohou je zistiť f(N) modulo M (zvyšok po delení). N aj M môžu byť veľké čísla preto to nie je možné robiť len postupným sčítavaním a umocňovaním.
Offline
#2 23. 07. 2017 01:50
- check_drummer
- Příspěvky: 4634
- Reputace: 99
Re: N-tá mocnina
↑ sio:
Ahoj, co použít Eulerovu větu?
A nebo aplikovat mod M vždy po několika vynásobeních - např. 
tak, že nejprve spočtu 
(to je 4) a následně 
(to je 2).
A nebo i oba tyto postupy jsou složité? - tj. hledáš algoritmus s časovou složitostí nižší než lineární v N?
"Máte úhel beta." "No to nemám."
Offline
#4 23. 07. 2017 13:33
- check_drummer
- Příspěvky: 4634
- Reputace: 99
Re: N-tá mocnina
Ta věta říká toto. Takže umožní zjednodušit mocniny - nahradit některé "části" mocnin číslem 1. pak tedy stačí již zkoumat jen mocniny 
, kde 
.
A dál lze pokračovat třeba tak, že vyjádříme exponent ve dvojkové soustavě a budeme postupně umocňovat a na druhou, opět na druhou atd. (průběžně modulo m) až získáme ty mocniny, které odpovídají číslicím 1 v dvojkovém rozvoji exponentu a výsledná čísla vynásobíme. tento postup lze použít i bez Eulerovy věty - a má čas. složitost nějakých n.log(n), tedy zejména ne kvadratickou.
"Máte úhel beta." "No to nemám."
Offline
#5 23. 07. 2017 16:13
Re: N-tá mocnina
Dlhšie som nad tým premýšľal ale je to na mňa zložité. Dokázal som urobiť len to že postupne som každé pre každé číslo našiel zvyšok po delení a potom som to sčítal. Dobré čísla s ktorými pracujem sa zmestia do pamäte PC ale nevýhoda je, že takto to má kvadratickú zložitosť. Mohli by ste mi prosím trošku podrobnejšie popísať ako to zjednodušiť ku tej n*log (n)?
Offline
#6 24. 07. 2017 23:17
- check_drummer
- Příspěvky: 4634
- Reputace: 99
Re: N-tá mocnina
↑ sio:
Počítejme 
. b vyjádři v binární soustavě jako b1b2b3b4... a vyjádři jako součin čísel 
pro ta i, pro která je bi nenulové.
"Máte úhel beta." "No to nemám."
Offline
#7 25. 07. 2017 10:49
Re: N-tá mocnina
Ak správne rozumiem tak mám napr. M=12 a N=10.
f(10) = 1 + 1 + 4 + 27 + 256 + 3125 + 46656 +823543+16777216+387420489+10000000000
Výsledok f(10) mod 12 mi hrubou silou vyšiel 6 (môže v tom byť chyba).
Takže pri hľadaní zvyšku pri čísle 10 by som išiel takto:
je v dvojkovej sústave 1001010100000010111110010000000000.
Pre akúkoľvek mocninu desiatky modulo 12 = 4 teda každý ak vynásobíme počet nenulových základov krát 4 dostaneme 4194304 a to modulo 12 = 4.
Takto vychádza zvyšok 4 čo je správne.
Ak by sme mali číslo 20.
No už číslo 15 by takto počítač nevedel spracovať keďže 
je v dvojkovej 11000010011101101100010110001011010100110110001100000000000 a to už je veľa. Nehovoriac o tom, že najväčšie číslo môže byť miliarda.
Offline
#8 25. 07. 2017 14:27
Re: N-tá mocnina
↑ sio:
Klasicky algoritmus na rychle umocnovanie - celkova zlozitost 
:
Code:
function a^e mod m:
if e == 0:
return 1
if e mod 2 == 0:
x = a^(e/2) mod m
return (x*x) mod m
else
x = a^((e-1)/2) mod m
return (a*x*x) mod mVsetky cisla su 
, pomocna premenna x sa pocita rekurzivne. V kazdom kroku rekurzie sa exponent zmensi aspon 2x, takze je tam len logaritmicky vela krokov a v kazdom sa robi len konstatny pocet operacii.
Ten pristup s mocninami 2-ky je v podstate to iste, ale takto je to jednoduchsie.
Offline
a to už je pri N = 
veľa. Nedá sa to nejak zrýchliť?#12 28. 07. 2017 17:04 — Editoval check_drummer (29. 07. 2017 14:12)
- check_drummer
- Příspěvky: 4634
- Reputace: 99
Re: N-tá mocnina
↑ sio:
Akorát Xellos mocní jedno číslo, ale sio potřebuje sečíst všechny mocniny 
... takže te nodhad složitosti je podle mě u sio správně.
Edit. Oprava - jedno umocnění zabere jen log(n) operací.
"Máte úhel beta." "No to nemám."
Offline
#13 01. 08. 2017 11:46 — Editoval mracek (02. 08. 2017 07:10)
Re: N-tá mocnina
Ja treba zadani vubec nepochopil, az kdyz to rozepsat.
M = 12, N = 10
f(N) = 0 na 0 + (1 na 1) + (2 na 2) + (3 na 3) ... + (N na N)
f(10) = 1 + 1 + 4 + 27 + 256 + ...
x = f(n) mod M = ?
Ja bych z toho vzal posledni cislici.
A pri nasobeni bych vzal tez posledni cislici.
(teda, pokud M<10)
0 na 0 = 1
1 na 1 = 1
2 na 2 = 4
3 na 3 = 9
4 na 4 = 16 * 16 -> 6 * 6 -> 36 -> 6
Treba to bude fungovat a vyhnes se silene velkym cislum.
Edit: Tak jsem nad tim rano premyslel, a nejspis bude potreba vic des. mist (M*10 nebo M*100, M*1000). nebo jine reseni.
Kdyz:
M = 3
5/3 = 3*1 + 2
15/3 = 3*5 + 0
25/3 = 3*8 + 1
115/3 = 3*38 + 1
Ale napadlo mne, ze existuje vzorec pro soucet aritmeticke a goniometricke rady, mozna by se dal pouzit + logaritmy a jit na to opacne. Dopocitavat mocninu M. A tady bych asi sel uz pre numericke metody a dopocitaval to zleva a zprava. I tak pri velkych cislech bude treba pouzit programy, co umi pocitat vsechny des. mista.
Offline