Matematika

Tak som to dorobil, no prišiel som na neuveriteľnú chybu, algoritmus najskôr pracoval dobre po 10 na 16. nechápal som kde je chyba, no prišiel som na to, že moja vylepšená Fermatova formula pracuje dobre iba zhruba 10 na 16. Čo je neuveriteľne!

No a kto chce môže vyskúšať tento algoritmus, kde je chyba už odstránená. Kód je v pythone a vypočíta obrovské čísla za moment, žiadne minúty, všetko ráta do sekundy a správne.

Tu je kód. Ten kód obsahuje vylepšenú metódu ako redukovať obrovské mocniny vo Fermatovom vzťahu a teda aj stovky a tisíce čísiel nie su žiadny problém. Dôležite pri kopírovani je mat dobre odsadené medzery v kóde.

Citát

zdrojový kód programu:

http://www.poling.sk/0378/find_prime.txt

pred 2 hodinami, robopol napísal:

Tak som to dorobil, no prišiel som na neuveriteľnú chybu, algoritmus najskôr pracoval dobre po 10 na 16. nechápal som kde je chyba, no prišiel som na to, že moja vylepšená Fermatova formula pracuje dobre iba zhruba 10 na 16. Čo je neuveriteľne!

 

Tak teraz som ťa nepochopil. Našiel si chybu v algoritme, alebo tvoja formula pracuje zhruba do 10^16 ? 

Ja som toho povymýšľal viac k prvočíslam a v minulosti som objavil formulu, že  pre a=2 ,aˆ(n-1/2) mod n =1 or n-1, pre prvočísla, čo je iné ako mala Fermatova veta, ktorá je a=2, aˆ(n-1) mod n = 1 or n-1, pre prvočísla. Hľadal som chybu v kóde prečo mi pre čísla >10ˆ16 vyhadzuje nesprávny výsledok. No je to záhada, pretože moje formula pracuje pre čísla zhruba do 10ˆ16. A je to ešte divnejšie pre Mersenove čísla > 10ˆ16, to funguje  takto:

a=2 ,2ˆ(n-1/2) mod n =2 or n-2

v blizkej buducnosti napisem članok k tomuto algoritmu a aj ako to spustit online stranke, kde je python, pokial ho nema niekto nainstalovany. Kod funguje, len som zamenil podmienku pre vyhodnotenie vyplyvajuce z malej Feramatovej vety, kod je dobry prave v tom, že poskytuje metódu ako sa zabvit tých obrovských mocnín a to 100% funguje.

Ako príklad, náhodne som si vybral Mersenove číslo, výpočet trval 1 sekundu pričom ešte aj hľadal deliteľov. Tento algoritmus pracuje v polynomialnom čase.

pred 54 minútami, robopol napísal:

 Hľadal som chybu v kóde prečo mi pre čísla >10ˆ16 vyhadzuje nesprávny výsledok. No je to záhada, pretože moje formula pracuje pre čísla zhruba do 10ˆ16...

 

Skôr typujem, že je to chyba v numerickom výpočte. Skús test, napríklad súčin čísiel 12345678987654321 * 12345678987654321 = 152415789666209420210333789971041. Odmocnina 152415789666209420210333789971041 by mala byť  12345678987654321. Predpokladám, že tento výsledok v pythone nedostaneš. To ale neznamená, že tvoj algoritmus je nesprávny.

Keby si vedel ako som musel pracne zistit kde je chyba, prechádzal som celý kód, nechápal som ako je možné, že pre >10 na 16 to vyhadzuje divne výsledky a pre <10 na 16 správne. Ja som bol 100% presvedčený, že formula a=2, aˆ(n-1)/2 mod n = 1 or n-1, pre prvočísla funguje. Pre mna je to záhada, prečo nefunguje. však si skus do wolframu dat napríklad:

n=9689

https://www.wolframalpha.com/input/?i=2ˆ((9689-1)%2F2)+mod+9689

skus si akekolvek do zhruba 10 na 16. Potom skus väčšie a zistis ze uz vyhadzuje zle.

pred 11 minútami, robopol napísal:

 Pre mna je to záhada, prečo nefunguje.

Nie je to záhada, je to dané aritmetikou, ktorá je obmedzená počtom bitov. Veď si skús naprogramovať ten môj príklad. Nemám nainštalovaný python, ale s veľkou pravdepodobnosťou, nedostaneš správy výsledok. Ak napríklad v algoritme porovnáš takéto výsledky, tak to dá nesprávnu odpoveď. Predpokladám, že ak tvoj algoritmus pre menšie čísla funguje, funguje aj pre väčšie. 

ty to nechapeš. Program mi vyhodil doby vysledok, problem je, že moja folrmula nefunguje a ja neviem prečo. fermatova podmienka funguje, čo je dva krat vačšie číslo v podmienke, ako u mojej formuly. Však program funguje ultra rychlo pre tisice cislic aj viac, superpočitač vypočita eššte vačšie mersenove prvočíslo ako je zname do 1 sekundy.

pred 4 minútami, robopol napísal:

ty to nechapeš. 

