Srovnání algoritmů na prvočísla

Srovnání algoritmů na prvočísla
« kdy: 04. 12. 2022, 23:01:27 »
Který z algoritmů bude asymptoticky lepší v čase? Hlavní cyklus klasicky počítá od dvojky a inkrementuje i. (Případně od trojky a inkrementuje po 2, to je fuk)
-ten, který daného kandidáta zkouší dělit všemi čísly až po číslo samotné i (to je pro ukázku zde jenom)
ten, který daného kandidáta zkouší dělit všemi čísly až po FLOOR(SQRT(i))
-ten, který daného kandidáta zkouší dělit jen prvočísly až po číslo samotné i, přičemž si prvočísla ukládá to pomocné tabulky
-Erasthenovo síto

Druhá větev-
je lepší (opět rychlejší) v druhém vnoření cyklu při porovnání odmocniny si odmocninu nejdřív spočítat (sqrt(i)) a nebo testovat  j<=i*i
-samozřejmě taky vím, že taky dost výkonu ubere, když odmocnina není převedená z float na int
« Poslední změna: 05. 12. 2022, 07:48:38 od Petr Krčmář »


xPoli

Re:algoritmus na prvočísla - srovnání
« Odpověď #1 kdy: 05. 12. 2022, 07:22:03 »
Záleží na implementaci a architektuře. Záleží na tom, jestli se bude provádět dělení nebo násobení a porovnání - jestli je celočíselné násobení a porovnání na 1 + 1 takt a dělení na desítky až stovky taktů, pak zdánlivě hloupý algoritmus s násobením a porovnáním může být řádově efektivnější. Záleží na datových typech. Záleží na tom, co se myslí pod pojmem asymptoticky - matematický význam a význam v reálném světě VT je jiný. Záleží na (ne)dostupnosti paměti. Pak se to dá i spočítat nebo ozkoušet a změřit, ty algoritmy nejsou tak složité, aby se nedaly napsat.




oss

  • ***
  • 166
    • Zobrazit profil
    • E-mail
Re:Srovnání algoritmů na prvočísla
« Odpověď #2 kdy: 05. 12. 2022, 08:52:21 »
To je snad jasne s popisu a so stresokolskej matematiky (no skor zakladnoskolskej). Nie?

Re:Srovnání algoritmů na prvočísla
« Odpověď #3 kdy: 06. 12. 2022, 10:02:35 »
Cielom otazky/skolskeho prikladu je uvedomit si casovu zlozitost delenia (algoritmus, ktory ho pouziva co najmenej je najrychlejsi) a sqrt.

Prvy bod: najprv delis vsetkym co vidis, potom delis mensim poctom cisel, a algoritmus Eratosthenovho sita nedeli vobec.

Druhy bod: nasobenie je rychlejsie ako sqrt

CPU

  • ****
  • 361
    • Zobrazit profil
    • E-mail
Re:Srovnání algoritmů na prvočísla
« Odpověď #4 kdy: 06. 12. 2022, 15:47:08 »
To je nějaký školní projekt nebo tam je možný nějaký profit?


Doplnění:
Pokud jde o známá prvočísla, pak existuje rovnice, která s konstantní (relativně malou) náročností zjistí, jestli je číslo prvočíslo s pravděpodobností 100%!!! Rovnice není naprosto přesná, ale to nevadí, protože jsou známá všechna (3 ?) prvočísla, která vychází špatně.

Kdyby za tím byl nějaký reálný profit, něco bych měl.


Re:Srovnání algoritmů na prvočísla
« Odpověď #5 kdy: 06. 12. 2022, 16:05:26 »
Erasthenovo sito pouziva nejmene narocne operace. Deleni a odmocniny jsou slozitejsi nez nasobeni a pokud si dobre pamatuji, lze ho v situ nahradit opakovanym scitanim.

Re:Srovnání algoritmů na prvočísla
« Odpověď #6 kdy: 06. 12. 2022, 20:27:38 »
Erasthenovo sito pouziva nejmene narocne operace. Deleni a odmocniny jsou slozitejsi nez nasobeni a pokud si dobre pamatuji, lze ho v situ nahradit opakovanym scitanim.

