Elektroda.pl
Elektroda.pl
X
Elektroda.pl
Advanced Search
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

Obliczenia na b. dużych liczbach (do 2mld miejsc znaczacych)

tzok 06 Mar 2005 16:47 2412 10
Reply | New topic
  • #1
    tzok
    Moderator of Cars  
    Witam, mam taki fajny temat projektu, może komuś przyda się to co już napisałem a może ktoś znajdzie tam jakieś błędy lub zechce dopisać dzielenie.

    Założenia są takie:
    *liczba jest przechowywana w klasie jako tablica bajtów, po jednym bajcie na pozycję
    *klasa zawiera podstawowy interfejs do operacji na liczbie
    *działania są realizowane przez zewnętrzne funkcje (nie metody klasy)
    *reprezentacja liczb jest stałoprzecinkowa bez znaku
    Code: text Expand Select all Copy to clipboard
    //---------------------------------------------------------------------------

#include <stdlib>
#include <string>
#include <stdio>

//---------------------------------------------------------------------------
class liczba
{
private:
        char* tbl;
        int dl;
public:
        liczba(const char*);
        liczba(const int=0);
        ~liczba();
        void set(const char*);
        void setpos(const char, const int);
        char getpos(const int)const;
        char* get()const;
        int getlen()const;
        void print()const;

};

liczba::liczba(const char* _tbl)
{
        dl=strlen(_tbl);
        int i=0, lz=0;
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        tbl=new char[dl-lz];
        for(int i=0; i<dl-lz; i++)
                tbl[i]=_tbl[i+lz]-'0';
        dl-=lz;
}

liczba::liczba(const int _dl): dl(_dl)
{
        tbl=new char[dl];
}

liczba::~liczba()
{
        delete [] tbl;
}

void liczba::set(const char* _tbl)
{
        delete [] tbl;
        dl=strlen(_tbl);
        int i=0, lz=0;
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        tbl=new char[dl-lz];
        for(int i=0; i<dl-lz; i++)
                tbl[i]=_tbl[i+lz]-'0';
        dl-=lz;
}

void liczba::setpos(const char x, const int i)
{
        tbl[i]=x;
}

char liczba::getpos(const int i)const
{
        if(i<dl&&i>=0) return tbl[i];
        return 0;
}

char* liczba::get()const
{
        return tbl;
}

int liczba::getlen()const
{
        return dl;
}

void liczba::print()const
{
        for(int i=0; i<dl; i++)
                printf("%d", tbl[i]);
}
//---------------------------------------------------------------------------
char* suma(const liczba& a, const liczba& b)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci dluzszego czynnika
        char* c=new char[dlmax+2]; // rezerwacja pamieci na wynik z uwzgletnieniem znaku terminujacego
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';
//---------------------------------------------------------------------------------------
        char x=0, cr=0;
//-------------------petla sumowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)+b.getpos(b.getlen()-1-i)+cr;
                //--------obsluga przeniesienia--------
                if(x>9){
                        x-=10;
                        cr=1;}
                else cr=0;
                //-------------------------------------
                c[dlmax-i]=x+'0';}
//--------------------------------------------------------------------------------------
        c[0]=cr+'0'; // dopisanie ewentualnego przeniesienia
        return c;
}

char* roznica(const liczba& a, const liczba& b)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci najdluzszego czynnika
        char* c=new char[dlmax+1]; // rezerwacja pamieci na wynik
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax; i++)
                c[i]='0';
        c[dlmax]='\0';
//---------------------------------------------------------------------------------------
        signed char x=0, cr=0;
//-------------------petla odejmowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)-b.getpos(b.getlen()-1-i)-cr;
                //-------------------obsluga pozyczki------------------
                if(x<0){
                        x+=10;
                        cr=1;}
                else cr=0;
                //-----------------------------------------------------
                c[dlmax-1-i]=x+'0';}
        return c;
}
//------------------------funkcja treningowa, brak komentarzy-----------------------------
char* ilzcyfr(const liczba& a, const char& b)
{
        int dlmax=a.getlen();

        char* c=new char[dlmax+2];

        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';

        char x=0, cr=0;
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)*b+cr;
                if(x>9){
                        cr=x/10;
                        x=x%10;}
                else cr=0;
                c[dlmax-i]=x+'0';}
        c[0]=cr+'0';
        return c;
}
//----------------------------------------------------------------------------------------
char* iloczyn(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();

        char* c=new char[dla+dlb+2]; // wynik jest niedluzszy niz suma dlugosci obydwu cyfr
        for(int i=0; i<dla+dlb+2; i++)
                c[i]=0;
        c[dla+dlb+1]='\0';

        char* temp=new char[dla+dlb+1]; // zmienna pomocnicz przechowyjaca wynik mnozenia przez pojedyncza cyfre
        for(int i=0; i<dla+dlb; i++)
                temp[i]=0;

        char x=0, cr=0; // zmienne pomocnicze
//--------------------------------petla cyfr drugiego czynnika---------------------------
        for(int j=0; j<dlb; j++){
        //-----------------------petla cyfr pierwszego czynnika--------------------------
                for(int i=0; i<dla; i++){
                        x=a.getpos(a.getlen()-1-i)*b.getpos(b.getlen()-1-j)+cr;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                cr=x/10;
                                x=x%10;}
                        else cr=0;
                        //---------------------------------------------------------------
                        temp[dla+dlb-j-i-1]=x;}
                temp[dlb-1-j]=cr; // dopisanie ewentualnego przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
//-------------------------------petla sumowania wynikow mnozen przez kolejne cyfry------
                for(int k=0; k<dla+dlb; k++){
                        x=temp[dla+dlb-1-k]+c[dla+dlb-k]+cr;
                        temp[dla+dlb-1-k]=0;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                x-=10;
                                cr=1;}
                        else cr=0;
                        //---------------------------------------------------------------
                        c[dla+dlb-k]=x;}
                c[0]=cr; // dopisanie przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
                }
