Kalkulačka s libovolnou přesností? – C / C++ – Fórum – Programujte.com

Potřeboval bych poradit s kalkulačkou co má mít libovolnou přesnost - tzn. počítá ve zlomkách a délka čísel může přesahovat long a double.

Vstupem kalkulačky má být postfixová notace (RPN) http://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace

Začínám nad tím přemýšlet a pořád mě nenapadá nějaké elegantní řešení.. Proto se chci zeptat zkušených programátorů jak by na to teoreticky šli.. :)

Nevím jestli je to úplně nejlepší řešení, ale co takhle si vytvořit pole znaků - každý prvek by byla jedna číslice:

112 + 35 = 147

1, 1, 2
0, 3, 5
-----
1, 4, 7

stejně řešit i násobení a odčítání - jen u dělění si nejsem jistý, protože mě nenapadá řešení, které by zahrnovalo dělit i např. 50 místným číslem...

Předpokládám, že to RPN nějak zvládneš, jediný problénm bude asi to dělení

LJ1024 napsal:
Nevím jestli je to úplně nejlepší řešení, ale co takhle si vytvořit pole znaků - každý prvek by byla jedna číslice:

112 + 35 = 147

1, 1, 2
0, 3, 5
-----
1, 4, 7

stejně řešit i násobení a odčítání - jen u dělění si nejsem jistý, protože mě nenapadá řešení, které by zahrnovalo dělit i např. 50 místným číslem...

Předpokládám, že to RPN nějak zvládneš, jediný problénm bude asi to dělení

Prečo by pole mao vyť take veľké ako je hodnota double ? ak chceč reprezentovať číslo 1 000 000 nepotrebuješ milion prvkov, stači 7

ps: aka škola / fakulta ?

ale tech prvku by to pole klidne i ten milion mohlo mit :)

"libovolnou přesnost" ? To jako ze umi fakt libovolny pocet znaku? Treba i vic nez nacpes do vsech disku na svete? Treba i spocitat pi naprosto presne? To je dost tezke zadani.
Ale k reseni s omezene neomezenou presnosti- udelat si spojaky/nafukovaci pole, od nejmensi cifry po nejvetsi a pak s nima pocitat.Je to jednoduche, a vysledek je hned. Pak jeste neco na zjednodusovani zlomku.

Krychlik napsal:
"libovolnou přesnost" ? To jako ze umi fakt libovolny pocet znaku? Treba i vic nez nacpes do vsech disku na svete? Treba i spocitat pi naprosto presne? To je dost tezke zadani.
Ale k reseni s omezene neomezenou presnosti- udelat si spojaky/nafukovaci pole, od nejmensi cifry po nejvetsi a pak s nima pocitat.Je to jednoduche, a vysledek je hned. Pak jeste neco na zjednodusovani zlomku.

To LJ1024 : Ano, bude omezena pocitacem, takze nebude libovolna. Libovolna presnost proste nejde.

To Krychlik : Tu sa hovori o presnosti algoritmu. A ta teda 100% byt moze, aj ked to dnesne pocitace nezvladaju.

pokud vyresis problem s delenim, tak to sem prosim dej, diky... :)

problem s delenim rieši spôsob ukládania čísel. Bude potrebné vytvoriť metody na krátenie zlomku a hľadanie spoločného menovateľa.

problem vidím v časovej zložitosti násobenia, co tak implementovat Karacubovo násobení

To Wizard : zadani znelo jasne "...kalkulačkou co má mít libovolnou přesnost..." zadny algoritmus, proste kalkulacka, a ta uplne presna nebude nikdy.

vzhledem k tomu, ze to byl ukol na programovani a ne na sestavovani nejakeho pristroje, tak se mluvi o presnosti algoritmu... Pokud reknes nejake libovolne cislo (presnost), tak bude stale mensi nez nekonecno - tudiz lze vytvorit pocitac, ketry to zvladne.

"Pokud reknes nejake libovolne cislo (presnost), tak bude stale mensi nez nekonecno - tudiz lze vytvorit pocitac, ketry to zvladne." Reknu teba gogoleplex- to je vic nez atomu ve vesmiru> nejde vytvorit takovy pocitac> neni pravda ze pro kazdou presnost jde vytvorit takovy pocitac> nejde vytvorit takova kalkulacka, at mas algoritmus jaky chces. Lójrt.

