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
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
↑ 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?
Offline
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.
Offline
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
↑ 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é.
Offline
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
↑ sio:
Klasicky algoritmus na rychle umocnovanie - celkova zlozitost :
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 m
Vsetky 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
↑ 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í.
Offline
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