//-------------------------------petla konwersji wartosci wyniku na string---------------
        for(int i=0; i<dla+dlb+1; i++)
                c[i]+='0';
//---------------------------------------------------------------------------------------
        delete [] temp; // usuniecie zmiennej pomocniczej
        return c;
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
        char* wpis=new char[255];
        char* wynik;
        liczba c;

        //string wpis;

        printf("a=");
        scanf("%s", wpis);
        liczba a(wpis);
        printf("b=");
        scanf("%s", wpis);
        liczba b(wpis);
        delete [] wpis;

                printf("\n");
        a.print();
        printf(" + ");
        b.print();
        printf(" = ");
        wynik=suma(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
        a.print();
        printf(" - ");
        b.print();
        printf(" = ");
        wynik=roznica(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
        a.print();
        printf(" * ");
        b.print();
        printf(" = ");
        wynik=iloczyn(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");

        system("pause");

        return 0;
}
//---------------------------------------------------------------------------
  • #2
    Xitami
    Level 29  
    Wg pewnej książki klasyczne mnożenie dwóch liczb po milionie cyfr na maszynie o dzielności 10MIPS (mało ale niech tam) zajmie 24 godziny! Istnieją inne algorytmy, wg. tego samego źródła algorytm Karatsuby 10 minut, FFT 10 sekund (doba to 86 400 sekund) na tej maszynie pomnożenie miliarda cyfr przez miliard zajmie tylko 2700 lat (FFT 3 miesiące)
  • #3
    tzok
    Moderator of Cars  
    Mnożenie na pewno nie jest optymalne... ale działa, nadal brakuje mi natomiast dzielenia. Oczywiście mógłbym wykorzystać jakiś gotowy kod, problem w tym że chciałbym go przynajmniej rozumieć.
  • #4
    shg
    Level 35  
    Przypominam, że komputery liczą w systemie binarnym!
    Implementacja tego była by tylko trochę trudniejsza (chyba, że ktoś myśli jak maszyna, do czego się konsekwentnie zbliżam :D ) niż systemu dziesiętnego, a wydajność wielokrotnie wyższa.
    Można by wtedy w prosty sposób zrobić mnożenie i dzielenie (binarne jest prostsze!), gdzieś na elektrodzi był chyba temat o dzieleniu, a jakby co to tu można coś znaleźć:
    http://www.8052.com/
    Jest tam gdzieś opisany sposób dzielenia binarnego, poza tym dość sporo takich procedur jest w książce "Hacker's delight", -> priv.

    Problemem była by tylko konwersja ascii<->liczba, trochę długo by to trwało :D
  • Helpful post
    #5
    eihs
    Level 13  
    shg wrote:
    Problemem była by tylko konwersja ascii<->liczba, trochę długo by to trwało :D


    Wcale nie bylaby takim problemem :)

    zalozmy ze mamy liczbe 357, chcemy ja rozpisac na jedynki i zera. robimy sobie zatem kolumny, w kazdej kolumnie dokladnie jedna cyferka zapisana w czterech bitach


    0011 || 0101 || 0111, sa ladne trzy kolumny, teraz przesuwamy o jeden w prawo
    0001 || 1010 || 1011 -> 1 te wychodzaca cyferke zapamietujemy, jesli po przesunieciu, w ktorejs kolumnie jest wiecej niz 7 to odejmujemy od tego 3 i petlimy dalej (przesuniecie, ewentualne odejmowanie, az do zera)


    a wiec od poczatku

    Code: text Expand Select all Copy to clipboard
    
   3    5    7 
---- ---- ---- 
0011 0101 0111 
0001 1010 1011 -> 1 po przesunieciu 
    -0011-0011 
0001 0111 1000      po odejmowaniu 

0000 1011 1100 -> 0 po przesunieciu 
    -0011-0011 
0000 1000 1001      po odejmowaniu 

0000 0100 0100 -> 1 po przesunieciu 

0000 0010 0010 -> 0 po przesunieciu 

0000 0001 0001 -> 0 po przesunieciu 

0000 0000 1000 -> 1 po przesunieciu 
         -0011 
0000 0000 0101      po odejmowaniu 

0000 0000 0010 -> 1 po przesunieciu 

0000 0000 0001 -> 0 po przesunieciu 

0000 0000 0000 -> 1 po przesunieciu (zero wiec koniec) 

teraz czytamy od konca te bity co nam wychodzily z przesuniecia, czyli 101100101b = 357 


    mam nadzieje ze latwo zrozumiec :)

    greets
  • #6
    shg
    Level 35  
    Tak, faktycznie, już problemu nie ma, wczoraj wydumałem algorytm szybkiej konwersji między systemami liczb, wystarczy na dziesiętny zamienić, a potem na ASCII (albo odwrotnie), przy czym można to dość mocno zoptymalizować :D dla tego jednego konkretnego zadania
    https://www.elektroda.pl/rtvforum/viewtopic.php?p=1302839
  • #7
    tzok
    Moderator of Cars  
    Jak na razie dzielenie jest zrealizowane na... odejmowaniu ale jest baaaardzo nieefektywne jeśli różnica między liczbami jest duża, można je znacząco usprawnić mnożąc dzielnik przez 10^n tak aby był o jeden rząd wielkości mniejszy od dzielnej i dopiero odejmować.

    ***

    No... wreszcie udało mi się (z pomocą kolegów z grupy lab.) coś wykombinować:
    Code: text Expand Select all Copy to clipboard
    //---------------------------------------------------------------------------