To Krychlik : Keby si aspoň trochu poradil a nie tu len spamoval. Nikoho nezaujímajú tvoje konšpiračné teórie.
To jvaclavik : Mohol by si sa inšpirovať nejakou už dostupnou knižnicou, napr.: http://gmplib.org/ A tá poznámka, že počíta v zlomkoch by mohla znamenať len implementáciu racionálnych čísiel, čo nie je moc zložité. A má to byť v C alebo C++?

To m->29 : Uz sem poradil jak resit omezenou presnost, jenom tvrdim ze zadani je nesplnitelne. Nevim o tom, ze bych psal nejake konspiracni teorie, ale rad se necham opravit.

Krychlik napsal:
To m->29 : Uz sem poradil jak resit omezenou presnost, jenom tvrdim ze zadani je nesplnitelne. Nevim o tom, ze bych psal nejake konspiracni teorie, ale rad se necham opravit.

Ale abyste nerekli, ze sem jenom spamer, neznaboh a hovado nekulturni tak napisu celej navrh postupu jak pocitat. Predpoklady- vstup jsou pouze zlomky ("...počítá ve zlomkách..."), a operatory jsou pouze +-*/ , zadne mocneni a podobne vylomeniny.
ulozeni cisel- znaminko + 2 spojaky: citatel a jmenovatel, od posledni cifry
pomocne funkce:

scitani celych cisel-jde se od posledni cifry a scitaji se jednotlive cifry a prenos, dokud jedno cislo neskonci, pak se jeste pricita prenos a jak je 0, tak se zkopiruje se zbytek delsiho cisla. Narocnost n.
porovnani velikosti absolutni hodnoty-cisla se prevedou do zapisu od nevetsi cifry, pritom se pocita kolik jich je- bud ma jedno vic a tedy je vetsi, nebo se pak musi jit postupne a az bude jedno mit jednu cifru vetsi tak je vetsi. Narocnost je prevod=n+porovnavani=0, tedy n.
odcitani celych cisel(toto neni nutne poteba, jde upravit scitani)-od vetsiho se odecte mensi a prida se znaminko vetsiho. Odcita se stejne jako scita, jenom prenos je zaporny. Narocnost n.
nasobeni celych cisel- stejne jako lidsky- do vysledku se pricita pro kazdou cifru 2. cisla cifranasobek 1.Nasobeni cifrou se dela stejne jako scitani, jenom prenosy budou vetsi. Jednoduchy trik- spocitat si vsech 10 nasobku prvniho cisla a ty pricitat podle toho co je na prislusnem miste 2. cisla. Narocnost je n*n. Slozity trik Karacuba- rychlost bude asi n na 1,5 ale je poteba nejak rychle pristupovat ke vsem cifram cisla, coz je v teto reprezentaci nemozne(?). Mozna prevod cisel do pole a tam to vynasobit.
deleni delitelem- prevod na tvar od nejvetsi cifry k nejmensi a delit jako polynomy. Je potreba si pamatovat delky cisel. Narocnost n*n
nejvetsi spolecny delitel-eukliduv algoritmus pomoci funkce na odcitani celych cisel, nebo do deleni delitelem pridat jeste spocitani zbytku. Narocnost je "rozumna".


ted samotne funkce na pocitani se zlomky:
c1,c2,c-citatel,j1,j2,j-jmenovatel,C+operator(=celociselne)
scitani(obe cisla stejne znaminko, -5/7 -3/9 je tedy scitani )-
c=c1 C* j2 C+ c2 C* j1
j= j1 C* j2
c= c C/ nejvetsi delitel c a j
j= j C/ nejvetsi delitel c a j
znaminko je znaminko treba prvniho
nasobeni- c=c1 C* c2
j= j1 C* j2
c= c C/ nejvetsi delitel c a j
j= j C/ nejvetsi delitel c a j
znaminko spocitat jako u bezneho nasobeni
deleni- c= c1 C* j2
j= c2 C* j1
c= c C/ nejvetsi delitel c a j
j= j C/ nejvetsi delitel c a j
znaminko jako u nasobeni
odcitani(ruzne znaminka -7/8 + 4/789 je tedy odcitani)
j=j1 C* j2
x=c1 C* j2
y=c2 C* j1
j=od vetsiho z x y celociselne odecist mensi+vysledek ma znaminka vetsiho
c= c C/ nejvetsi delitel c a j
j= j C/ nejvetsi delitel c a j

