Jump to content

Recommended Posts

Posted

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

 

 

 

Posted
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 ? 

Posted

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.

 

Posted

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.

 

priklad.jpg

Posted
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.

Posted

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.

Posted
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. 

Posted

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.

Posted
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".

Posted

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?

Posted
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.

Posted

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.

Posted

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.

Posted

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.

priklad.jpg

Posted

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. 

Posted

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.

Posted

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. 

Posted

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

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

Posted

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.

Posted

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.

Posted

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.   

Posted

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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue. Additional information you can see at Privacy Policy