#include <stdlib>
#include <string>
#include <stdio>

//---------------------------------------------------------------------------
class liczba
{
private:
        char* tbl;
        int dl;
public:
        liczba(const char*);
        liczba(const int=0);
        ~liczba();
        void set(const char*);
        void setpos(const char, const int);
        char getpos(const int)const;
        char* get()const;
        int getlen()const;
        void print()const;

};

liczba::liczba(const char* _tbl)
{
        dl=strlen(_tbl);
        int i=0, lz=0;
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        tbl=new char[dl-lz];
        for(int i=0; i<dl-lz; i++)
                tbl[i]=_tbl[i+lz]-'0';
        dl-=lz;
}

liczba::liczba(const int _dl): dl(_dl)
{
        tbl=new char[dl];
}

liczba::~liczba()
{
        delete [] tbl;
}

void liczba::set(const char* _tbl)
{
        delete [] tbl;
        dl=strlen(_tbl);
        int i=0, lz=0;
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        tbl=new char[dl-lz];
        for(int i=0; i<dl-lz; i++)
                tbl[i]=_tbl[i+lz]-'0';
        dl-=lz;
}

void liczba::setpos(const char x, const int i)
{
        tbl[i]=x;
}

char liczba::getpos(const int i)const
{
        if(i<dl&&i>=0) return tbl[i];
        return 0;
}

char* liczba::get()const
{
        return tbl;
}

int liczba::getlen()const
{
        return dl;
}

void liczba::print()const
{
        for(int i=0; i<dl; i++)
                printf("%d", tbl[i]);
}
//---------------------------------------------------------------------------
char* suma(const liczba& a, const liczba& b)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci dluzszego czynnika
        char* c=new char[dlmax+2]; // rezerwacja pamieci na wynik z uwzgletnieniem znaku terminujacego
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';
//---------------------------------------------------------------------------------------
        char x=0, cr=0;
//-------------------petla sumowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)+b.getpos(b.getlen()-1-i)+cr;
                //--------obsluga przeniesienia--------
                if(x>9){
                        x-=10;
                        cr=1;}
                else cr=0;
                //-------------------------------------
                c[dlmax-i]=x+'0';}
//--------------------------------------------------------------------------------------
        c[0]=cr+'0'; // dopisanie ewentualnego przeniesienia
        return c;
}

char* roznica(const liczba& a, const liczba& b, int bsr=0)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci najdluzszego czynnika
        char* c=new char[dlmax+1]; // rezerwacja pamieci na wynik
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax; i++)
                c[i]='0';
        c[dlmax]='\0';
//---------------------------------------------------------------------------------------
        signed char x=0, cr=0;
//-------------------petla odejmowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)-b.getpos(b.getlen()-1-i+bsr)-cr;
                //-------------------obsluga pozyczki------------------
                if(x<0){
                        x+=10;
                        cr=1;}
                else cr=0;
                //-----------------------------------------------------
                c[dlmax-1-i]=x+'0';}
        return c;
}
//------------------------funkcja treningowa, brak komentarzy-----------------------------
char* ilzcyfr(const liczba& a, const char& b)
{
        int dlmax=a.getlen();

        char* c=new char[dlmax+2];

        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';

        char x=0, cr=0;
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)*b+cr;
                if(x>9){
                        cr=x/10;
                        x=x%10;}
                else cr=0;
                c[dlmax-i]=x+'0';}
        c[0]=cr+'0';
        return c;
}
//----------------------------------------------------------------------------------------
char* iloczyn(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();

        char* c=new char[dla+dlb+2]; // wynik jest niedluzszy niz suma dlugosci obydwu cyfr
        for(int i=0; i<dla+dlb+2; i++)
                c[i]=0;
        c[dla+dlb+1]='\0';

        char* temp=new char[dla+dlb+1]; // zmienna pomocnicza przechowyjaca wynik mnozenia przez pojedyncza cyfre
        for(int i=0; i<dla+dlb; i++)
                temp[i]=0;

        char x=0, cr=0; // zmienne pomocnicze
//--------------------------------petla cyfr drugiego czynnika---------------------------
        for(int j=0; j<dlb; j++){
        //-----------------------petla cyfr pierwszego czynnika--------------------------
                for(int i=0; i<dla; i++){
                        x=a.getpos(a.getlen()-1-i)*b.getpos(b.getlen()-1-j)+cr;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                cr=x/10;
                                x=x%10;}
                        else cr=0;
                        //---------------------------------------------------------------
                        temp[dla+dlb-j-i-1]=x;}
                temp[dlb-1-j]=cr; // dopisanie ewentualnego przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
//-------------------------------petla sumowania wynikow mnozen przez kolejne cyfry------
                for(int k=0; k<dla+dlb; k++){
                        x=temp[dla+dlb-1-k]+c[dla+dlb-k]+cr;
                        temp[dla+dlb-1-k]=0;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                x-=10;
                                cr=1;}
                        else cr=0;
                        //---------------------------------------------------------------
                        c[dla+dlb-k]=x;}
                c[0]=cr; // dopisanie przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
                }
