abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    dnes 17:33 | IT novinky

    Americký prezident Donald Trump vyzval nového generálního ředitele firmy na výrobu čipů Intel, aby odstoupil. Prezident to zdůvodnil vazbami nového šéfa Lip-Bu Tana na čínské firmy.

    Ladislav Hagara | Komentářů: 1
    dnes 16:55 | Nová verze

    Bylo vydáno Ubuntu 24.04.3 LTS, tj. třetí opravné vydání Ubuntu 24.04 LTS s kódovým názvem Noble Numbat. Přehled novinek a oprav na Discourse.

    Ladislav Hagara | Komentářů: 0
    dnes 16:44 | Nová verze

    Byla vydána verze 1.89.0 programovacího jazyka Rust (Wikipedie). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example.

    Ladislav Hagara | Komentářů: 0
    dnes 12:22 | IT novinky

    Americká technologická společnost Apple uskuteční v USA další investice ve výši sta miliard dolarů (2,1 bilionu korun). Oznámil to ve středu šéf firmy Tim Cook při setkání v Bílém domě s americkým prezidentem Donaldem Trumpem. Trump zároveň oznámil záměr zavést stoprocentní clo na polovodiče z dovozu.

    Ladislav Hagara | Komentářů: 2
    dnes 04:55 | Nová verze

    Zálohovací server Proxmox Backup Server byl vydán v nové stabilní verzi 4.0. Založen je na Debianu 13 Trixie.

    Ladislav Hagara | Komentářů: 0
    včera 16:33 | Nová verze

    Byla vydána nová verze 1.54.0 sady nástrojů pro správu síťových připojení NetworkManager. Novinkám se v příspěvku na blogu NetworkManageru věnuje Jan Václav.

    Ladislav Hagara | Komentářů: 0
    včera 14:11 | IT novinky

    Knižní edice správce české národní domény přináší novou knihu zkušeného programátora Pavla Tišnovského s názvem Programovací jazyk Go. Publikace nabízí srozumitelný a prakticky zaměřený pohled na programování v tomto moderním jazyce. Nejedná se však o klasickou učebnici, ale spíše o průvodce pro vývojáře, kteří s Go začínají, nebo pro ty, kdo hledají odpovědi na konkrétní otázky či inspiraci k dalšímu objevování. Tištěná i digitální verze knihy je již nyní k dispozici u většiny knihkupců.

    Ladislav Hagara | Komentářů: 2
    včera 13:11 | IT novinky

    OpenAI zpřístupnila (en) nové nenáročné otevřené jazykové modely gpt-oss (gpt-oss-120b a gpt-oss-20b). Přístupné jsou pod licencí Apache 2.0.

    Ladislav Hagara | Komentářů: 5
    včera 04:33 | Nová verze

    Byla vydána RC verze openSUSE Leap 16. S novým instalátorem Agama, Xfce nad Waylandem a SELinuxem.

    Ladislav Hagara | Komentářů: 0
    včera 03:44 | Nová verze

    Google Chrome 139 byl prohlášen za stabilní. Nejnovější stabilní verze 139.0.7258.66 přináší řadu novinek z hlediska uživatelů i vývojářů. Podrobný přehled v poznámkách k vydání. Opraveno bylo 12 bezpečnostních chyb. Vylepšeny byly také nástroje pro vývojáře. S verzí 139 přestal být podporován Android 8.0 (Oreo) a Android 9.0 (Pie).

    Ladislav Hagara | Komentářů: 0
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (40%)
     (24%)
     (4%)
     (6%)
     (3%)
     (1%)
     (1%)
     (21%)
    Celkem 268 hlasů
     Komentářů: 23, poslední 4.8. 13:01
    Rozcestník

    Dotaz: Velka cisla v C

    24.3.2012 09:57 Karel Machyna
    Velka cisla v C
    Přečteno: 889×
    Zdravim, prepisuju jeden program z php do pythonu a do C a zasekl jsem se u velkych cisel. V cem je problem - v originalnim PHP kodu je (zjednodusene) toto:
    $a = bcpowmod(2, 249, 997);
    echo $a."\n";
    
    Spravny vysledek 161. V pythonu s tim samym neni zadny problem:
    print 2**249 % 997
    
    Vysledek opet spravne a uz asi chapete kam mirim. Kod v C:
    long long x = ((long long)pow(a, d)) % n;
    printf("x=%lld\n",x);
    
    No a asi neprekvapi, ze dojde k preteceni zobrazi se zaporny vysledek. Moje otazka je, jak toto vyresit. Vim, ze existuji knihovny pro praci s velkymi cisli (libgmp), ale tem bych se hrozne rad vyhnul. Je nejaka moznost jak toho vyresit standardnimi prostredky C/C++?

    Řešení dotazu:


    Odpovědi

    Řešení 1× (Dr. Eddy)
    24.3.2012 10:16 luky
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Pokud Vam jde o tu mocninu, tak muzete pouzit cinskou vetu o zbytcich.
    24.3.2012 13:47 Michal Kubeček | skóre: 72 | Luštěnice
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Tak to by mne docela zajímalo. Můžete to nějak rozvést?
    24.3.2012 16:07 luky
    Rozbalit Rozbalit vše Re: Velka cisla v C
    To, cim se moduluje, si rozdelim na nesoudelna cisla, pro ktera plati ze jejich druha mocnina je mensi nez maximalni hodnota ulozitelna do daneho typu, a pak pro kazde to cislo spocitam mocninu binarnim pulenim. Potom to podel ty cinsky vety prevedu do puvodniho modula.
    24.3.2012 17:26 Michal Kubeček | skóre: 72 | Luštěnice
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Což ale dává smysl jen v případě, že modul je sám příliš velký a jde dobře rozložit na součin nesoudělných čísel. Tady je to prvočíslo, a to dost malé.
    24.3.2012 17:44 luky
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Ono se to vyplati i u mensich modulu kvuli rychlosti.
    24.3.2012 17:47 luky
    Rozbalit Rozbalit vše Re: Velka cisla v C
    A tim mensim modulem nemyslim trojciferny cislo ;-) Znat je to treba v pripade, ze CPU umi jen 16bit(32bit) a vetsi integery se museji emulovat.
    25.3.2012 10:51 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Velka cisla v C
    1, 2, 3 To je zase nějaký domácí úkol? Nechcete to raději řešit v jedné diskusi místo ve třech?
    pavlix avatar 24.3.2012 10:30 pavlix | skóre: 54 | blog: pavlix
    Rozbalit Rozbalit vše Re: Velka cisla v C
    print 2**249 % 997
    Otázka je jestli to počítá tak jak bys chtěl (kvůli rychlosti apod).
    Já už tu vlastně ani nejsem. Abclinuxu umřelo.
    24.3.2012 11:59 lertimir | skóre: 64 | blog: Par_slov
    Rozbalit Rozbalit vše Re: Velka cisla v C
    V 99,99% špatně, tedy pomalu a neoptimálně. Pochybuji, že by algoritmus do normálního vzorce měl aplikovánu čínskou větu o zbytcích a také téměř určitě implementace nevyužívá identity
    a^fi(n) % n = 1
    kde fi(n) je Eulerova funkce přirozeného čísla n. A díky prioritě operací (mocnina je prioritnější než modulo, dělení a násobení) také patrně nevyužívá identity
    (a*b)%n = ((a%n)*(b%n))%n
    která umožňuje počítat modulo pro mnohem menší čísla než nejdříve pronásobit a pak dělit.
    pavlix avatar 24.3.2012 12:43 pavlix | skóre: 54 | blog: pavlix
    Rozbalit Rozbalit vše Re: Velka cisla v C
    V 99,99% špatně, tedy pomalu a neoptimálně. Pochybuji, že by algoritmus do normálního vzorce měl aplikovánu čínskou větu o zbytcích a také téměř určitě implementace nevyužívá identity
    Python prakticky neoptimalizuje. Alespoň v současných verzích. Ale problém je v tom, že i kdybys chtěl takovýto výraz optimalizovat, tak by se musela vymýtit spousta zlozvyků jako používat stejné operátory na různé účely.

    A i tak by programátoři byli kolikrát překvapeni, co jejich program vlastně dělá. Python pracuje nad objekty a z objektů samotných zjišťuje, jak se mají dané operace provést. Na rychlé výpočty je mnohem lepší C, které se případně z Pythonu zavolá. Na druhou stranu na první pokusy a proof of concept implementace je Python ideální už díky podpoře velkých čísel.
    Já už tu vlastně ani nejsem. Abclinuxu umřelo.
    24.3.2012 13:14 tom
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Doplnim, ze v pythonu je pow(a,b,c)=a^b mod c.
    pavlix avatar 24.3.2012 13:28 pavlix | skóre: 54 | blog: pavlix
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Díky.
    Já už tu vlastně ani nejsem. Abclinuxu umřelo.
    24.3.2012 13:55 Michal Kubeček | skóre: 72 | Luštěnice
    Rozbalit Rozbalit vše Re: Velka cisla v C
    a také téměř určitě implementace nevyužívá identity
    a^fi(n) % n = 1
    kde fi(n) je Eulerova funkce přirozeného čísla n.

    Vezmu-li v úvahu, že φ(997) = 996 > 249, tak v tom zase tak zásadní problém nevidím. Nemluvě o tom, že pokud exponent není opravdu výrazně větší než n, bude samotný výpočet φ(n) (časová náročnost obecně odmocnina z n) trvat déle než prostě tu mocninu spočítat v příslušném ℤ/ℤ[n] (časová náročnost logaritmická vzhledem k exponentu).

    24.3.2012 22:00 lertimir | skóre: 64 | blog: Par_slov
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Souhlas, že v tomto případě se identitou nic nezíská, a pokud nic více tazatel nepotřebuje, tak jednoduché použití funkcí nad dlouhými čísly otázku řeší. Psal jsem ale poznámku proto, že hlavní důvod přepisu kódu z pythonu do C je obvykle rychlost. A ve chvíli, kdy je uvedené pouze úvodní test/příklad a mohou se používat mnohem větší čísla, a cíl je primárně rychlost, tak více zisku rychlosti dává promyšlení toho, co počítám a jak, tedy návrh a implementace algoritmů, než prosté použití standardních operací
    25.3.2012 00:23 Michal Kubeček | skóre: 72 | Luštěnice
    Rozbalit Rozbalit vše Re: Velka cisla v C
    Já zase chtěl upozornit, že nelze doporučit optimální algoritmus, když vlastně nevíme, které z operandů jsou "velké".
    24.3.2012 11:19 jano
    Rozbalit Rozbalit vše Re: Velka cisla v C
    algoritmus square and multiply by to mal riesit pomerne rychlo a jednoducho
    pavlix avatar 24.3.2012 13:50 pavlix | skóre: 54 | blog: pavlix
    Rozbalit Rozbalit vše Re: Velka cisla v C
    +1
    Já už tu vlastně ani nejsem. Abclinuxu umřelo.

    Založit nové vláknoNahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.