Diskuze: Rýchle počítanie s veľkými číslami

V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Ferko

Člen

Ferko:5.3.2018 17:06

Ahoj,
mám problém s jedným programom:
Máme pole n čísel <1..100> a q otázok. Každá otázka je tvorená troma číslami (o,d,m). Pre každú otázku treba napísať (súčin čísel ležiacich v poli na pozíciach o až o+d-1) mod m.

Problém je, že n môže byť aj 10⁵, čo zapríčiní, že súčin sa nezmestí ani do long a BigInteger je pomalý.

Nenapadá vás nejaké rozumnejšie riešenie?

Ďakujem

Príklad princípu v Pythone:

for i in range(q):
    o,d,m=input().split()
    o,d,m=int(o),int(d),int(m)
    s=1
    for j in range(o-1,o+d-1):
       s*=p[j]
    print(s%m)

Editováno 5.3.2018 17:07

Odpovědět

5.3.2018 17:06

DHPICO

Tvůrce

DHPICO:5.3.2018 17:42

když se ti to nejvejde do Long, tak můžeš rozložit výpočet a ukládat si to do Stringu, ale nedokážu říct, zda to je rychlejší než BigInteger

Nahoru Odpovědět

5.3.2018 17:42

Požehnáni budíš oráj

krepsy3

Tvůrce

krepsy3:5.3.2018 17:58

BigInteger je, alespoň v .NETu, velmi dobře optimalizovaná struktura. Zároveň je bezpečná a spolehlivá. Nevím, zda by specificky tento úkol šel matematicky udělat nějakou rychlejší cestou přes string, nicméně bych ti doporučil bigint.

Zamyslím-li se, tak jako zrovna 10⁵ je celkem v pohodě, protože je to ta desítka, za kterou se ti kumulují nuly, jak víc a víc násobíš, takže by to šlo řešit cestou "dvojího násobení" - v hlavní cestě násobíš čísla a odtrhuješ nulové řády, jejichž exponent pak násobíš v té druhé cestě, a ve finálním výpisu to dáš dohromady. Teoreticky by se tato možnost dala aplikovat na jakákoliv čísla ve "věděcké notaci" a ukládat do typu double, ale hrozilo by znepřesnění výpočtu kvůli desetinné čárce, pokud by čísel bylo moc.

P.S. Vědecká notace = 3278.2 = 3.2782e3 = 3.2782 * 10³

Editováno 5.3.2018 18:00

Nahoru Odpovědět

5.3.2018 17:58

Programátor je stroj k převodu kávy na kód.

Jindřich Máca

Tvůrce

Jindřich Máca:5.3.2018 18:13

Pánové, opravdu? Jelikož tohle je typický "školní" příklad, tak trik je čistě matematický. Čísla řádu 10⁵, dokonce i vynásobená mezi sebou, se do long bohatě vejdou a víc nepotřebujete, protože Základní pravidla modulární aritmetiky. :-`

Můžete modulovat po každém násobení, dokonce každé to číslo samotné před tím násobením, což většinou značně sníží jeho řád, a pokud modulujete všechno stejným číslem, celkový výsledek se nezmění.

Editováno 5.3.2018 18:14

Nahoru Odpovědět

5.3.2018 18:13

Patrik Valkovič

Člen

Patrik Valkovič:5.3.2018 18:17

Malá fermatova věta
Eulerova věta

Editováno 5.3.2018 18:18

Nahoru Odpovědět

5.3.2018 18:17

Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.

Ferko

Člen

Ferko:5.3.2018 18:39

Ďakujem, toto by teda malo fungovať?

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s mod m);
  end;

alebo aj toto?

for j:=a to a+x-1 do s*=(k[j] mod m);

Nahoru Odpovědět

5.3.2018 18:39

Jindřich Máca

Tvůrce

Jindřich Máca:6.3.2018 0:33

Lépe bude fungovat to první, protože v tom druhém Ti s bude pořád narůstat, i když o něco pomaleji a na konci ho pak musíš ještě zmodulovat do výsledné podoby. Naopak u toho prvního držíš celé s pravidelnou modulací v přiměřeném rozsahu a po skončení cyklu už ho ani modulovat nemusíš.

Pro jistotu tedy:

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s); # s již prošlo mod na konci cyklu
  end;

P.S.: Nejlepší bude, když si sám napíšeš nějakou krátkou řadu malých čísel a zkusíš si to spočítat, jestli to sedí.

Nahoru Odpovědět

6.3.2018 0:33

Naučíme tě pracovat na home-office.

Zjistit více...

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.

Nejčastěji vyhledáváné

Diskuze: Rýchle počítanie s veľkými číslami