Mnozenie dwoch liczb w systemie BCD [C++]

[gofeer]

Musze napsiac program ktory mnozy dwie liczby dodatnie podane w BCD(binary coded decimal). Problem polega na tym ze nie za bardzo mam pomysl, W BCD liczba 52 to 0101(oznacza 5)0010 (oznacza 2) czyli mamu 01010010. Kolejne zestawy 4 bitow liczac od prawej oznaczaja jednosci, dziesiatki, setki, itd... Mi wystarczy to dla osmiu bitow czyli maksymalna liczba moze wynosic 99 xxxxyyyy. Do programu wprowadzamy liczby w postaci BCD(xxxxyyyy) nastepnie trzeba je zamienic na sys 10 przmnozyc i spowrotm wyswietlic w BCD no chyba ze ktos ma jakis inny pomysl to kazde rozwiazanie mile widziane, szukalem tez na googlach ale nic ciekawego co by sie nadawalo nie znalazlem, jak ktos ma cos o tym w Pl , Eng to tez sie chenie zapoznam

[Nargil]

1. wczytuj sobie bcd jako string

2. przeksztalc 4 kolejny bity na cyfre

3. pomnoz

4. wynik rowniez zapisz jako string

5. kolejne cyfry stringa zamieniaj na bcd

 

ja tu problemu nie widze... bym nie mial takiego problemu z czasem to bym ci to zrobil.

[gofeer]

dzieki za pomysl ale jeszcze mam pytanie jak ze stringu wyodrebnic po cztery bity i przeksztalcic to na cyfre zwykla a nastepnie w druga strone(chicaz to to juz pewnei bedzie analogicznie) jabys mogl mi podac ten fragment kodu z jakims wyjasnieniem to bylbym wdzieczny

[gofeer]

dzieki za pomysl ale jeszcze mam pytanie jak ze stringu wyodrebnic po cztery bity i przeksztalcic to na cyfre zwykla a nastepnie w druga strone(chociaz to to juz pewnie bedzie analogicznie) jabys mogl mi podac ten fragment kodu z jakims wyjasnieniem to bylbym wdzieczny

[Nargil]

[php:1:c93d6d53ea]

string bcd1;

int i;

int wykladnik=0;

int nrbitu=1;

int liczba1=0;

 

// sprawdzanie czy liczba bitow w stringu bcd1 jest wielokrotnoscia 4 - aby uniknac zwisu przy 101 lub 10 zamieniamy je na odpowiednio 0101 i 0010

int tmp;

tmp=bcd1.length()/4;

if(tmp*4!=bcd1.length()) // jesli nie to dorzucamy na poczatek brakujace zera

{

tmp=bcd1.length()-(tmp*4);

for(i=0; i<4-tmp; ++i)bcd1.insert(0,"0");

}

 

// teraz przeksztalcamy bcd na liczbe

for(i=0; i<=bcd1.length()-1; ++i)

{

if(nrbitu<=4){

tmp=i/4;

liczba1=(bcd1.at((tmp*4)+(4-nrbitu))-48)*powl(2,wykladnik)+liczba1;

++nrbitu;

++wykladnik;

}

if(nrbitu==5 && i!=bcd1.length()-1){

nrbitu=1;

wykladnik=0;

liczba1*=10;

}

}

[/php:1:c93d6d53ea][php:1:c93d6d53ea]

// teraz dzialasz tak samo z liczba2

 

char wynik[20+1]; // 20 oznacza ze akceptowany wynik mnozenia jest maksymalnie 20-cyfrowy ( zmieniaj do woli )

sprintf(wynik,"%d", liczba1*liczba2);

 

for(i=strlen(wynik)-1; i>=0; --i)

{

int s=0,c,a;

long int n,bin=0;

n=wynik-48;

do

{

c=n%2;

n=n/2;

bin=c*powl(10,s)+bin;

s++;

}

while(n>=1);

char bity[5];

sprintf(bity,"%4ld", bin);

for(int j=0; j<=4; ++j)if(bity[j]==' ') bity[j]='0';

wynikbcd.insert(0,bity);

}

[/php:1:c93d6d53ea]

 

glowy sobie uciac nie dam ( ale migdalki co mnie bola to chetnie ) ze to jest bezbledne ale powinno dzialac :) troche samoinicjatywy tez mozesz wykazac i ewentualnie poprawic. masz szczescie ze zachorowalem i znalazlem troche czasu dla ciebie ;p

[sapero]

witam

 

właśnie dzisiaj przyspieszyłem programik do liczenia silnii (dobry dodatek w asmie) - i tak się składa, że operuje w BCD

 

Zastosowałem tu szybkie mnożenie - dwie tablice - jedna to wynik i zarazem można, druga to taka podręczna pamięć dla szczątkowego wyniku

 

mnożnik to liczba typu DWORD (4bajty). Wielkość obu tabel ogranicza tylko wydajność komputera:

 

