[es] - Aritmetika velikih brojeva

chachka
Srđan Mijatov
Programer
BUS Computers
Kikinda

Član broj: 53780
Poruke: 576
*.ADSL.neobee.net.

Sajt: www.baze-podataka.net

+4 Profil

Aritmetika velikih brojeva

^{18.11.2007. u 20:28 - pre 200 meseci}

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'

"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

Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
212.200.223.*

+31 Profil

Re: Aritmetika velikih brojeva

^{18.11.2007. u 22:32 - pre 200 meseci}

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

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 01:00 - pre 200 meseci}

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;

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

Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
212.200.223.*

+31 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 06:42 - pre 200 meseci}

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.

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 09:54 - pre 200 meseci}

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

Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
212.200.223.*

+31 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 12:33 - pre 200 meseci}

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

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 13:09 - pre 200 meseci}

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

Odgovor na temu

chachka
Srđan Mijatov
Programer
BUS Computers
Kikinda

Član broj: 53780
Poruke: 576
*.simex-su.co.yu.

Sajt: www.baze-podataka.net

+4 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 13:27 - pre 200 meseci}

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

"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

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 14:30 - pre 200 meseci}

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

Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
212.200.223.*

+31 Profil

Re: Aritmetika velikih brojeva

^{19.11.2007. u 15:08 - pre 200 meseci}

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

Prikačeni fajlovi

Sabiranje_Stringova.pas - 3.22k

Odgovor na temu