Žádnou odmocninu nepotřebuješ počítat ani v tom algoritmu "s odmocninou".

Re:Srovnání algoritmů na prvočísla
« Odpověď #7 kdy: 06. 12. 2022, 23:45:15 »
Podstata je že  nezáleží na tom jestli dělení je rychlejší než modulo. Ale kolik operací dělá který algoritmus pro velké vstupní n. Přesněji operací v nejhlubším cyklu. Nebo se pletu?

(Ano, je tam nejednoznačnost , prvních n prvočísel(list), nté prvočíslo, prvočísla pod n(list),  prvočíslobtěsně nad n)

A jde o časouvou a ne pamět. Nárocnost

Re:Srovnání algoritmů na prvočísla
« Odpověď #8 kdy: 07. 12. 2022, 01:21:06 »
A jde o časouvou a ne pamět. Nárocnost
Můžu se zeptat, co je opravdu cílem cvičení? Obvykle v reálu jde o tradeoff mezi výpočtem a pamětí. Přesněji - co to je "velké vstupní n"? Protože mám pocit, že v tom máte zmatek a že ve skutečnosti se bavíte o nízkých desítkách bitů maximálně. (a pak nemá smysl mluvit o asymptotách). Pokud jde o velká čísla (u bezpečných šifer se bavíme řádově o kilobitech, pokud prvočíslo použijete na vytvoření eliptické křivky, tak ve stovkách bitů), pak vřele doporučuji pročíst zde https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests a optimálně ještě od Bruce Schneiera knížku Applied Cryptography.

Navíc ale ono taky záleží jaká operace, třeba násobení n-bitových čísel znamená n * (rotace + sčítání), takže tam pak máme nějaké ln(x) ke složitosti navíc.

Ktomu doplňme, že i na paměti záleží. Hustota prvočísel je x/ln(x). To znamená, že pro tabulku 64-bitových prvočísel (potřebných k faktorizaci 128bit čísel) potřebujete cca 3ExaByte, což není málo ;-)

Citace: CPU
Pokud jde o známá prvočísla, pak existuje rovnice, která s konstantní (relativně malou)
nemáte prosím odkaz? Připadá mi to příliš dobré, aby to byla (obecně) pravda (aneb, proč se třeba při genrsa používají probability testy a ne ta rovnice), tak by mě zajímalo, o co jde a jaká to má ty "ale".

smoofy

  • *****
  • 1 053
    • Zobrazit profil
    • E-mail
Re:Srovnání algoritmů na prvočísla
« Odpověď #9 kdy: 07. 12. 2022, 07:11:44 »
Tak existuje treba Euleruv vzorec na vypocet prvocisel ale ten generuje jen 39 prvocisel a jeste bych rekl ze ne v rade.

oss

  • ***
  • 166
    • Zobrazit profil
    • E-mail
Re:Srovnání algoritmů na prvočísla
« Odpověď #10 kdy: 07. 12. 2022, 08:06:28 »
Boze vy to tu v komentaroch neskutocne komplikujete a riesite veci, na ktore sa tazatel ani nepytal. pricom jeho otazka je uplne jasna.

xPoli

Re:Srovnání algoritmů na prvočísla
« Odpověď #11 kdy: 07. 12. 2022, 09:48:36 »
pricom jeho otazka je uplne jasna.

Právěže není. Wasper na to upozorňuje taky. Nejsme na webu o matematice, ale na webu o počítačích. Tazatel neumí/nechce konkretizovat zadání. Nevíme, co je cílem, nevíme, jaké jsou omezující podmínky, nevíme, co je k dispozici.

Podstata je že  nezáleží na tom jestli dělení je rychlejší než modulo. Ale kolik operací dělá který algoritmus pro velké vstupní n. Přesněji operací v nejhlubším cyklu. Nebo se pletu?

