Python a najväčšie pravdepodobné prvočíslo

20.9.2009 13:37 | Přečteno: 1611× | poslední úprava: 20.9.2009 13:28

Pokračujem v nezaujímavých blogpostoch - dnes o Pythone a pravdepodobných prvočíslach.

Dnes som narazil na skupinu čísel nazvanú "pravdepodobné prvočísla". Vedel som, že podobné čísla existujú, no nikdy som sa k nejakému takému nedostal - nikdy som náhodne na nejaké nenatrafil a na druhej strane ma to nezaujímalo natoľko, že by som si nejaké vyhľadal. Avšak dnes ma jeden komentár zo Slashdotu doviedol k takýmto číslam, konkrétne ich rebríčku.

Samozrejme som sa hneď pozrel na miesto číslo jeden v rebríčku. Bolo tam jednoduché "2^4583176+2131". Na prvý pohľad sa mi to nezdalo ako obrovské číslo. Ani na druhý pohľad, keď som si pozrel počet cifier, sa mi to nezdalo ako veľké číslo. Dotretice som si vypočítal koľko by zabralo v pamäti miesto a keď mi vyšlo, že približne približne pol megabajtu, tak mi začalo dochádzať, že je to dosť veľké číslo.

Chcel som vedieť ako vyzerá. Ako prvá možnosť ma napadla Python - vedel som, že s veľkými číslami si vie poradiť, tak som ho teda vyskúšal. Zadal som mu výraz, začal chrúmať a vyťažovať jedno jadro procesoru (GIL sucks!) na maximum. Čakal som minútu, že čo na to povie, no on si len ticho chrúmal ďalej. Bol som hladný, šiel som chrúmať (obed) aj ja...

Medzitým mi absolútne vypadlo z hlavy, že som mu niečo také dal počítať. Prepol som sa na plochu s konzolou a zprvu ma prekvapila obrovská kopa čísel - vtedy mi doplo. On to vážne vypočítal! (samotné číslo ako príloha v prvom komentári)

A teraz už len zistiť, či to je prvočíslo... ;)

       

Komentáře

[Milan Lajtoš]

 

Sľubované najväčšie pravdepodobné prvočíslo. gprp.txt (1,3 MiB). Sem som to nemohol dať, súbor je príliš veľký. :(

[David Watzke]

A teraz už len zistiť, či to je prvočíslo... ;)

To by chtělo uplácat nějakej CUDA prográmek

[Limoto]

Co jsem kdysi zkoušel, tak calc počítal rychleji než python

[David Watzke]

Btw, pomocí

time bc <<< '2^4583176+2131'

to bylo za

real    1m8.915s
user    1m7.834s
sys     0m0.112s

na Athlonu64 X2 @ 2.75 GHz

[David Watzke]

Python 3.1.1 si řekl, že tolik spěchat nebude...

time python3 -c 'print(2**4583176+2131)'
[...]

real    5m34.495s
user    5m32.413s
sys     0m0.100s

Měření Pythonu 2.6.2 mě po 13 minutách přestalo bavit.

[Milan Lajtoš]

Python 2.6.2, Core2Duo T7300 na 800MHz

real    99m24.838s
user    80m0.060s
sys     0m18.959s

Ale počítač som používal bežne ďalej, takže som to určite predĺžil. To isté s calc:

real    1m11.521s
user    1m4.612s
sys     0m0.207s

[Limoto]

time calc 2^4583176+2131

real    0m43.866s
user    0m43.757s
sys     0m0.037s
 

Phenom II@3,65GHz

[Limoto]

Zato na 64b už je to mnohem zajímavější:

real    0m15.770s
user    0m15.496s
sys     0m0.013s

[David Watzke]

Hustý. U mě to calc dal za 27 sekund. Takže s přehledem vyhrává a je víc než 12x rychlejší než (novej) Python

[Limoto]

Ještě by to chtělo zkusit icc + patch. Ale ten mám jenom 32...

[Limoto]

icc -xW -ipo


real    0m21.506s
user    0m21.195s
sys     0m0.030s
 

Calc na 32b. patch-AuthenticAMD už to nezlepšilo...

[Limoto]

clang -O2


real    0m24.825s
user    0m24.502s
sys     0m0.000s
 

GCC je šmejd...

[Jan Grmela]

U mě byl calc ještě rychlejší:

