Dotaz: Velka cisla v C

[Karel Machyna]

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

---

---

Odpovědi

[Dr. Eddy]

Pokud Vam jde o tu mocninu, tak muzete pouzit cinskou vetu o zbytcich.

[Michal Kubeček]

Tak to by mne docela zajímalo. Můžete to nějak rozvést?

[luky]

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.

[Michal Kubeček]

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

[luky]

Ono se to vyplati i u mensich modulu kvuli rychlosti.

[luky]

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.

[Filip Jirsák]

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]

print 2**249 % 997

Otázka je jestli to počítá tak jak bys chtěl (kvůli rychlosti apod).

[lertimir]

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]

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.

[tom]

Doplnim, ze v pythonu je pow(a,b,c)=a^b mod c.

[pavlix]

Díky.

[Michal Kubeček]

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

[lertimir]

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í

[Michal Kubeček]

Já zase chtěl upozornit, že nelze doporučit optimální algoritmus, když vlastně nevíme, které z operandů jsou "velké".

[jano]

algoritmus square and multiply by to mal riesit pomerne rychlo a jednoducho

[pavlix]

+1