Tak melo by to byt vsechno.Pokud jsou na vstupu jenom zlomky(odmocniny nee), tak vysledky vsech operaci jsou zase zlomky a teda toto pocita uplne presne. Netvrdim ze je to jedine a nejrychlejsi reseni.Taky nekde muze byt chybka.

Ja by som odporucil pouzit linearny spajany zoznam, kde kazdy prvok zoznamu bude jedna cislica. Konkretne obojsmerny linearny zoznam pre jednoduche ''chodenie'' po jednotlivych prvkoch v obidvoch smeroch

mephi: ČVUT FIT
m->29: C++

pouštím se do realizace a mám pár problémů:

jak načíst ze vstupu číslo delší než datový typ? nemůžu použít
cin >> neco;
potřebuji to rovnou uložit do spojáku, ale jak?


má smysl zadávat vstup ve zlomcích nebo ne? Jsou tu vstupem celá i desetinná čísla.. Teoreticky by to mělo jít udělat způsobem dvou spojových seznamů, kde jeden na celé číslo a druhý na jeho desetinou část. Myslíte že je to vhodné řešení?

Se zlomky by byla složitější manipulace.., navíc nevím jak bych tam aplikoval třeba euklidův algoritmus na největší společný dělitel. Jenže ten bych stejně možná potřeboval na dělení, pro zkrácení, nebo další možnost je dělit to jako polynomy jako píše kolega.

To jvaclavik : nacist ze vstupu delsi datovy typ => musis si ho prevest sam.. nacist treba po znacich a dostat do datovych struktur tak jak je potreba

To jvaclavik : 2 spojaky na celou+desetinou cast bude hodne vesele pocitani. K cemu by to vubec bylo, kdyz stejne v programu pocitas se zlomkama?

To Krychlik : V tom spočívá omezenost většiny lidí. Myslí si, že proto, že to nikdo nedokázal, tak to není možné.

Krychlik napsal:
To jvaclavik : 2 spojaky na celou+desetinou cast bude hodne vesele pocitani. K cemu by to vubec bylo, kdyz stejne v programu pocitas se zlomkama?

neumi pracovat se stringem.. musis pouzit metodu .c_str()

To jvaclavik : Neni pravda, musis s nima pocitat od 1 deleni dal. treba spocti 2/3 + 4 .Plus stejne si musis napsat aritmetiku pro pocitanise zlomkama, tak proc psat 2? A jeste u nasobeni treba 123,456 * 23,45. Jak presne to chces pocitat? Jako zlomek to mas citatel 123456 * 2345 a jmenovatel 1000*100, pak jeste pokratit nejvetsim delitelem. Snadne. Jako spojaky cele cislo + desetine nevidim nejaky rozumny algoritmus, ale treba na nej prijdes, nevzdavej se jenom proto, ze jsem napsal, ze to bude vesele pocitani.
To djanosik : Ano, jestli plati : Preferuje funkcni postup pred postupem, kde je vymyslena jenom reprezentace dat=> je omezeny , pak jsem omezeny. (OT : jestli jsem i uzavreny, pak jsem kompaktni :)

právě jsem takové potřeboval využít "neomezené" rozsahy do jednoduchého interpretu - pokud netrváš na vlastním řešení, mně osvědčila se mi knihovna GMP http://gmplib.org/ . Nad GMP se provádí veškeré operace opravdu rychle...

vojtěch havel napsal:
právě jsem takové potřeboval využít "neomezené" rozsahy do jednoduchého interpretu - pokud netrváš na vlastním řešení, mně osvědčila se mi knihovna GMP http://gmplib.org/ . Nad GMP se provádí veškeré operace opravdu rychle...

vyskytl se mi snad už poslední problém.. A to jak to číslo zkrátit.
Chtěl bych použít euklidův algoritmus, ale nemůžu přijít na to jak dostat z čísla které je uloženo po jednotlivých cifrách v poli modulo.
Napadá mě jen nějakým způsobem využít algoritmus pro "ruční" dělení čísel.. Ale netusím jak to zapracovat do PC, a hlavně když bude dělitel delší než int tak by tam mohl být s tou metodou kdy si sepisuji další čísla problém..

Nenapadá vás řešení?

tak už to mam hotové, po ohodnocení to nahodim na můj web: http://janvaclavik.cz i s dokumentací.

To jvaclavik : Tak gratuluju, je to poradne dilo. Kdy to asi tak bude dostupne?