//-------------------------------petla konwersji wartosci wyniku na string---------------
        for(int i=0; i<dla+dlb+1; i++)
                c[i]+='0';
//---------------------------------------------------------------------------------------
        delete [] temp; // usuniecie zmiennej pomocniczej
        return c;
}
//---------------------------------------------------------------------------
int compare (const liczba& a, const liczba& b, int bsr=0)
{       //zwraca 1 gdy a>=b*10^bsr  lub 0 gdy a<b*10^bsr
        int dla = a.getlen();
        int dlb = b.getlen()+bsr;
        if(dla>dlb) return 1;
        else if(dla<dlb) return 0;
        else{
                for(int i=0; i<dla; i++){
                        if(a.getpos(i)==b.getpos(i)) continue;
                        if(a.getpos(i)>b.getpos(i))return 1;
                        else return 0;
                }
        }
        return 1;
}
//---------------------------------------------------------------------------
char* iloraz(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();
        int off=dla-dlb; // roznica rzedow liczb
        char x; // cyfra wyniku
        liczba temp; // zmienna pomocnicza do odejmowania
        char* tempa=suma(a, "0"); // Przypisanie stringa odpowiadającego liczbie a do wskaźnika
        temp.set(tempa); // skopiowanie liczby a do zmiennej pomocniczej temp
        delete [] tempa; // zwolnienie pamięci zajmowanej przez string
        char* rozn;
        if(compare(temp, b, off)==0) off--; // jesli po wyrownaniu rzedow dzielnik jest wiekszy od dzielnej zmniejsz jego rzad o jeden
        char* c=new char[off+1]; // tablica wynikowa
        for(int i=0; i<off+1; i++)
                c[i]=0; // inicjalizacja tablicy wynikowej
        int dlc=off;
        while(off>=0){ // zaczynamy od najbardziej znaczacej cyfry wyniku
                x=0; // zerowanie zmiennej przed obliczeniem kolejnej cyfry wyniku
                while(compare(temp, b, off)){ // odejmujemy od dzielnej dzielnik pomnozony przez 10^off dopuki wynik nie będzie mniejszy od dzielnika
                        rozn=roznica(temp, b, off); // to jest konieczne aby zachowac wskaznik do stringa ktory tworzy ta funkcja
                        temp.set(rozn);
                        delete [] rozn; // ... aby po jego zczytaniu moc zwolnic zajmowana przezen pamiec
                        x++; // zliczamy odjecia
                        }
                c[dlc-off]=x+'0'; // ... i zapisujemy je jako kolejne cyfry wyniku
                off--; // przechodzimy do kolejnej cyfry wyniku
        }
        c[dlc-off]=0; // terminujemy wynikowy ciąg
        return(c);
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
        char* wpis=new char[255];
        char* wynik;
        liczba c;

        printf("a=");
        scanf("%s", wpis);
        liczba a(wpis);
        printf("b=");
        scanf("%s", wpis);
        liczba b(wpis);
        delete [] wpis;
//for(int z=0; z<10000; z++){
                printf("\n");
        a.print();
        printf(" + ");
        b.print();
        printf(" = ");
        wynik=suma(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
        a.print();
        printf(" - ");
        b.print();
        printf(" = ");
        wynik=roznica(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
        a.print();
        printf(" * ");
        b.print();
        printf(" = ");
        wynik=iloczyn(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
        a.print();
        printf(" / ");
        b.print();
        printf(" = ");
        wynik=iloraz(a, b);
        c.set(wynik);
        delete [] wynik;
        c.print();
                printf("\n");
//}
        system("pause");

        return 0;
}
//---------------------------------------------------------------------------
  • #8
    tzok
    Moderator of Cars  
    Update funkcji main():
    Code: text Expand Select all Copy to clipboard
    int main(int argc, char* argv[])
{
        char* wpis=new char[255];
        char* ops;
        char op;
        int dalej=1;
        liczba c;
        printf("a=");
        scanf("%s", wpis);
        do{
                liczba a(wpis);
                printf("operacja [+, -, *, /, =]: ");
                scanf("%1s", &op);
                if(op=='='){
                        printf("\nwynik=");
                        a.print();
			delete [] wpis;
                        break;}
                printf("b=");
                scanf("%s", wpis);
                liczba b(wpis);
                delete [] wpis;
                switch(op){
                        case '+': wpis=suma(a, b); break;
                        case '-': wpis=roznica(a, b); break;
                        case '*': wpis=iloczyn(a, b); break;
                        case '/': wpis=iloraz(a, b); break;}
                a.set(wpis);
                printf("\na=");
                a.print();
                printf("\n");
                }while(dalej);
        printf("\n");
        system("pause");
        return 0;
}

    Okazuje się, że kod:
    scanf("%s", wpis);
    scanf("%c", &op);
    Nie zadziała, bo drugi scanf zczyta entera potwierdzającego pierwszy scanf.
  • #9
    Grzesiek1711
    Level 16  
    coś ta procedurka nie do końca działa - właśnie dzielenie wywala błąd bo mi np 10/20=-48 czyli coś jeszcze nie do końca jest OK - ale i tak jestem pod wielkim wrażeniem normalnie RE5PECT...(nie sądziłem że to będzie tak szybko liczyło)
  • #10
    tzok
    Moderator of Cars  
    tzok wrote:
    *reprezentacja liczb jest stałoprzecinkowa bez znaku

    Tylko ten termin "stałoprzecinkowa" mi z roztargnienia wyszedł - reprezentowane są tylko liczby całkowite.
    ***
    Faktycznie - jest tam błąd z alokacją pamięci, tylko gdzie?
    Code: text Expand Select all Copy to clipboard
    int main(int argc, char* argv[])
{
        char* wpis=new char[32];
        char* w=0;
        char* ops;
        char op;
        int dalej=1;
        liczba c;
        printf("Uzycie:\n");
        printf("<liczba>[Enter]<operator><liczba>[Enter]<operator><liczba>[Enter]...[=][Enter]\n: ");
        scanf("%s", wpis);
        liczba a(wpis);
        do{
                printf(": ");
                scanf(" %c", &op);
                if(op=='='){
                        printf("\nwynik=");
                        a.print();
                        delete [] wpis;
                        break;}
                scanf("%s", wpis);
                liczba b(wpis);
                switch(op){
                        case '+': w=suma(a, b); break;
                        case '-': w=roznica(a, b); break;
                        case '*': w=iloczyn(a, b); break;
                        case '/': w=iloraz(a, b); break;}
                a.set(w);
                delete [] w;
                printf("= ");
                a.print();
                printf("\n");
                }while(dalej);
        printf("\n\n");
        system("pause");
        return 0;
}

    ****
    ok, już znalazłem błąd:
    Code: text Expand Select all Copy to clipboard
    char* iloraz(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();
        int off=dla-dlb; // roznica rzedow liczb
        char x; // cyfra wyniku
        liczba temp; // zmienna pomocnicza do odejmowania
        char* tempa=suma(a, "0"); // Przypisanie stringa odpowiadającego liczbie a do wskaźnika
        temp.set(tempa); // skopiowanie liczby a do zmiennej pomocniczej temp
        delete [] tempa; // zwolnienie pamięci zajmowanej przez string
        char* rozn;
        if(compare(temp, b, off)==0) off--; // jesli po wyrownaniu rzedow dzielnik jest wiekszy od dzielnej zmniejsz jego rzad o jeden
        if (off<0) off=0;
        char* c=new char[off+2]; // tablica wynikowa
        for(int i=0; i<off+2; i++)
                c[i]='0'; // inicjalizacja tablicy wynikowej
        c[off+1]=0; // terminujemy wynikowy ciąg
        int dlc=off;
        while(off>=0){ // zaczynamy od najbardziej znaczacej cyfry wyniku
                x=0; // zerowanie zmiennej przed obliczeniem kolejnej cyfry wyniku
                while(compare(temp, b, off)){ // odejmujemy od dzielnej dzielnik pomnozony przez 10^off dopuki wynik nie będzie mniejszy od dzielnika
                        rozn=roznica(temp, b, off); // to jest konieczne aby zachowac wskaznik do stringa ktory tworzy ta funkcja
                        temp.set(rozn);
                        delete [] rozn; // ... aby po jego zczytaniu moc zwolnic zajmowana przezen pamiec
                        x++; // zliczamy odjecia
                        }
                c[dlc-off]=x+'0'; // ... i zapisujemy je jako kolejne cyfry wyniku
                off--; // przechodzimy do kolejnej cyfry wyniku
        }

        return(c);
}
  • #11
    tzok
    Moderator of Cars  
    Dzieci, nie róbcie tego w domu (kod jest paskudny ale działa). Oto wersja finalna, nadal tylko liczby całkowite ale ze znakiem:
    Code: text Expand Select all Copy to clipboard
    //---------------------------------------------------------------------------

#include <stdlib>
#include <string>
#include <stdio>

//---------------------------------------------------------------------------
class liczba
{
private:
        char* tbl;
        int dl;
        signed char sgn;
public:
        liczba(const char*);
        liczba(const int=0);
        ~liczba();
        int set(const char*);
        void setpos(const char, const int);
        char getpos(const int)const;
        char* get()const;
        int getlen()const;
        void print()const;
        signed char getsgn()const;
        void setsgn(const signed char);

};

liczba::liczba(const char* _tbl)
{
        sgn=1;

        dl=strlen(_tbl);
        int i=0, lz=0;
        if(_tbl[0]=='-') {sgn=-1; lz++; i++;}
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        dl=lz;
        i=0;
        while(_tbl[i+lz]-'0'>=0&&_tbl[i+lz]-'0'<=9) {dl++; i++;}
        tbl=new char[dl-lz];
        for(int i=0; i<dl-lz; i++)
                //if(_tbl[i+lz]-'0'>=0&&_tbl[i+lz]-'0'<=9) tbl[i]=_tbl[i+lz]-'0';
                //else tbl[i]=0;
                tbl[i]=_tbl[i+lz]-'0';
        dl-=lz;
}

liczba::liczba(const int _dl): dl(_dl)
{
        sgn=1;
        tbl=new char[dl];
}

liczba::~liczba()
{
        delete [] tbl;
}

int liczba::set(const char* _tbl)
{
        sgn=1;
        delete [] tbl;
        dl=strlen(_tbl);
        int ln;
        int i=0, lz=0;
        if(_tbl[0]=='-') {sgn=-1; lz++; i++;}
        while(_tbl[i]=='0'&&i<dl) {lz++; i++;};
        if((dl-lz)==0) lz--;
        ln=lz;
        i=0;
        while(_tbl[i+lz]-'0'>=0&&_tbl[i+lz]-'0'<=9) {ln++; i++;}
        //if(ln==lz)ln++;
        if (dl==ln){
                tbl=new char[dl-lz];
                for(int i=0; i<dl-lz; i++)
                        //if(_tbl[i+lz]-'0'>=0&&_tbl[i+lz]-'0'<=9) tbl[i]=_tbl[i+lz]-'0';
                        //else tbl[i]=0;
                        tbl[i]=_tbl[i+lz]-'0';
                dl-=lz;
                return 0;}
        else {
                dl=ln;
                tbl=new char[dl-lz];
                for(int i=0; i<dl-lz; i++)
                        //if(_tbl[i+lz]-'0'>=0&&_tbl[i+lz]-'0'<=9) tbl[i]=_tbl[i+lz]-'0';
                        //else tbl[i]=0;
                        tbl[i]=_tbl[i+lz]-'0';
                dl-=lz;
                return 1;}
}

void liczba::setpos(const char x, const int i)
{
        tbl[i]=x;
}

char liczba::getpos(const int i)const
{
        if(i<dl&&i>=0) return tbl[i];
        return 0;
}

char* liczba::get()const
{
        return tbl;
}

int liczba::getlen()const
{
        return dl;
}

void liczba::print()const
{
        if(sgn==-1) printf("-");
        for(int i=0; i<dl; i++)
                printf("%d", tbl[i]);
}
signed char liczba::getsgn()const
{
        return sgn;
}
void liczba::setsgn(const signed char newSgn)
{
        sgn=newSgn;
}
//---------------------------------------------------------------------------
char* equal(const liczba& a)
{
        int dlmax=a.getlen();
        int so=0;
        if(a.getsgn()==-1)so=1;
        char* c=new char[dlmax+so+1];
        if(a.getsgn()==-1)c[0]='-';
        for(int i=0; i<dlmax+1; i++)
                c[i+so]=a.getpos(i)+'0';
        c[dlmax+so]='\0';
        return c;
}
//---------------------------------------------------------------------------
char* suma_(const liczba& a, const liczba& b)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci dluzszego czynnika
        char* c=new char[dlmax+2]; // rezerwacja pamieci na wynik z uwzgletnieniem znaku terminujacego
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';
//---------------------------------------------------------------------------------------
        char x=0, cr=0;
//-------------------petla sumowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)+b.getpos(b.getlen()-1-i)+cr;
                //--------obsluga przeniesienia--------
                if(x>9){
                        x-=10;
                        cr=1;}
                else cr=0;
                //-------------------------------------
                c[dlmax-i]=x+'0';}
//--------------------------------------------------------------------------------------
        c[0]=cr+'0'; // dopisanie ewentualnego przeniesienia
        return c;
}

char* roznica_(const liczba& a, const liczba& b, int bsr=0)
{
        int dlmax;
        if(a.getlen()>=b.getlen()) dlmax=a.getlen();
        else dlmax=b.getlen(); // ustalenie dlugosci najdluzszego czynnika
        char* c=new char[dlmax+1]; // rezerwacja pamieci na wynik
//-------------------zerowanie i terminowanie zmiennej, bedzie przekazana jako c-string--
        for(int i=0; i<dlmax; i++)
                c[i]='0';
        c[dlmax]='\0';
//---------------------------------------------------------------------------------------
        signed char x=0, cr=0;
//-------------------petla odejmowania cyfr------------------------------------------------
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)-b.getpos(b.getlen()-1-i+bsr)-cr;
                //-------------------obsluga pozyczki------------------
                if(x<0){
                        x+=10;
                        cr=1;}
                else cr=0;
                //-----------------------------------------------------
                c[dlmax-1-i]=x+'0';}
        return c;
}
//------------------------funkcja treningowa, brak komentarzy-----------------------------
char* ilzcyfr(const liczba& a, const char& b)
{
        int dlmax=a.getlen();

        char* c=new char[dlmax+2];

        for(int i=0; i<dlmax+1; i++)
                c[i]='0';
        c[dlmax+1]='\0';

        char x=0, cr=0;
        for(int i=0; i<dlmax; i++){
                x=a.getpos(a.getlen()-1-i)*b+cr;
                if(x>9){
                        cr=x/10;
                        x=x%10;}
                else cr=0;
                c[dlmax-i]=x+'0';}
        c[0]=cr+'0';
        return c;
}
//----------------------------------------------------------------------------------------
char* iloczyn_(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();

        char* c=new char[dla+dlb+2]; // wynik jest niedluzszy niz suma dlugosci obydwu cyfr
        for(int i=0; i<dla+dlb+2; i++)
                c[i]=0;
        c[dla+dlb+1]='\0';

        char* temp=new char[dla+dlb+1]; // zmienna pomocnicza przechowyjaca wynik mnozenia przez pojedyncza cyfre
        for(int i=0; i<dla+dlb; i++)
                temp[i]=0;

        char x=0, cr=0; // zmienne pomocnicze
//--------------------------------petla cyfr drugiego czynnika---------------------------
        for(int j=0; j<dlb; j++){
        //-----------------------petla cyfr pierwszego czynnika--------------------------
                for(int i=0; i<dla; i++){
                        x=a.getpos(a.getlen()-1-i)*b.getpos(b.getlen()-1-j)+cr;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                cr=x/10;
                                x=x%10;}
                        else cr=0;
                        //---------------------------------------------------------------
                        temp[dla+dlb-j-i-1]=x;}
                temp[dlb-1-j]=cr; // dopisanie ewentualnego przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
//-------------------------------petla sumowania wynikow mnozen przez kolejne cyfry------
                for(int k=0; k<dla+dlb; k++){
                        x=temp[dla+dlb-1-k]+c[dla+dlb-k]+cr;
                        temp[dla+dlb-1-k]=0;
                        //-------obsluga przeniesienia-----------------------------------
                        if(x>9){
                                x-=10;
                                cr=1;}
                        else cr=0;
                        //---------------------------------------------------------------
                        c[dla+dlb-k]=x;}
                c[0]=cr; // dopisanie przeniesienia
                x=0, cr=0; // zerowanie wykorzystanych zmiennych pomocniczych
                }