Podstata je, kolik taktů je potřeba na výpočet. Resp. kolik taktů navíc oproti N je potřeba pro výpočet N+1. A zde záleží na tom, jaké aritmetické operace se budou používat, s jakými datovými typy, na jaké architektuře. "...operací v nejhlubším cyklu" - to chápu jako úvahu o vnořených cyklech (for, while), ale tak to nemusí nutně být.

_Jenda

  • *****
  • 1 264
    • Zobrazit profil
    • https://jenda.hrach.eu/
    • E-mail
Re:Srovnání algoritmů na prvočísla
« Odpověď #12 kdy: 07. 12. 2022, 10:49:09 »
pricom jeho otazka je uplne jasna.

Právěže není. Wasper na to upozorňuje taky. Nejsme na webu o matematice, ale na webu o počítačích. Tazatel neumí/nechce konkretizovat zadání. Nevíme, co je cílem, nevíme, jaké jsou omezující podmínky, nevíme, co je k dispozici.

Podstata je, kolik taktů je potřeba na výpočet. Resp. kolik taktů navíc oproti N je potřeba pro výpočet N+1. A zde záleží na tom, jaké aritmetické operace se budou používat, s jakými datovými typy, na jaké architektuře. "...operací v nejhlubším cyklu" - to chápu jako úvahu o vnořených cyklech (for, while), ale tak to nemusí nutně být.
Tazatel se ptal na asymptotickou složitost, ta je alespoň v mé sociální bublině (kolem matfyzu) definována dost jasně, základní operace s čísly (sčítání, násobení, dělení; odmocnina už je trochu sporná, ale tazateli ji stačí vypočítat jednou na začátku) jsou konstantní pokud není uvedeno/nelze předpokládat že je to jinak a nějaké počty taktů se neřeší, protože to jen násobí konstantou a v běžně používané "big-O notation" se konstanty zanedbávají.

Tady je ale problém v tom, že tazatel si musí vyjasnit, vzhledem k čemu složitost chápe. Složitost se většinou uvádí vzhledem k bitové velikosti vstupu: zatímco i roste lineárně, jeho bitová velikost roste logaritmicky. Takže člověk by tady naivně řekl že to má lineární složitost (uděláme lineárně kroků vzhledem k i - testujeme nějaká čísla od 0 do i), ale uvádí se, že to má 2^n, protože pro představu třeba pro i=1024 uděláme 1024 kroků, ale „velikost vstupu“ je jenom 10 (bitů), pro velikost vstupu 20 už uděláme milion kroků atd.

Odpovědi na jeho dotazy vzhledem k i by tedy byly: O(i), O(sqrt(i)), O(něco něco https://en.wikipedia.org/wiki/Prime-counting_function, takže asi log(i), ale záleží jak si prvočísla generuje a jak je má uložena), a z hlediska asymptotického je jedno jestli si předpočítá odmocninu nebo počítá i*i (v praxi je samozřejmě nejlepší předpočítat).

Problém tazatelova popisu také je, že je takový celkově zmatený, a motivace (o co mu jde) by taky pomohla.

Pokud by ho tedy zajímala „standardní složitost vzhledem k n“, tak „stačí exponenciálovat výše uvedené“ *, ale problém je, že už možná má na mysli operace s čísly, která nejsou konstantně velká, a tak se nedá použít ten předpoklad, že operace s nimi trvají konstantně dlouho. (v praxi ale ten limit bývá délka čísla v počítači, tedy 64 bitů, a tam se s takhle naivním algoritmem nedostane; pro chytřejší testování prvočíselnosti už to ale problém být začne).

*Pozor, že u manipulace s exponenciálními funkcemi se věci v exponentu chovají jinak než by člověk intuitivně čekal, například O(2^(2n)) není O(2^n) i když O(n) je O(2n), kdysi jsem přesně tohle grandiózně zfailil ve škole.

https://softwareengineering.stackexchange.com/questions/312563/time-complexity-of-2sqrtn
https://stackoverflow.com/questions/4856107/is-22n-o2n