Skočiť na obsah

Matematika


robopol

Odporúčané príspevky

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

 

 

 

Odkaz na príspevok
Zdieľať na iných stránkach

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 ? 

Odkaz na príspevok
Zdieľať na iných stránkach

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.

 

Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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. 

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

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?

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

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. 

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.   

Odkaz na príspevok
Zdieľať na iných stránkach

Vytvorte si účet alebo sa prihláste, aby ste mohli písať príspevky

Ak chcete odoslať príspevok, musíte byť členom

Vytvoriť konto

Zaregistrujte si nový účet v našej komunite. Je to ľahké!

Zaregistrovať si nové konto

Prihlásiť sa

Máte už konto? Prihláste sa tu.

Prihlásiť sa teraz
×
×
  • Vytvoriť nové...

Dôležitá informácia

Táto stránka používa súbory cookies, pre zlepšenie používania stránok tohto webu. Pre viac informácií kliknite sem. Ďalšie informácie nájdete na stránke Zásady ochrany osobných údajov