//-------------------------------petla konwersji wartosci wyniku na string---------------
        for(int i=0; i<dla+dlb+1; i++)
                c[i]+='0';
//---------------------------------------------------------------------------------------
        delete [] temp; // usuniecie zmiennej pomocniczej
        return c;
}
//---------------------------------------------------------------------------
int compare (const liczba& a, const liczba& b, int bsr=0)
{       //zwraca 1 gdy a>=b*10^bsr  lub 0 gdy a<b*10^bsr
        int dla = a.getlen();
        int dlb = b.getlen()+bsr;
        if(dla>dlb) return 1;
        else if(dla<dlb) return 0;
        else{
                for(int i=0; i<dla; i++){
                        if(a.getpos(i)==b.getpos(i)) continue;
                        if(a.getpos(i)>b.getpos(i))return 1;
                        else return 0;
                }
        }
        return 1;
}
//---------------------------------------------------------------------------
char* iloraz_(const liczba& a, const liczba& b)
{
        int dla=a.getlen();
        int dlb=b.getlen();
        int off=dla-dlb; // roznica rzedow liczb
        char x; // cyfra wyniku
        liczba temp; // zmienna pomocnicza do odejmowania
        char* tempa=equal(a); // Przypisanie stringa odpowiadającego liczbie a do wskaźnika
        temp.set(tempa); // skopiowanie liczby a do zmiennej pomocniczej temp
        delete [] tempa; // zwolnienie pamięci zajmowanej przez string
        char* rozn;
        if(compare(temp, b, off)==0) off--; // jesli po wyrownaniu rzedow dzielnik jest wiekszy od dzielnej zmniejsz jego rzad o jeden
        if (off<0) off=0; // jesli dzielnik jest wiekszy do dzielnej ustaw przesuniecie na 0
        char* c=new char[off+2]; // tablica wynikowa
        for(int i=0; i<off+2; i++)
                c[i]='0'; // inicjalizacja tablicy wynikowej
        c[off+1]=0; // terminujemy wynikowy ciąg
        int dlc=off;
        while(off>=0){ // zaczynamy od najbardziej znaczacej cyfry wyniku
                x=0; // zerowanie zmiennej przed obliczeniem kolejnej cyfry wyniku
                while(compare(temp, b, off)){ // odejmujemy od dzielnej dzielnik pomnozony przez 10^off dopuki wynik nie będzie mniejszy od dzielnika
                        rozn=roznica_(temp, b, off); // to jest konieczne aby zachowac wskaznik do stringa ktory tworzy ta funkcja
                        temp.set(rozn);
                        delete [] rozn; // ... aby po jego zczytaniu moc zwolnic zajmowana przezen pamiec
                        x++; // zliczamy odjecia
                        }
                c[dlc-off]=x+'0'; // ... i zapisujemy je jako kolejne cyfry wyniku
                off--; // przechodzimy do kolejnej cyfry wyniku
        }

        return(c);
}
char* iloraz(const liczba& a, const liczba& b)
{
        char* wynik=iloraz_(a, b);
        if(a.getsgn()==b.getsgn())return wynik;
        else {
                int dl=strlen(wynik);
                char* c=new char[dl+2];
                c[0]='-';
                for(int i=0; i<dl+1; i++)
                        c[i+1]=wynik[i];
                c[dl+1]=0;
                delete [] wynik;
                return c;}
}
char* iloczyn(const liczba& a, const liczba& b)
{
        char* wynik=iloczyn_(a, b);
        if(a.getsgn()==b.getsgn())return wynik;
        else {
                int dl=strlen(wynik);
                char* c=new char[dl+2];
                c[0]='-';
                for(int i=0; i<dl+1; i++)
                        c[i+1]=wynik[i];
                c[dl+1]=0;
                delete [] wynik;
                return c;}
}
char* suma(const liczba& a, const liczba& b)
{
        bool minus=0;
        char* wynik=0;
        if((a.getsgn()==-1)&&(b.getsgn()==1))
                if(compare(a, b)){
                        wynik=roznica_(a, b);
                        minus=1;}
                else{
                        wynik=roznica_(b, a);
                        minus=0;}
        else if((a.getsgn()==1)&&(b.getsgn()==-1))
                if(compare(a, b)){
                        wynik=roznica_(a, b);
                        minus=0;}
                else{
                        wynik=roznica_(b, a);
                        minus=1;}
        else if((a.getsgn()==-1)&&(b.getsgn()==-1))
                if(compare(a, b)){
                        wynik=suma_(a, b);
                        minus=1;}
                else{
                        wynik=suma_(a, b);
                        minus=1;}
        else
                if(compare(a, b)){
                        wynik=suma_(a, b);
                        minus=0;}
                else{
                        wynik=suma_(a, b);
                        minus=0;}

        if(minus){
                int dl=strlen(wynik);
                char* c=new char[dl+2];
                c[0]='-';
                for(int i=0; i<dl+1; i++)
                        c[i+1]=wynik[i];
                c[dl+1]=0;
                delete [] wynik;
                return c;}
        else return wynik;
}
char* roznica(const liczba& a, const liczba& b)
{
        bool minus=0;
        char* wynik=0;
        if((a.getsgn()==-1)&&(b.getsgn()==1))
                if(compare(a, b)){
                        wynik=suma_(a, b);
                        minus=1;}
                else{
                        wynik=suma_(a, b);
                        minus=1;}
        else if((a.getsgn()==1)&&(b.getsgn()==-1))
                if(compare(a, b)){
                        wynik=suma_(a, b);
                        minus=0;}
                else{
                        wynik=suma_(b, a);
                        minus=0;}
        else if((a.getsgn()==-1)&&(b.getsgn()==-1))
                if(compare(a, b)){
                        wynik=roznica_(a, b);
                        minus=1;}
                else{
                        wynik=roznica_(b, a);
                        minus=0;}
        else
                if(compare(a, b)){
                        wynik=roznica_(a, b);
                        minus=0;}
                else{
                        wynik=roznica_(b, a);
                        minus=1;}

        if(minus){
                int dl=strlen(wynik);
                char* c=new char[dl+2];
                c[0]='-';
                for(int i=0; i<dl+1; i++)
                        c[i+1]=wynik[i];
                c[dl+1]=0;
                delete [] wynik;
                return c;}
        else return wynik;
}