gum@thinkpad ~ $ time calc 2^4583176+2131
bash: calc: command not found

real    0m3.115s
user    0m0.368s
sys     0m0.092s

Bc to trvalo docela dlouho (Athlon 5050e@2.6 GHz, 64-bit):

gum@thinkpad ~ $ time calc 2^4583176+2131
...

real    1m15.164s
user    1m14.117s
sys     0m0.092s

[Jan Grmela]

Samo má v druhém příkladu být příkaz bc ..., ne calc

[9002]

Mas pokazeny copy-paste na linuxe?

[Jan Grmela]

No o kvalitě copy-past na Linuxu bych s úspěchem pochyboval, dost často na něj nadávám. Zvláště otravná je občasná chyba když něco označím myší, je to ve schránce, ale po zavření dokumentu, odkud jsem to bral, se to ze schránky vytratí.

[9002]

no to je IMHO logicke, nie?

[David Watzke]

Cože? Co je na tom logickýho?

[9002]

Program uz nepouzivas => nepotrebujes jeho vystupy => niesu nutne ani jeho udaje vo schranke... Co je na tom nelogicke?

[Jan Grmela]

Takže když si označím text v prohlížeči a jeho okno zavřu, tak by logicky ten text měl ze schránky zmizet? Řekl bych, že dost uživatelů si otevře soubor, zkopíruje z něj něco do schránky, soubor zavře a pak zkopírovaný text někam vloží. Rozhodně rychlejší než soubor otevřít, přepnout se do jiné aplikace, vložit text, soubor zavřít a přepnout se zpět do aplikace.

[Honza Balák]

+1, taky bych to tak předpokládal, ale realita je jiná...

[mrzout]

používejte nějakého správce schránky (klipper, parcellite)

[Jan Grmela]

Takže jsem se po pěti letech používání Linuxu na desktopu dozvěděl, že jsem špatně pochopil koncept schránky. Tak dobrý, no Asi deformace z Windows...

[Filip Jirsák]

Schránka ve Windows funguje úplně stejně.

Představte si, že byste si takhle vložil do schránky třeba nějaký větší obrázek. Pokud by musel být ve schránce nezávisle na programu, musel by program do schránky nakopírovat v nejrůznějších formátech, které zná – pravděpodobně byste velice rychle zjistil, jak málo RAM máte, a že vám nestačí ani swap. Zatímco takhle program jenom do schránky vloží odkaz, že má pro schránku k dispozici data v těchto a těchto formátech, a samotný obrázek nikam nekopíruje. Teprve když si nějaký jiný program o obsah schránky řekne, řekne si rovnou i o formát a teprve pak ten obrázek původní program v jednom zvoleném formátu předá.

[Limoto]

Ale proč to dělá v případě textu?

[Filip Jirsák]

Protože API je pro oba případy stejné.

[koroptev]

ale proc to dela v pripade textu NA LINUXU !

[koroptev]

to ale popisujete nejakou svou predstavu o tom, jak to funguje na Win, ze, protoze presne takhle se to nechova, zkuste otevrit oci a zjisti, jak to doopravdy je a nesirit tady blbosti ...

[Filip Jirsák]

Clipboard Operations

When placing a clipboard format on the clipboard, a window can delay rendering the data in that format until the data is needed. To do so, an application can specify NULL for the hData parameter of the SetClipboardData function. This is useful if the application supports several clipboard formats, some or all of which are time-consuming to render. By passing a NULL handle, a window renders complex clipboard formats only when and if they are needed.

[koroptev]

... window CAN delay .....

zjevne to aplikace, ktere pouzivam, nedelaji, asi to bude u jednodussich datovych struktur (text, obrazky) standard; na linuxu je standard presne opacny

recitujete teorii a ja vam rikam - vemte ruku oko a zkuste to, bezne veci

 

[koroptev]

ale k veci - neni pravda, ze to na windows funguje uplne stejne (tzv. "logicky") jako na linuxu ..

[Filip Jirsák]

Okamžité kopírování je pouze zvláštní případ odloženého kopírování, kdy interval odložení je nula. Opačně to převést nelze.

[koroptev]

neznam a nepouzivam to api, pokud vy ano, pak je nekde rozpor, scite, outlook, malovani, paint.net atd. atd. funguji zpusobem, ktery jsem popsal