No dobre, zrejme to nechápem... Ale skús naprogramovať ten môj príklad, aký dostaneš výsledok. Ak správny, potom je to "záhada".

tono ked aritmetika funguje pre dva krat vacšie číslo a vždy spravne tak jedina vec co nefunguje je moja formula pre n>10 na 16. To nie je take tazke pochopit. Ty si nevšimas, že ja som zmenil podmienku v programe za Feramtovu a zrazu všetko beži ako ma. chapeš to?

Práve teraz, robopol napísal:

Ty si nevšimas, že ja som zmenil podmienku v programe za Feramtovu a zrazu všetko beži ako ma. chapeš to?

Dobre, súhlasím, ale vypočítaj mi v pythone odmocninu z 152415789666209420210333789971041. Snáď to nie je až toľko programovania.

ale ja sa nehadam, že to neurobi dobre. tvoj príklad. Ja ale žiadne takéto funkcie nepouživam, moj algoritmus beži na uplne základnej aritmetike celých čísiel a modulo, čo je zvyšok po deleni, celočíselny.

Každá numerická matematická operácia, aj modulo, je v konečnom prípade iba aritmetickou operáciou súčtu (rozdieľ, podieľ, je fakticky tiež len súčet). A počet bytov vždy rozhoduje o relevantnosti výsledku.

odmocninu nie je základná aritmetika, funckia sqrt() je nejak implementovana a to zalaži od algoritmu ako to ráta a ja vôbec netvrdím, že python to robí lepšie ako to je v inych programovacích jazykoch.

tvoj príklad mi vyhodil zaokruhlenie výsledku a teda mocnina toho čísla sa už nezhodovala s výpisom úplne.

Podľa môjho odhadu tvoj algoritmus funguje správne. Nemá to totiž logiku, aby bol obmedzený rozsahom. Chyba je pravdepodobne v aritmetike, obmedzenej počtom platných bitov. 

on teraz funguje dobre, kedze som prisiel nastastie na to v com bola chyba. chyba mi vyhadzuje pri podmienke  (vid. vyssie), spravne výsledky dáva pri fermatovej podmienke. To je detail. ide o implementaciu napadu ako efektivne v polynomialnom case vediet vyratat obrovsku mocninu modulo číslo. A ten algoritmus je na toto vytvoreny. teda ty možeš narvat lubovolne množstvo čísli a je len obmedzenie ako si písal pamat počítača, rýchlosť procesora atd. Ja myslím, že to je obdivuhodny výsledok takto jednoducho postaveného algoritmu, on sa dá kombinavat napr. v Rabin-miler teste, ktorý sa snaží eliminovať pseudoprvočísla.

tak sa s tym troška hram a skusal som troska väčšie prvočísla:

Mersenove prvočíslo v tabulke:

https://sk.wikipedia.org/wiki/Mersennovo_prvočíslo

na 25 pozicii, 6533 cifier, algoritmus vyhodnocoval zhruba 1 minutu

No a tu je článok a návod na program. Komu sa článok páči nech zdieľa ďalej.

https://robopol.sk/blog/algoritmus-na-extremne-prvocisla-v-pythone

Blahoželám! Ja som použil bežný algoritmus. Na mojom laptope TOSHIBA 4 GB RAM, trvala verifikácia tohoto čísla 2 minúty a 20 sekúnd. 

čo je bežny algoritmus? neviem čo si prvereroval čim :)

ak myslis to 25 mersenove prvocislo, tak presne to trvalo 43 sec.

Testoval som číslo 2^21701-1 Použil som CAD, neviem aký algoritmus sa tam využíva. Overoval som si to aj online https://numberworld.info/primeCheck 

No tam to ide okamžite, to znamená, že Mersennove prvočísla ma ten program v sebe, ak mu zadáš iné takéto veľke prvočíslo (nie Mersenovo) bude busy.

inak pre zaujímavosť tóno, to najväčšie Mersenove prvočíslo mi vychádza, že by rátal moj pc zhruba cca 46-64 hodín. Inak k tvojmu príkladu s odmocninou je problém u pythonu, nie len u neho, že premenné float má ohraničené na 16 cifier, nejde teda o chybu.

V matematickom CADE som našiel funkciu, ktorá definuje pravdepodobnosť, či sa jedná o prvočíslo. Funguje celkom spoľahlivo a hlavne dáva takmer okamžite výsledok, aj pri obrovských číslach. Ako som sa dočítal, je založená na https://en.wikipedia.org/wiki/Lucas_primality_test 

pred 21 hodinami, robopol napísal:

No tam to ide okamžite, to znamená, že Mersennove prvočísla ma ten program v sebe, ak mu zadáš iné takéto veľke prvočíslo (nie Mersenovo) bude busy.

Skúšal som nejaké cifry čísla 2^21701-1 zmeniť a nebol busy,  výsledok bol false. To samozrejme ešte neznamená, že prvočísla nemá uložené v databáze.   

to je tým tono, že našiel prveho maleho deliteľa, aj moj algoritmus to ma, obrovske čislo može byt delitelne 3,7,11 atd a je to časty jav.