Aritmetika velikih brojeva

[ chachka @ 18.11.2007. 20:28 ] @

Neka su veliki integeri prikazani kao niz cifara u stringu:

Code:
var a, b: String;
...
a := '12345678901234567890';
b := '1234';

Potrebno mi je sabiranje ova dva integera, oduzimanje, mnozenje, celobrojno delenje i ostatak pri celobrojnom delenju. Znaci potrebne su mi funkcije:

Code:
function Add(a, b: String): String;
function Sub(a, b: String): String;
function Mul(a, b: String): String;
function Div(a, b: String): String;
function Mod(a, b: String): String;

Drugim recima, trebaju mi funkcije koje rade sledece:

Code:
var c, d, e, f: String;
...
c := '123';
d := '12';
e := Div(c, d); // e = '10'
f := Mod(c, d); // f = '3'

[ Milan Milosevic @ 18.11.2007. 22:32 ] @

Malo ti treba.
Ja sam to radio par meseci.
Pogledaj na netu ima neke gotove komponente.

[ savkic @ 19.11.2007. 01:00 ] @

Iako problem možda deluje komplikovano, zapravo je jednostavan. Treba krenuti od škole tj. od sistema kako su nas učili računskim operacijama. Na papiru nećeš imati nikakvih problema da sabereš ili oduzmeš ma koliko velike brojeve, za množenje i deljenje isto nije teško, samo treba više vremena. Dakle, algoritam je prost i svodi se na simulaciju ručnog računanja. Evo ti primer za moduo, pravio sam ga kod potrebe računanja kontrolne cifre pa je zato delilac ograničen.
A naravno možeš uzeti i neku biblioteku specijalizovane namene.

Code:

function StrMod(const ABroj: string; const ADenumerator: Smallint): Integer;
var
  Temp: string;
  BrojCifara: Smallint;
  TempNumerator: Integer;
begin
  Temp := ABroj;
  BrojCifara := Length(IntToStr(ADenumerator)) + 1;
  repeat
    TempNumerator := StrToIntDef(Copy(Temp, 1, BrojCifara), 0);
    Result := TempNumerator mod ADenumerator;
    Temp := IntToStr(Result) + Copy(Temp, BrojCifara + 1, Length(Temp) - BrojCifara);
  until Temp = IntToStr(Result);
end;

[ Milan Milosevic @ 19.11.2007. 06:42 ] @

Da u zavisnosti koju brzinu izracunavanja zelis da postignes. Ako zelis da samo izracunas, a da cekas 10 min
za mnozenje brojeva od par hiljada decimala moze relativno lako.
Sto se tice mnozenje, na ovom forumu je dat algoritam pre jedno par godina. Potrazi da se ne mucis da
ga pravis iz pocetka. Ako nije obrisan.

[ savkic @ 19.11.2007. 09:54 ] @

> Da u zavisnosti koju brzinu izracunavanja zelis da postignes. Ako zelis da samo izracunas, a da cekas 10 min
> za mnozenje brojeva od par hiljada decimala moze relativno lako.

Današnji računari su veoma brzi, možda par sekundi ili ispod sekunde.

[ Milan Milosevic @ 19.11.2007. 12:33 ] @

Daj takav algoritam da ga probamo ja imam dosta brzu masinu.

[ savkic @ 19.11.2007. 13:09 ] @

> Daj takav algoritam da ga probamo ja imam dosta brzu masinu.

Algoritam bi bio kao onaj na papiru, nikada mi nije trebao i nemam kod, a sad baš i nemam vremena da ga zarad diskusije pišem. Možeš probati dati primer za moduo.

[ chachka @ 19.11.2007. 13:27 ] @

Citat:

Milan Milosevic: Malo ti treba.

Ok, možda sam preterao kada sam tražio gotove funkcije :) Dovoljan mi je i link koji sadrži adekvatne algoritme. Ne trebaju mi neki preterano brzi algoritmi bitno je da rade sa string prezentacijom velikih brojeva.

Savkić koristi 'StrToIntDef' da pretvori delioca iz stringa u integer. Tako nešto sam radio i ja, ali šta ako je delilac prevelik da bi se mogao konvertovati u integer (ili int64)?

[ savkic @ 19.11.2007. 14:30 ] @

> Savkić koristi 'StrToIntDef' da pretvori delioca iz stringa u integer. Tako nešto sam radio i ja, ali šta ako je delilac prevelik da bi se
> mogao konvertovati u integer (ili int64)?

U onom primeru je delilac smallint dakle mali broj i uzima se samo onoliko cifara koliko ima i sam delilac, tako da nema opasnosti. Ako i delilac ima više od 18 cifara (ne može da potpadne pod Int64), onda bi morao da se izdeli na manje delove, svaki se od njih podeli i na kraju se zbroje rezultati.

[ Milan Milosevic @ 19.11.2007. 15:08 ] @

Evo da ne budem cicija. Ovde imas jedan prost primer i funkciju za sabiranje string celobrojnih vrednosti.

_{[Ovu poruku je menjao Milan Milosevic dana 19.11.2007. u 16:32 GMT+1]}