muj tip je, ze ani vy o tom nic nevite - co to je "interval odlozeni" ? o nicem takovem se tam nemluvi (reknete si to nahlas, at slysite jak absurdne to zni, jako ze se to odlozi o 5s? :-} vas prispevek napovida, ze jste to takhle vtipne (ne)pochopil), hovori se tam o tom, ze to aplikace bud prdne primo do schranky (to je to ihned), anebo nastavi nejaky parametr funkce na null (ne nulu a neni to interval) a v tom pripade se zavazuje, ze to vyrenderuje az kdyz si o to nekdo dalsi rekne (to je to, co je na linuxu patrne standard); boze ...

[koroptev]

ten parametr (ktery se v pripade delayed renderingu nastavuje na NULL) se predava teto http://msdn.microsoft.com/en-us/library/ms649051%28VS.85%29.aspx funkci, prectete si to (nebo nechte nekoho, kdo umi anglicky a nedela mu problem porozumet jednoduchemu textu, aby vam to prelouskal), pokud neni NULL je to handle na ty data (co pujdou do schranky)

[Filip Jirsák]

API umožňuje oba dva případy – jak okamžité vložení dat, tak vložení pouze oznámení, a data poskytnout teprve na žádost. Dokonce umožňuje i kombinaci – třeba obrázek ve vektorovém formátu vloží do schránky ihned, ale jeho variantu vyrendrovanou do bitmapy poskytne jenom na požádání. Přičemž okamžité předání dat je pouze speciálním případem odloženého předání – mohlo by klidně fungovat tak, že API pro správu schránky ihned zavolá příslušnou funkci, která data vrací na požádání, a data si uschová v keši. Z hlediska programu, který data ze schránky použije, by v tom nebyl rozdíl. Jinými slovy, jako uživatel musíte vždy předpokládat, že po ukončení aplikace nebudou data z ní vložená do schránky k dispozici, pokud nemáte u konkrétní aplikace zkušenost, že se chová jinak. Zkuste si na Windows okopírovat do schránky velký obrázek z Gimpu nebo PhotoShopu, nebo celou tabulku z Excelu. Pak nám můžete vyprávět o tom, na co se vás ty programy zeptaly, a jak to dopadlo, když jste odpověděl, že data nechcete ve schránce ponechávat.

Intervalem odložení jsem myslel čas, protože to je to podstatné – buď se to do schránky vloží hned, nebo až později. Nastavením NULL se aplikace nezavazuje, že data vyrendruje, pokud si o ně někdo řekne, ale pouze dává možnost i o data říci později. Pokud uživatel mezi tím aplikaci ukončí, nebo data ztratí smysl, nevyrendruje se nic.

Tipovat, co o tom vím a co nevím, raději nezkoušejte – pokoušel jsem se to nejprve vysvětlit bez odkazů na API a dokumentaci, protože jsem předpokládal, že jsou lidé jako vy, kteří dokumentaci Windows API v životě neviděli. Ze zkušeností s používáním toho API vás můžu ubezpečit, že funguje tak, jak je to v dokumentaci popsáno a jak jsem to zde popisoval.

[koroptev]

no ted uz me (ani za pomoci "muzu vas ubezpecit") nepresvedcite, ze vite, o cem mluvite - po tech vsech zbleptech a komediich s intervalem se to posunulo od "ve win stejne jako v linuxu" k "ve win to lze i jinak"

takze kdyz to program necha ve schrance i po svem ukonceni nebo rekne, ze to bude poskytovat delayed, tak je to z hlediska ostatnich aplikaci, ktere data chteji stejne? i po ukonceni toho programu? vidite ten rozpor?

ted se jen zamyslete, proc se excel pta "ve schrance je mnoho dat, muzu je zahodit" a proc se ostatni (zadna co znam) neptaji "zahazuji, chcete ponechat"?

protoze ponechavaji automaticky a ja to jako uzivatel mohu v naproste vetsine (zatim jsem nenarazil na opak) predpokladat! (a ano, excel se pta, gimp dejte jako priklad, nebo ten photoshop, ptaji se? nevim, nepouzivam, dejte svou zkusenost, v pripade, ze se ptaji, je to argument pro vas nebo pro me?)

 

[Filip Jirsák]

