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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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)

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

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) = $0^{0}$ + $1^{1}$ + $2^{2}$ + $3^{3}$ +...+ $N^{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: 2365
Reputace:   64 
 

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ř. $3^3 \mod 5$ tak, že nejprve spočtu $3^2 \mod 5$ (to je 4) a následně $4.3 \mod 5$ (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?


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

#3 23. 07. 2017 10:31

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: N-tá mocnina

Ahoj,

lineárna zložitosť by vpohode stačila.

Ako by som vyzeral algoritmus cez tú Eulerovu vetu?

Ďakujem.

Offline

 

#4 23. 07. 2017 13:33

check_drummer
Příspěvky: 2365
Reputace:   64 
 

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 $a^x$, kde $x< \varphi (m) $.
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.


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

#5 23. 07. 2017 16:13

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

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: 2365
Reputace:   64 
 

Re: N-tá mocnina

↑ sio:
Počítejme $a^b$. b vyjádři v binární soustavě jako b1b2b3b4... a $a^b$ vyjádři jako součin čísel $a^{2^i}$ pro ta i, pro která je bi nenulové.


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

#7 25. 07. 2017 10:49

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

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:
$10^{10}$ 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 $15^{15}$ 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

Xellos
Příspěvky: 515
Škola: MFF CUNI, Bc. (13-16)
Reputace:   34 
 

Re: N-tá mocnina

↑ sio:
Klasicky algoritmus na rychle umocnovanie - celkova zlozitost $O(N\log{N})$:

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 m

Vsetky cisla su $\le m$, 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

 

#9 25. 07. 2017 15:18

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: N-tá mocnina

↑ Xellos:
Skúsil som to ale zistil som, že to má veľmi veľkú zložitosť lebo ak to robím pre každé číslo 1 až N tak to vychádza tuším $O(\frac{N}{2}N\log{N})$ a to už je pri N = $10^{9}$ veľa. Nedá sa to nejak zrýchliť?

Offline

 

#10 25. 07. 2017 16:57

misaH
Příspěvky: 8347
 

Re: N-tá mocnina

↑ sio:

no - ja neviem.

prečítal si si príspevok od Xellosa poriadne?

On píše niečo úplne iné ako ty.

Offline

 

#11 25. 07. 2017 22:43

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: N-tá mocnina

↑ misaH:
Jasné, nedošlo mi to.

Offline

 

#12 28. 07. 2017 17:04 — Editoval check_drummer (29. 07. 2017 14:12)

check_drummer
Příspěvky: 2365
Reputace:   64 
 

Re: N-tá mocnina

↑ sio:
Akorát Xellos mocní jedno číslo, ale sio potřebuje sečíst všechny mocniny $k^k$... takže te nodhad složitosti je podle mě u sio správně.

Edit. Oprava - jedno umocnění zabere jen log(n) operací.


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

#13 01. 08. 2017 11:46 — Editoval mracek (02. 08. 2017 07:10)

mracek
Příspěvky: 155
Reputace:   
 

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

 

#14 01. 08. 2017 19:22

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: N-tá mocnina

↑ mracek:

Veľkým číslam sa dá vyhnúť pomocou algoritmu pre rýchle umocňovanie, ktorý uviedol vyššie Xellos. Problémom však ostáva vysoká časová zložitosť, N môže byť aj 10 miliard.

Offline

 

#15 02. 08. 2017 07:14

mracek
Příspěvky: 155
Reputace:   
 

Re: N-tá mocnina

↑ sio: Dyt nic nerikam, jen premyslim nad jinymi zpusoby.

Offline

 

#16 02. 08. 2017 09:58

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: N-tá mocnina

↑ mracek:

Ano, a za to Vám ďakujem. Jedine tak sa dajú riešiť úlohy.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson