Aritmetika velikih brojeva

Aritmetika velikih brojeva 18.11.2007. u 20:28 · pre 230 meseci #1

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'

Potpis

"The best code is no code at all."
- Zidar (ES član)
"Biggest obstacle to learning
SQL is unlearning procedural
programming." - Joe
Celko
"Minimize code, maximize data."
- A. Neil Pappalardo

Re: Aritmetika velikih brojeva 18.11.2007. u 22:32 · pre 230 meseci #2

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

Re: Aritmetika velikih brojeva 19.11.2007. u 01:00 · pre 230 meseci #3

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;

Potpis

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Re: Aritmetika velikih brojeva 19.11.2007. u 06:42 · pre 230 meseci #4

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.

Re: Aritmetika velikih brojeva 19.11.2007. u 09:54 · pre 230 meseci #5

> 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.

Potpis

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Re: Aritmetika velikih brojeva 19.11.2007. u 12:33 · pre 230 meseci #6

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

Re: Aritmetika velikih brojeva 19.11.2007. u 13:09 · pre 230 meseci #7

> 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.

Potpis

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Re: Aritmetika velikih brojeva 19.11.2007. u 13:27 · pre 230 meseci #8

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)?

Potpis

"The best code is no code at all."
- Zidar (ES član)
"Biggest obstacle to learning
SQL is unlearning procedural
programming." - Joe
Celko
"Minimize code, maximize data."
- A. Neil Pappalardo

Re: Aritmetika velikih brojeva 19.11.2007. u 14:30 · pre 230 meseci #9

> 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.

Potpis

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Re: Aritmetika velikih brojeva 19.11.2007. u 15:08 · pre 230 meseci #10

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]}

Sabiranje_Stringova.pas3.22k

Srodne teme