A i B to tabele, BC to mnożnik, tabela A to wynik i zarazem mnożna. Należy do niej wpisać liczbę którą się chce pomnożyć (oczywiście w BCD). Najmniej znaczące cyfry znajdują się na początku tabeli ( a[0] ) Tabela B powinna być wyzerowana przed mnożeniem

CHAR a[0xFFFFF], b[0xFFFFF] /* 2097150 cyfr dla wyniku */'zerowanie tabelRtlZeroMemory(&a, 0xFFFFF)RtlZeroMemory(&b, 0xFFFFF)'mnożymy 40000 * 7a[0]=7UINT BC, LenA /* LenA to ilość bajtów wyniku */BC = 40000LenA = 1'start'NASM assembler IBasic PRO     _asm         MOV  eax,[$BC] ;eax = 40000LoopDo:         MOV  ebx,eax         AND  ebx,1         JZ   RLCA           ; jump if BC & 1 = 0         DEC  eax            ; mul--         PUSH eax;*************************AddAtoB:            MOV  ecx,[LenA]  ; Counter            MOV  edx,$b            MOV  ebx,$a            CLC              ; Clear Carry      LaddAB:            MOV  al,[edx]    ; Get 2 bytes from b[n]            ADC  al,[ebx]    ; Add a[n]            DAA              ; BCD correction            MOV  [edx],al    ; Store in b[n]            INC  edx            INC  ebx            LOOP LaddAB      ; 'next n'            JNC  Lrlcaexit            INC  dword[edx]  ; if Carry then add one digit            JMP  Lrlcaexit;*************************RLCA:         SHR eax,1           ; mul = mul >> 1         PUSH eax;*************************            MOV  ecx,[LenA]  ; Counter            MOV  ebx,$a            CLC              ; Clear Carry      Lrlca:            MOV  al,[ebx]    ; Get 2 bytes from a[n]            ADC  al,al       ; bytes *2 + Carry            DAA              ; BCD correction            MOV  [ebx],al    ; Store in a[n]            INC  ebx         ; n++            LOOP Lrlca       ; 'next n'            JNC  Lrlcaexit            INC  dword[ebx]  ; if Carry then add one digit            INC  dword[$LenA]; and inc number of digits;*************************Lrlcaexit:         POP  eax         CMP  eax,1         JA  LoopDo          ;   until BC>1;*************************AddBtoA:            MOV  ecx,[LenA]  ; Counter            MOV  edx,$a            MOV  ebx,$b            CLC              ; Clear Carry      LaddBA:            MOV  al,[edx]    ; Get 2 bytes from a[n]            ADC  al,[ebx]    ; Add bytes from b[n]            DAA              ; BCD correction            MOV  [edx],al    ; Store in a[n]            INC  edx         ; n++            INC  ebx            LOOP LaddBA      ; 'next n'            JNC  LaddBAexit            INC  dword[edx]  ; if Carry then add one digit            INC  dword[$LenA]; and inc number of digitsLaddBAexit:         _endasm

Jak to działa:

jeśli BC jest parzyste : podziel BC przez 2 a wynik pomnóż przez 2

a jeśli BC nie jest parzyste : odejmij jeden od BC i dodaj wynik (tabela A) do liczby BCD w tabeli B

powtarzaj od początku dopuki BC > 1

na końcu dodaj liczbę z tabeli B do liczby z tabeli A

 

jak łatwo zauważyć dla mnożnika 40000 cała pętla wykona się 16 razy (40000 to 16 bitów) a zatem jest to (chyba) najszybszy algorytm mnożenia, urodzony w czasach rozkwitu zx spectrum 8)

 

Liczbę cyfr wyniku obliczamy

digits = (LenA * 2) - (a[LenA-1]<0x10)

wynik można wyświetlić tak

sub PrintA   INT x   For x=LenA-1 to 0 step -1      Print Hex$(a[x]), /* dla delphii: IntToHex(a[x], 2) */   Next x   ReturnEndsub

kilka wyników obliczania silnii tym alborytmem na Athlonie 2800+

1000! - 0.078s 2568 cyfr

10000! - 13s 35660 cyfr

50000! - 7min 213237 cyfr

75000! - 19min 333061 cyfr

[[k@rol]]

Hehe sapero... to trochę wolno. ;) Windowsowy kalkulator robi to około 17 razy szybciej na Athlonie 1800+. :P

Dla przykładu silnia z 75000 zajęła mu nieco ponad minutę. ;)

[sapero]

2,2142807374883101672219837615212e+333060

to wynik z kalkulatora - u mnie liczył jakieś 20s i wywalił 2 okienka że to potrwa i czy kontynuować

co mam zrobić z tymi kilkoma cyferkami? tyle wiem że wynik jest 2e333060 ale nam chodzi o prawdziwy wynik

 

taki jeden serwer "liczy" 3 razy szybciej- ciekawe czy ma pośrednie wyniki czy jest taki krass. Porównałem się z wynikiem z serwera: identico :)

 

niestety studenci zrobili bałagan na stronie i link jest bad; a jeśli ktoś chciałby sprawdzić swój wynik obliczeń to chętnie udostępnię albo program albo wynik