Matematické Fórum

↑ liamlim:
Ahoj, těch hodnot a máš a každou takovou rovnici jsi schopen vyřešit v konstantním čase - nebo ne?
Resp. v jakém čase jsi schopen spočítat operace s čísly velkými jako n - v konstantním nebo v log(n)? Pak by ta šložitost byla

↑ check_drummer:

Já teď něčemu úplně nerozumím. Jak umím konstantně vyřešit kvadratickou rovnici? Buď potřebuji odmocninu, která má časovou složitost logaritmickou nebo nějaké půlení intervalů, které taky není konstantní, ne?

edit: No a já právě nevím, jaký je nejlepší možný přístup. Navíc má celkem nepěkné meze a vystupuje v sumě, což mi komplikuje určení, co bude nejlepší.

↑ laszky:
Ahoj, ale jak zjistíš rychle, že je dané číslo prvočíslem? Pokud podle tabulek, tak to mohu tabulku použít i pro n. :-)

↑ laszky:

To úplně nefunguje. Stejně budeš muset všechna čísla vzít alespoň jednou do ruky. Nějak je označit nebo tak něco. To zabere konstantní čas stejně jako prosté vydělení a ověření zda se nejedná o dělitel.

↑ check_drummer:

No, ma uvaha byla nasledujici:

Kdyz budu brat v uvahu pouze cisla , pro snizim casovou slozitost na polovinu.

Pokud budu brat v uvahu pouze cisla , , pro snizim ji na tretinu, atd.

Pokud na zacatku takto vyradim nasobky prvocisel, ziskam  .

Vidim v tom pouze praci navic v pocatecnim stanoveni tech omezujicich podminek.

Ale urcite tim nechci liamlimovi branit v testovani sudych cisel ;-)

↑ MichalAld:

Já si jen pohrával s nějakými rovnostmi a zjistil jsem, že mám problém s vyjádřením té složitosti. Ten algoritmus je nanic, je pomalý. Najde nějaký dělitel zadaného čísla.

↑ check_drummer:

Ok. Tak jednoducha otazka: Usetrim cas, kdyz zkontroluju dvojku a pak uz jenom cisla , ? Ja se na ta suda cisla vubec nebudu ptat, proste je preskocim ;-)

↑ liamlim:

Podle wiki je nejvetsi zname prvocislo , tabelovano jsem narychlo nasel prvocisla az do , tj az do 1000 miliard = 1 bilionu. ;-) Takze v tomto neni zadny prakticky problem.

laszky napsal(a):

↑ liamlim:

Podle wiki je nejvetsi zname prvocislo , tabelovano jsem narychlo nasel prvocisla az do , tj az do 1000 miliard = 1 bilionu. ;-) Takze v tomto neni zadny prakticky problem.

No ale není žádné velké číslo, to je nějakých 40 bitů, to v dnešní době 64-bitových počítačů ani nestojí za řeč, to není ani jeden registr v procesoru...

To největší známé prvočíslo je už dost velké, na jeho uložení by bylo třeba nějakých 77 Mb, ale to je dnes taky celkem prd...každopádně ale, to jsou dost speciální čísla (Mersennova čísla) u kterých to lze rychle vyzkoušet.
Neznamená to ovšem, že bychom znali (nebo dokázali najít) i všechna mezi tím - tam je obrovské neznámé území.

Kdyby nebyl praktický problém s nalezením nějakého dělitele velkého čísla, nebyl by praktický problém i s "lámáním" RSA šifry. Tam se dnes používají čísla o délce 1024 bitů nebo 4096 bitů (což je o dost více než těch 40, co máme tabelovaných).

Na druhou stranu, kvantové počítače (pokud je někdy někdo vyrobí) by faktorizaci měly zvládat v polynomiálním čase - i když jsem zatím úplně nepochopil, jak to dělají.

↑ laszky:
Je tam rozpor pokud se týká asymptotické složitosti, tj. chování "v nekonečnu" - tam už žádnou tabelaci použít nemůžeš a proto nemůžeš říci, že znáš řekněme log(n) prvočísel. Korektní by bylo použít třeba log(m) prvočísel, kde ale m je vzheldem k n konstantní.
Teď jsem si všiml Tvé poznámky o "praktické asymptotice", tak to je potom ok.

Ale zbývá tam jeden problém - pokud předem znám prvočísla, která budu testovat, tak můžu stanovit, že budu třeba procházet jen lichá čísla, nebo jen čísla tvaru 6k+-1 (budu ignorovat násobky 2 a 3), ale pokud ta prvočísla předem neznám, tak si myslím že nebudu schopen apriori zjistit jaká čísla mám procházet a jaká ignorovat.  I když - možná pomocí čínské věty o zbytcích najdu vhodná čísla tvaru Xk+Yi...