[ z@re @ 14.06.2005. 00:04 ] @
treba mi algoritam za mnozenje dva n-bitna binarna broja u C-u. algoritam sam napisa po skolskom primjeru mnozenja binarih brojeva, ali je prespor i ima preveliku kompleksnost. trebalo bi mi nesto poput strassenovog algoritma pomocu brzih fourierovih transformacija, ali nemogu niti nac pseudokod na netu za to. i bilo bi idealno kad bi se algoritam mogao prilagoditi da radi sa binarnim brojem koji je reprezentiran bool poljem, a ne integerom. hvala unaprijed.
[ vlaiv @ 16.06.2005. 22:43 ] @
Probaj nesto ovako:

struct VelikiBroj {
...
}TVelikiBroj, PVelikiBroj*;

// ne znam kako si ga nazvao pa cisto ... :) a i vise ce biti pseudo kod ...

void DodajNa(PVelikiBroj a, PVelikiBroj b); //napravis funkciju koja na veliki broj dodaje drugi ... (algoritam sa Carry-jem i jednom for petljom)

bool BitAt(PVelikiBroj a, int pozicija); //vraca da li je bit na poziciji "upaljen"

void ShiftIt(PVelikBroj a); //siftuje sve upaljene bit-ove za jedan na levo ...

PVelikiBroj Mnozi(PVelikiBroj a, PVelikiBroj b){

PVelikiBroj rezultat = alociraj memoriju i postavi na 0;

for(int i=0;i<BinearnihCifara(b);i++){
if(BitAt(a,i))
DodajNa(rezultat,b);
ShiftIt(b);
}

return rezultat;
}
// samo pazi, funkcija ovakva kakva je menja sadrzaj broja b, pa napravi ili lokalnu kopiju ili prilikom zvanja posalji kopiju ukoliko ti treba original ...

Eventualna optimizacija je da u for petlju stavis broj sa manje "upaljenih" bitova...