Tak ještě jednou, pomalu a naposledy: aplikace v Linuxu i ve Windows oznámí, že má data pro schránku a v jakých formátech je schopna je poskytnout. To znamená, že po ukončení aplikace nebudou data k dispozici. Volitelně pak může existovat keš, která si tato data přečte a poskytuje je dál, takže jsou pak k dispozici i po ukončení aplikace – pokud se neukončí ona keš nebo data nesmaže. Ve Windows je tato keš rovnou součástí systému a aplikace vkládající data do schránky si její použití může vynutit; v linuxu si nejsem jist, zda pro ovládání takové keše je nějaké běžně používané API (odhlédněme teď od toho, že v Linuxu těch schránek existuje víc). Pro aplikaci v tom není žádný rozdíl, vždy je odkázána na to, že jí data ze schránky někdo poskytne – ať už původní aplikace, nebo keš.

To znamená, že by uživatel měl vždy ve vlastním zájmu předpokládat, že aplikace pouze oznámila dostupnost dat ve schránce, ale že data nejsou nakopírována v keši – pokud si u konkrétní aplikace není jist tím, že si aplikace vynucuje nahrání dat do keše už při vložení. Nic vám samozřejmě nebrání předpokládat takové chování u všech aplikací, klidně navzdory tomu, že jste se v této diskusi dozvěděl minimálně od dvou lidí, že je takový předpoklad neoprávněný. Až si pak jednou zkopírujete do schránky nějaká důležitá data, a pak je ve schránce nenajdete, můžete si stěžovat maximálně na lampárně hlavního nádraží.

[Jan Grmela]

Díky za vysvětlení, nikdy mě nenapadlo to brát jako feature, vždycky jsem si myslel, že neponechání dat ve schránce po ukončení aplikace je nějaký podivná chyba mého KDE. Takže Alt + F2 > klipper a mohu konečně být spokojen

[Ondrej 'SanTiago' Zajicek]

> Co je na tom logickýho?

Logicke je na tom to, ze ve schrance neni nejaka hromada dat oddelena od programu, ale v podstate jen odkaz na program, ktery ta data drzi. Pri pastnuti pak dojde k handshake mezi zdrojovym a cilovym programem, aby se domluvili na formatu predavanych dat. Proto je mozne pastovat nejenom text, ale i slozita data (pokud jim obe strany rozumi). Pokud jedna strana skoncila, tak se nemuze ucastnit handshake a tedy nemuze slouzit jako zdroj dat.

[koroptev]

co je na tom logickeho pro uzivatele

[Limoto]

Co to máš za bash, že mu vypsání "command not found" trvá 3 sekundy?

[Jan Grmela]

Tipuju, že za to může command-not-found z mého SUSE.

[David Watzke]

3 sekundy, než ti to hodilo command not found?

[Martin]

Nicméně to není moc překvapivý výsledek. Jediným smyslem života calc jsou matematické výpočty a je pro tyto účely brutálně optimalizovaný, což se o Pythonu dá říct jen stěží.

[Honza Balák]

Zkoušel jsem to v Haskellu a po 13 minutách to skončilo chybou...

[Martin]

Jakou chybou? Jaký datový typ jsi použil? Jak vypadal algoritmus? U výpočetně náročných úloh je potřeba dát pozor na práci s pamětí. V takových případech totiž začínají hrát velmi důležitou roli slova jako "laziness" nebo "thunk". Hoď sem svůj program.

[Honza Balák]

No chyba bude v tom, že jsem žádný program neřešil, prostě jsem tam plácnul ten výraz a bylo to. Na menší hausnumera to stačí . Je pravda, že Haskell jsem viděl naposledy před 6 lety, takže tak...
Nicméně pokud máš nástřel toho programu v Haskellu, byl bych rád...

[Limoto]

Jak to v tom pythonu počítals? Pokud tam dals "2^4583176+2131", tak ti vyšla blbost

[Limoto]

Hmm, ale to netrvá tak dlouho, takže asi ne

[mirec]

time qalc "2^4583176+2131"

real    0m7.248s
user    0m7.156s
sys     0m0.037s

[Ondrej 'SanTiago' Zajicek]

A co na tom chcete pocitat? Vzdyt to jde spocitat skoro z hlavy, ze to cislo bude vypadat takhle:

0x45EF08000....000853

 

[Ondrej 'SanTiago' Zajicek]

To je samozrejme nesmysl, bude to vypadat takhle: 0x2000....000853 .