BigNum
BigNum
Mam nejake velke cisla (typicky desiatky cifier) ulozene v stringu a definujem pre ne operatory. Nejako som sa zasekol na deleni. Trocha som googlil a nasiel som nejake algoritmy. Tie ale pouzivaju bitovy shift a pride mi strasne chore, prevadzat moj desiatkovy string na binarny a potom este shiftovat
. Neexistuje nejaky jednoduchsi algoritmus, ktory este pracuje v realnom case?
-
Sagittarius
Guru
- Príspevky: 2883
- Registrovaný: 13 feb 2007, 21:58
- Bydlisko: Do nekonečna a ešte ďalej
Re: BigNum
A programovací jazyk, v ktorom to robíš? A mohol by si trocha podrobnejšie opísať tvoj problém. Lebo napr. ja som ho nepochopil.
Máš čísla uložené v stringu? Takže: jedno číslo jeden string napr. retazec = "1234567890" alebo máš v stringu celé delenie napr. retazec = "1234567890 / 9876543210" alebo ako?
A zmeň si názov témy.
A zmeň si názov témy.
-
audiotrack
VIP
- Príspevky: 25958
- Registrovaný: 09 sep 2005, 18:39
- Kontaktovať používateľa:
Re: BigNum
jazyk je tu dosť dôležitý, lebo napríklad v pascale by ti násobenie obrovských čísel (a teda aj delenie) spôsobilo chybu, v céčku by to prešlo ale so zlým výsledkom (pretečenie), v mahtlabe by ti to vyrátalo bez problémov...
Re: BigNum
Robim to v c++, a kedze najvacsi int aky som schopny ulozit na 64-bit. architekture ma 20 cifier tak pouzivam string.
Napr.:
A robim pre to aritmetiku, cize napr. pre + si parsujem ten string a scitavam to po cifrach odkonca (ako na zakladke), detto pre -, ale pre delenie to uz nefunguje tak ako v skole. Tak som na nete nasiel nejake kniznice co sa tykaju tohto problemu (bignums), ale tie boli velmi optimalizovane (pre mna necitalne
). Tak som hladal nejaky algoritmus, ale tiez bez uspechu 
Napr.:
Kód: Vybrať všetko
std::string s1 = "1234567890123456789012345678901234567890";
std::string s2 = "123456789012345678901234567890";
-
harrison314
Hardcore addict
- Príspevky: 8224
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: BigNum
Chceš aby bol výsledok reálne alebo cele číslo ?
Re: BigNum
Robim to pre Int cize vsetko celociselne.
-
harrison314
Hardcore addict
- Príspevky: 8224
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: BigNum
Skučal si delenie implementovať pomocou odčítania ?
Z hľadiska zložitosti to nieje bohviečo ale je to jednoduché riešenie, lebo odčítanie aj sčítanie máš hotové.
Z hľadiska zložitosti to nieje bohviečo ale je to jednoduché riešenie, lebo odčítanie aj sčítanie máš hotové.
Re: BigNum
To som skusal ako prve a je to strasne pomale. Predstav si, ze mas 40mieste cislo a delis ho jednotkou...
-
harrison314
Hardcore addict
- Príspevky: 8224
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: BigNum
Delenie jednotkou je extrémny prípad, ono by to chcelo optimalizáciu, napríklad neinkrementovať priamo číslo ( budúci výsledok delenia) v textovom formáte ale napr long int, ktorý po určitom limite pripočítaš k výstupu.
Deliť 1,2,5,10^n vieš velmi rýchlo, a keď dpravis nejake zazraky s čitatelom aj menovatelom môžeš to značne urýchliť.
Deliť 1,2,5,10^n vieš velmi rýchlo, a keď dpravis nejake zazraky s čitatelom aj menovatelom môžeš to značne urýchliť.
Re: BigNum
To nepojde, ked delitel uz je za hranicou long intu, teda napr. ak delim 100 cif. cislo 30 cif.
-
harrison314
Hardcore addict
- Príspevky: 8224
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: BigNum
Asi si ma nepochopil, skusim sem hodit pseudokod,
strint je cislo v textovom formate,
strint je cislo v textovom formate,
Kód: Vybrať všetko
strint a =....;
strint b= ....;
strint v = 0; // vystup v=a/b;
int buff;
if( b == 1) return a;
// tu skusis oba cleny delit 10^n ak pojdu
// takisto 2kou a 5
buff =0;
while( a > 0)
{
a = a -b ;
buff++;
if( buff > BUFF_MAX ) v = v + buff;
}
v--;
return v;
Re: BigNum
mozno to este stale nechapem, ale snazime sa zmensit obe cisla tym ze ich budeme delit tym 10^n, 2 , 5... A potom odcitame cyklom.
Ale co ked je nejake z nich prvocislo, proste ich nedokazem zmensit.
Podla mna to odcitanim cyklom nepojde, lebo som skusil nieco take a aj tak to slo neskutocne pomaly:
//autoeditácia príspevku (10 Feb 2011, 16:30)
ok, tam som to nakoniec nejako vyriesil, dakujem za pomoc
Ale co ked je nejake z nich prvocislo, proste ich nedokazem zmensit.
Podla mna to odcitanim cyklom nepojde, lebo som skusil nieco take a aj tak to slo neskutocne pomaly:
Kód: Vybrať všetko
//pocitam this / other
//stringint je class, ktora obsahuje string pomenovany stringInt
//bezparametricky konstruktor to inicializuje na 0
stringint si; // vysledok, navysujem o chunk
stringint temp; // spocitavam delitel
stringint chunk; // vypocitam 10^(rozdiel dlzkok stringov)
long int length = this->stringInt.length() - other.stringInt.length();
if (length == 0) {
chunk.stringInt = "1";
} else if (length > 0) {
chunk = stringint(10L) ^ stringint(length);
}else {
return si;
}
while (true) {
temp = temp + other * chunk;
si = si + chunk;
//tu porvnavam ci som uz neprekrocil hranicu, ak ano tak backtrekujem a chunk znizim o polovicu
//a ak chunk je 1 tak samozrejme koncim, kedze ho uz nemozem znizit
if (this->stringInt.length() < temp.stringInt.length()) {
temp = temp - stringinT * chunk;
si = si - chunk;
if (chunk.stringInt == "1") {
break;
} else {
chunk = chunk / stringint(2L);
}
} else {
if (this->stringInt.length() == temp.stringInt.length()) {
if (this->stringInt < temp.stringInt) {
temp = temp - stringinT * chunk;
si = si - chunk;
if (chunk.stringInt == "1") {
break;
} else {
chunk = chunk / stringint(2L);
}
}
}
}
}
ok, tam som to nakoniec nejako vyriesil, dakujem za pomoc
-
harrison314
Hardcore addict
- Príspevky: 8224
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: BigNum
Ako 
Re: BigNum
Nejako takto:
Snad to pochopis 
Kód: Vybrať všetko
// pocitam *this / other
// stringint obsahuje string s nazvom stringInt
stringint ret; //vysledok
stringint temp;
unsigned int pos = 0; // "ukazatel" na poziciu v 1cisle
unsigned int i; // pocitadlo
// do tempu vlozim tolko cifier z prveho cisla kolko cifier ma druhe
for (; pos < other.stringInt.length(); pos++) {
temp.stringInt.push_back(this->stringInt[pos]);
}
//kazdy cyklus vydeli temp otherom a potom prida k tempu dalsiu cifru z *this
for (; pos < this->stringInt.length() + 1; pos++) {
i = 0;
//delenie odcitacim cyklom
while (temp > 0) {
temp = temp - other;
i++;
}//ak sa prekroci nula tak backtrackujem a v temp mi ostane zvysok ku ktoremu pridam dalsiu cifru z *this
i--;
temp = temp + den;
temp.stringInt.push_back(this->stringInt[pos]);
ret.stringInt.push_back(i + 48);//zapisujem do vysledku
}