//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
        char* wpis=new char[2000000];
        char* w=0;
        char* ops;
        char op;
        int dalej=1;
        liczba c;
        printf("Uzycie:\n");
        printf("<liczba>[Enter]<operator><liczba>[Enter]<operator><liczba>[Enter]...[=][Enter]\n: ");
        liczba a;
        scanf("%s", wpis);
        while(a.set(wpis)){
                printf(" NIE LICZBA!!!\n: ");
                scanf("%s", wpis);}
        do{
                printf(": ");
                scanf(" %c", &op);
                if(op=='='){
                        printf("\nwynik=");
                        a.print();
                        delete [] wpis;
                        break;}
                scanf("%s", wpis);
                liczba b;
                if(b.set(wpis)) {printf(" NIE LICZBA!!!\n"); continue;}
                switch(op){
                        case '+': w=suma(a, b); break;
                        case '-': w=roznica(a, b); break;
                        case '*': w=iloczyn(a, b); break;
                        case '/': w=iloraz(a, b); break;
                        default: printf("ZLY OPERATOR!!!\n"); w=equal(a);}
                a.set(w);
                delete [] w;
                printf("= ");
                a.print();
                printf("\n");
                }while(dalej);
        printf("\n\n");
        system("pause");
        return 0;
}
//---------------------------------------------------------------------------
Reply | New topic