BigNum

Programovacie jazyky, rady, poradňa...
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

BigNum

Príspevok od používateľa Styx# »

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 :cry:. Neexistuje nejaky jednoduchsi algoritmus, ktory este pracuje v realnom case?
Sagittarius
Guru
Guru
Používateľov profilový obrázok
Príspevky: 2883
Registrovaný: 13 feb 2007, 21:58
Bydlisko: Do nekonečna a ešte ďalej

Re: BigNum

Príspevok od používateľa Sagittarius »

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. :wink:
audiotrack
VIP
VIP
Používateľov profilový obrázok
Príspevky: 25958
Registrovaný: 09 sep 2005, 18:39
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa audiotrack »

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...
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

Robim to v c++, a kedze najvacsi int aky som schopny ulozit na 64-bit. architekture ma 20 cifier tak pouzivam string.
Napr.:

Kód: Vybrať všetko

std::string s1 = "1234567890123456789012345678901234567890";
std::string s2 = "123456789012345678901234567890";
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 :(
harrison314
Hardcore addict
Hardcore addict
Používateľov profilový obrázok
Príspevky: 8224
Registrovaný: 27 máj 2009, 20:42
Bydlisko: Bratislava
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa harrison314 »

Chceš aby bol výsledok reálne alebo cele číslo ?
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

Robim to pre Int cize vsetko celociselne.
harrison314
Hardcore addict
Hardcore addict
Používateľov profilový obrázok
Príspevky: 8224
Registrovaný: 27 máj 2009, 20:42
Bydlisko: Bratislava
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa harrison314 »

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é.
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

To som skusal ako prve a je to strasne pomale. Predstav si, ze mas 40mieste cislo a delis ho jednotkou...
harrison314
Hardcore addict
Hardcore addict
Používateľov profilový obrázok
Príspevky: 8224
Registrovaný: 27 máj 2009, 20:42
Bydlisko: Bratislava
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa harrison314 »

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ť.
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

To nepojde, ked delitel uz je za hranicou long intu, teda napr. ak delim 100 cif. cislo 30 cif.
harrison314
Hardcore addict
Hardcore addict
Používateľov profilový obrázok
Príspevky: 8224
Registrovaný: 27 máj 2009, 20:42
Bydlisko: Bratislava
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa harrison314 »

Asi si ma nepochopil, skusim sem hodit pseudokod,

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;

Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

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:

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);
				}
			}
		}
	}
}
//autoeditácia príspevku (10 Feb 2011, 16:30)
ok, tam som to nakoniec nejako vyriesil, dakujem za pomoc :)
harrison314
Hardcore addict
Hardcore addict
Používateľov profilový obrázok
Príspevky: 8224
Registrovaný: 27 máj 2009, 20:42
Bydlisko: Bratislava
Kontaktovať používateľa:

Re: BigNum

Príspevok od používateľa harrison314 »

Ako :?:
Styx#
Medium Expert
Medium Expert
Používateľov profilový obrázok
Príspevky: 103
Registrovaný: 01 aug 2010, 21:35

Re: BigNum

Príspevok od používateľa Styx# »

Nejako takto:

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
}
Snad to pochopis :D
Napísať odpoveď