Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: thư viện xử lí số nguyên lớn?

  1. #1
    Ngày gia nhập
    03 2008
    Bài viết
    2

    Arrow thư viện xử lí số nguyên lớn?

    Có bạn nào biết thư viện hay gói phần mềm nào làm việc với số nguyên lớn kích thước vài trăm bit trở lên làm ơn chỉ mình với.Cho mình hỏi thêm là khái niệm world align là gì được không?

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    440

    Trích dẫn Nguyên bản được gửi bởi ggo Xem bài viết
    Có bạn nào biết thư viện hay gói phần mềm nào làm việc với số nguyên lớn kích thước vài trăm bit trở lên làm ơn chỉ mình với.Cho mình hỏi thêm là khái niệm world align là gì được không?
    http://en.wikipedia.org/wiki/Arbitra...ion_arithmetic

    World align là việc chứa dữ liệu vào bộ nhớ RAM bắt đầu tại địa chỉ chia hết cho độ dài của thế giới.

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    2

    Cảm ơn bạn.Mà bạn có biết thư viện(hay gói phần mềm nào xử lí số nguyên lớn không vậy chỉ mình với!

  4. #4
    Ngày gia nhập
    03 2008
    Bài viết
    1

    cái đó tự viết ra cũng được bác ạ, số đến cả nghìn chữ số cũng làm được!

  5. #5
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

  6. #6
    Ngày gia nhập
    01 2008
    Bài viết
    6

    Mặc định thư viện xử lí số nguyên lớn?

    Thư viện số nguyên lớn - Tình được giai thừa số nguyên lớn (100. 000!) - bignum digits[] sign lastdigits
    Đây là bài mình tham khảo :
    Các bạn hãy vào tham khảo nhé !
    http://www.cs.sunysb.edu/~skiena/392/programs/bignum.c


    HỌC LẬP TRÌNH LÀ PHẢI BIẾT COPY & PASTE

    Đây là thành quả của mình khi copy & paste và có code thêm :
    Note :
    PHP Code:
    * ) Bạn nào biết làm rồi thì có thể bỏ qua phần nàyBạn nào chưa biết thì chú ý vào nhé.
     - 
    Mình dùng devcpp 4.9.9.2 để code.
     - 
    Bạn hãy copy file bignum1.h và bignum2.h vào thư mục cài devcpp nhéGiả sử mình cài devcpp ở ổ C thì mình sẽ copy vào C:/Dev-Cpp/include
    Ở đây mình sẽ làm theo 2 cơ số 
      + ) 
    cơ số 10 (bignum1.h)
      + ) 
    cơ số 1 tỷ 1000.000.000)
      
    Mình không làm được hệ cơ số lũy thừa 2cái này dùng phép dịch bit chạy rất nhanh). Mình làm theo cơ số lũy thừa của 10 vì cái này dễ hơn.
    Thư viện cơ số 1 tỷ (1000.000.000có thể tính hơn được 100.000 trong thời gian vài phút mình đã thử cái này tùy cấu hình máynếu là máy dua 2 core thì chỉ mấy khoảng 2 3phútMáy yếu hơn thì chậm hơn của mình celeron 3.06 ram 1G thì khoảng gần 3 phút :nhớ mở file output b12.out bằng notepad nhớ không có là đơ luôn devcpp đấyKết quả của 100.000 là 456.590 chữ số :D)
    Chú ý khi dùng cơ số 1 tỷ (1000. 000. 000khi muốn chạy bình thường thì bạn chỉnh MAXDIGITS xuống nhé.(để 10000 cũng được mình hay test như thế). 
    File bignum1.h
    PHP Code:
    // file bignum1.h
    #include <iostream>
    #include <excpt.h>   // exception 

    using namespace std;

    #define MAXDIGITS 10000
    #define PLUS     +1
    #define MINUS    -1
    #define COSO     10

    class bignum {
      private :      
        
    int  digits[MAXDIGITS];   // Array int 
        
    int  sign;                // Sign bignum   
        
    int  lastdigits;          // Length bignum 
      
      
    public :
        
    // function constructor
        
    bignum() {
             
    memset (this->digits0MAXDIGITS sizeof (this->digits[0]));    
        }

        
    // function operator >> (input)
        
    friend istreamoperator >> (istreamcinbignuma) {
             
    string line;    // string bignum
             
    getline(cinline); 
             
    line;
             return 
    cin;  
        }
        
        
    // function operator << (output) 
        
    friend ostreamoperator << (ostreamcout, const bignuma) {
            
    int i;          // counter
            
            
    if (a.sign == MINUScout << "-";   
            for (
    a.lastdigits>=0--) cout << a.digits[i];
            
    cout << endl;
            
            return 
    cout;   
        }
        
        
    // operator bignum = string (line)
        
    void operator = (const stringlineinput) {
            
    int i0;   // counter
            
    string line;    
            
            
    string signbignum string(lineinput.begin() + 0lineinput.begin() + 1);
             if (
    signbignum == "+") {
                 
    this->sign PLUS;          
                 
    line string(lineinput.begin() + 1lineinput.end());        
             }
             else if (
    signbignum == "-") {
                 
    this->sign MINUS
                 
    line string(lineinput.begin() + 1lineinput.end());   
             }
             else {
                 
    this->sign PLUS;  
                 
    line lineinput;
             }
             
            
    this->lastdigits line.size() - 1;   
            for (
    line.size() - 1>=0--) this->digits[++] = line[i] - '0';           
        }
        
        
    // operator == (between two bignum)
        
    bool operator == (const bignumb) {
            
    int i;    // counter
            
            
    if (this->sign != b.sign) return false;
            if (
    this->lastdigits != b.lastdigits) return false;
            for (
    this->lastdigits>= 0--) {
                if (
    this->digits[i] != b.digits[i]) return false;
            }
            
            return 
    true;
        }
        
        
    // operator != (between two bignum)
        
    bool operator != (const bignumb) {
            static 
    bignum a = *this;
            if (
    == b) return false;
            
            return 
    true
        }
        
        
    // operator = (between two bignum)
        
    bignumoperator = (const bignumb) {
            
    int i;    // counter
            
            
    this->sign b.sign;
            
    this->lastdigits b.lastdigits;
            for (
    b.lastdigits>=0--) this->digits[i] = b.digits[i];
            
            return *
    this;  
        }
        
        
    // function Remove zero in bignum
        
    bignum removezero(const bignumb) {
            
    bignum a b;  
            while ( (
    a.lastdigits 0) && (a.digits[a.lastdigits] == 0)) a.lastdigits --;
            
    // - 0 = 0
            
    if ( (a.lastdigits == 0) && (a.digits[0] == 0)) a.sign PLUS;
            return 
    a;
        }
        
        
    // oprerator + (between two bignum)
         
    bignum operator + (const bignumy) {
           
    bignum a = *thiscy;    
           
    int carry 0i;    // carry and counter
           
           // sign of bignum  == sign of bignum b (PLUS, MINUS)
           
    if (a.sign == b.signc.sign a.sign;
           else { 
               
    // sign of bignum *this is MINUS and sing of bignum b is PLUS
               
    if (a.sign == MINUS) {
                   
    a.sign PLUS;
                   
    a;
                   
    a.sign MINUS;      
               } else {
                   
    b.sign PLUS;
                   
    b;
                   
    b.sign MINUS;     
               }
               return 
    c;
           }
           
    // length of bignum
           
    c.lastdigits max(a.lastdigitsb.lastdigits) + 1;
           for (
    0<= c.lastdigits++) {
               
    c.digits[i] = (carry a.digits[i] + b.digits[i]) % COSO;
               
    carry = (carry a.digits[i] + b.digits[i]) / COSO;
           }
           
    removezero(c);
           return 
    c;
        } 
        
        
    // operator += (with a bignum)
        
    bignum operator += (const bignumb) {
            
            return (*
    this = *this b); 
        }
        
        
    // operator - (between two bignum)
        
    bignum operator - (const bignumy) {
           
    bignum a = *thiscremovezero(y), so0;
           
    so0 "0";
           
    int borrow 0divi;    // counter
           // bignum b == 0
           
    if (== so0) return a;
           
           
    // bignum a == 0
           
    if (== so0) {   
              if (
    so0) {
                
    b.sign PLUS;    
                return 
    b;
              }
              else if (
    so0) {
                  
    b.sign MINUS;
                  return 
    b
              }
              else return 
    so0;
           }
           
           
    //sign of bignum a == sign of bignum b
           
    if (a.sign == b.sign) {
                 
    c.sign a.sign;     
           } else {
               
    // sign of bignum *this is MINUS and sing of bignum b is PLUS
               
    if (a.sign == MINUS) {
                   
    a.sign PLUS;
                   
    b;
                   
    c.sign MINUSa.sign MINUS;      
                   return 
    c;
               } else {
                   
    b.sign PLUS;
                   
    b;
                   
    c.sign PLUS;  b.sign MINUS;     
                   return 
    c;
               }
           }
           if (
    a.sign == PLUS
           {
               if (
    >= b) {
                   
    c.sign PLUS;  
                   
                   
    c.lastdigits max(a.lastdigitsb.lastdigits);
                   
                   for (
    0<= c.lastdigits++) {
                       
    div a.digits[i] - borrow b.digits[i];
                       if (
    a.digits[i] > 0borrow 0;
                       if (
    div 0) {
                           
    div += COSOborrow 1
                       } 
                       
    c.digits[i] = div COSO;
                   }
               } else {
                   
    c.sign MINUS;
                   
    c.lastdigits max(a.lastdigitsb.lastdigits);
                   for (
    0<= c.lastdigits++) {
                       
    div b.digits[i] - borrow a.digits[i];
                       if (
    b.digits[i] > 0borrow 0;
                       if (
    div 0) {
                           
    div += COSOborrow 1
                       } 
                       
    c.digits[i] = div COSO;
                   }   
               }
           } else {
                
    a.sign PLUS;
                
    b.sign PLUS;
                
    a;  
                if (
    bc.sign PLUS;
                else 
    c.sign MINUS;
           }
           
    removezero(c);
           return 
    c;
        } 
         
        
    // operator -= (with a bignum)
        
    bignum operator -= (const bignumb) {
            
            return (*
    this = *this b);
        }  
        
        
    // operator shift left bit (b is number)
        
    const bignum operator <<= (int b) {
           
    int in;        // counter
           
    bignum so0;    // bignum 0  
           
           // if bignum is 0 then return 0 (do nothing)
           
    so0 "0";
           if ((
    this->lastdigits) == && (this->digits[0] == 0)) return so0;
           
    this->lastdigits 1;
           
    memmove(this->digits bthis->digitssizeof (this->digits[0]));
           
    memset(this->digits0sizeof (this->digits[0]));
           
    /*
           for (i = lastdigits; i >=0; i --) this->digits[i + b] = this->digits[i];
           for (i = 0; i < b; i ++) this->digits[i] = 0;
           */
           
    this->lastdigits += b;
           
           return *
    this;
        }
        
        
    // operator * (between two bignum
        
    bignum operator * (const bignumb) {
            
    bignum cbsonhan = *thistong;
            
    int ij;
            
    "0";
        
            for (
    0<= a.lastdigits++) {
                for (
    1<= a.digits[i]; ++) {
                    
    tong sonhan c;
                    
    tong;    
                }
                
    sonhan <<= 1;
            }
             
    // sign
            
    c.sign = (this->sign) * (a.sign);

            return 
    c;  
        }
        
        
    // operator *= (with a bignum)
        
    bignum operator *= (const bignumb) {
           
           return (*
    this = *this b); 
        }
        
        
    // operator < (with a bignum)
        
    bool operator < (const bignumb) {
              
    bignum a = *this,bso0so0 ="0"
              
    int i;    // counter
              
              // bignum b == 0
              
    if (== so0) {
                   if (
    this->sign 0) return false;
                   else return 
    true
              }
              
    // check == 
              
    if (== b) return false;
              
    // check sign
              
    if (a.sign b.sign) return true;
              else if (
    a.sign b.sign) return false;
              else {
                   
    // +
                  
    if ((a.sign == PLUS) && (b.sign == PLUS)) {
                       if (
    a.lastdigits b.lastdigits) return false;
                       if (
    a.lastdigits b.lastdigits) return true;
                       for (
    a.lastdigits>=0--) {
                           if (
    a.digits[i] < b.digits[i]) return true;
                           if (
    a.digits[i] > b.digits[i]) return false;
                       } 
                       return 
    false;       
                  }
                  
    // -
                  
    if ((a.sign == MINUS) && (b.sign == MINUS)) {
                       if (
    a.lastdigits b.lastdigits) return true;
                       if (
    a.lastdigits b.lastdigits) return false;
                       for (
    a.lastdigits>=0--) {
                           if (
    a.digits[i] < b.digits[i]) return false;
                           if (
    a.digits[i] > b.digits[i]) return true;
                       }
                       return 
    false;       
                  }
              }
          }
          
        
    // operator > (with a bignum)
        
    bool operator > (const bignumb) {
            
    bignum a = *this;
            if (
    b) return false;
            if (
    == b) return false;
            
            return 
    true
        }
        
        
    // operator >= (with a bignum)
        
    bool operator >= (const bignumb) {
            
    bignum a = *this;
            if (
    b) return false;
            
            return 
    true
        } 
        
        
    // operator <= (with a bignum)
         
    bool operator <= (const bignumb) {
             
    bignum a = *this
             if (
    b) return false;
             
             return 
    true
         } 
          
        
    // operator / (between two bignum) 
        
    bignum operator / (const bignumy) {
            
    bignum c= *thisremovezero(y), sochiaso0so1;
            
    int asignbsign;  // sign 
            
    int i;             // counter
            
            
    try {
                
    // bignum b == 0
                
    if (== so0) { 
                      
    cout << "Could not divide zero !" << endl;
                }
                
    // sign
                
    c.sign = (a.sign) * (b.sign);
                
    asign a.signbsign b.sign;
                
                
    sochia "0"so0 "0"so1 "1";
                
    a.sign PLUS;
                
    b.sign PLUS;
                
    // bignum b == 1
                
    if(== so1) return *this;
                
    // bignum a == bignum b
                
    if (== b) return so1;
                if (
    b)  return so0;          
                else {  
                    
    c.lastdigits a.lastdigits;
                    for (
    c.lastdigits>= 0--) {
                        
    sochia <<= 1;
                        
    sochia.digits[0] = a.digits[i];
                        
    c.digits[i] = 0;     
                        while (
    true) {
                                 if (
    sochia b) break;
                                 
    c.digits[i] ++;
                                 
    sochia -= b;
                        }  
                    }
                    
    a.sign asign
                    
    b.sign bsign;
                }
            } catch (
    exception &e) {
                    
    cout << "Error !" << endl;  
            }
            
    removezero(c);
            return 
    c;          
        }
        
        
    // operator /= (with a bignum)
        
    bignum operator /= (const bignumb) {
           
           return (*
    this = *this b); 
        }
        
        
    // operator -()
        
    bignum operator -() {       
           
    bignum so0so0 "0"
           
           return (
    so0 - *this);
        }
        
        
    // operator get abs() (absolute)
         
    bignum abs() {
            
    bignum so0so0 "0";  
            
            if (*
    this so0) return (so0 - *this);  
            else return *
    this;
        }
        
        
    // operator % (with a bignum)
        
    bignum operator % (const bignumc) {
               
            
    bignum a = *thiscdso0;  
            
    so0 "0"int dsign;
            if (
    b) {
               if (
    a.sign == b.sign) {
                    if (
    a.sign == PLUSdsign PLUS;
                    else 
    dsign MINUS;      
               } else {
                      
    dsign PLUS;
               }
               
    a.sign PLUS;
               
    b.sign PLUS;
               
    - (b) * b;
               
    d.sign dsign;
               
               
    removezero(d);
               return 
    d;  
            } else if (
    b) {
               
    d.sign a.sign;    
               
    removezero(a);
               return 
    d;    
            }
            else return 
    so0;
        }
        
        
    // operator % (with a bignum)
        
    bignum operator %= (const bignumb) {
           
           return (*
    this = *this b); 
        }
    }; 
    File bignum2.h
    PHP Code:
    /*
      *
      *  Library Bignum code by My Firstlove Story
      *  Author : Hindua88
      *
    */
    /*
    Library bignum include: 
    1) friend istream& operator >> (istream& cin, bignum& a)
    2) friend ostream& operator << (ostream& cout, const bignum& a)  
    3) bool operator == (const bignum& b)
    4) bool operator != (const bignum& b)
    5) bignum& operator = (const bignum& b)
    6) bignum operator + (const bignum& b)
    7) bignum operator += (const bignum& b)
    8) bignum operator - (const bignum& y)
    9) bignum operator -= (const bignum& b)
    10) bignum operator * (const bignum& b)
    11) bignum operator *= (const bignum& b)
    12) bool operator < (const bignum& b)
    13) bool operator > (const bignum& b)
    14) bool operator >= (const bignum& b)
    15) bool operator <= (const bignum& b)
    16) bignum operator / (const bignum& y)
    17) bignum operator /= (const bignum& b)
    18) bignum operator -()
    19) bignum abs()
    20) bignum operator % (const bignum& c)
    21) bignum operator %= (const bignum& b)
    */
    #include <iostream>
    #include <sstream>
    #include <fstream>

    #define COSO 1000000000
    #define SOCHUSO 9

    using namespace std;

    #define MAXDIGITS 80000
    #define PLUS     +1
    #define MINUS    -1

    typedef unsigned __int32 uint;
    typedef unsigned __int64 ull;

    class 
    bignum {
      private :      
        
    uint  digits[MAXDIGITS];   // Array int 
        
    int  sign;                 // Sign bignum   
        
    int  lastdigits;           // Length bignum 
      
      
    public :
        
    // function constructor
        
    bignum() {
          
           
    memset(this->digits0MAXDIGITS sizeof(this->digits[0]));      
        }
        
    // for bignum = uint
        
    void operator = (const uinta) {
             
    this->lastdigits 0;
             
    this->sign PLUS;        // because a allways PLUS
             
    this->digits[0] = a;
             
    memset(this->digits 10, (MAXDIGITS 1) * sizeof (this->digits[0]));
        }
        
    // multi bignum * unit
        
    void operator *= (const uinta) {
             
    ull nho 0;  // carry
             
    int i;        // counter
             
    ull c a;
             
             
    this->sign this->sign;
             for (
    0<= this->lastdigits++) {
                 
    nho += this->digits[i]; 
                 
    this->digits[i] = nho COSO;
                 
    nho /= COSO;
             }
             if (
    nho && MAXDIGITS) {
                 
    this->digits[++ this->lastdigits] = nho;    
             }
        }
        
    // function operator >> (input)
        
    friend istreamoperator >> (istreamcinbignuma) {
             
    string line;    // string bignum
             
    getline(cinline); 
             
    line;
             
             return 
    cin;  
        }
        
    // function operator << (output) 
        
    friend ostreamoperator << (ostreamcout, const bignuma) {
            
    int i;          // counter
            
    string line;
            
            if (
    a.sign == MINUScout << "-";   
            for (
    a.lastdigits>=0--) {
                
    ostringstream os;
                
    os << a.digits[i];
                
    string s os.str();
                if (
    != a.lastdigits) {
                      while (
    s.size() < SOCHUSO"0" s;
                }
                
    line += s;
            } 
            
    cout << line << endl;
            
            return 
    cout;   
        }
        
    // operator bignum = string (line)
        
    void operator = (const stringlineinput) {
            
    int i0;   // counter
            
    string line;    
            
            
    string signbignum string(lineinput.begin() + 0lineinput.begin() + 1);
             if (
    signbignum == "+") {
                 
    this->sign PLUS;          
                 
    line string(lineinput.begin() + 1lineinput.end());        
             }
             else if (
    signbignum == "-") {
                 
    this->sign MINUS
                 
    line string(lineinput.begin() + 1lineinput.end());   
             }
             else {
                 
    this->sign PLUS;  
                 
    line lineinput;
             }
             
            while (
    line.size() % SOCHUSO != 0line "0" line;
            
            
    this->lastdigits line.size() / SOCHUSO 1;
            
            for (
    0<= this->lastdigits++) {
                
    istringstream fs(line.substr(SOCHUSOSOCHUSO));
                
    fs >> digits[this->lastdigits i]; 
            }
        }
        
    // operator == (between two bignum)
        
    bool operator == (const bignumb) {
            
    int i;    // counter
            
            
    if (this->sign != b.sign) return false;
            if (
    this->lastdigits != b.lastdigits) return false;
            for (
    this->lastdigits>= 0--) {
                if (
    this->digits[i] != b.digits[i]) return false;
            }
            
            return 
    true;
        }
        
    // operator != (between two bignum)
        
    bool operator != (const bignumb) {
            static 
    bignum a = *this;
            if (
    == b) return false;
            
            return 
    true
        }
        
    // operator = (between two bignum)
        
    bignumoperator = (const bignumb) {
            
    int i;    // counter
            
            
    this->sign b.sign;
            
    this->lastdigits b.lastdigits;
            for (
    b.lastdigits>=0--) this->digits[i] = b.digits[i];
            
            return *
    this;  
        }
        
    // function Remove zero in bignum
        
    bignum removezero(const bignumb) {
            
    bignum a b;  
            while ( (
    a.lastdigits 0) && (a.digits[a.lastdigits] == 0)) a.lastdigits --;
            
    // - 0 = 0
            
    if ( (a.lastdigits == 0) && (a.digits[0] == 0)) a.sign PLUS;
            
            return 
    a;
        }
        
    // oprerator + (between two bignum)
         
    bignum operator + (const bignumy) {
           
    bignum cy;    
           
    int i;            // counter
           
    ull nho 0;  // carry
           
           // sign of bignum  == sign of bignum b (PLUS, MINUS)
           
    if (this->sign == b.signc.sign this->sign;
           else { 
               
    // sign of bignum *this is MINUS and sing of bignum b is PLUS
               
    if (this->sign == MINUS) {
                   
    this->sign PLUS;
                   
    - *this;
                   
    this->sign MINUS;      
               } else {
                   
    b.sign PLUS;
                   
    = *this b;
                   
    b.sign MINUS;     
               } 
               return 
    c;
           }
           
    // length of bignum
           
    c.lastdigits max(this->lastdigitsb.lastdigits);
           for (
    0<= c.lastdigits++) {
               
    nho += this->digits[i] + b.digits[i];
               
    c.digits[i] = nho COSO;
               
    nho /= COSO;
           }
           if (
    nho && MAXDIGITSc.digits[++ c.lastdigits] = nho;        
           
           return 
    c;
        } 
        
    // operator += (with a bignum)
        
    bignumoperator += (const bignumb) {
            
            return (*
    this = *this b); 
        }
        
    // operator - (between two bignum)
        
    bignum operator - (const bignumy) {
           
    bignum a = *thiscremovezero(y), so0;
           
    so0 0;
           
    int iborrow 0div;
           
           
    // bignum a == b
           
    if (== b) return so0;
           
    // bignum b == 0
           
    if (== so0) return a;
           
    // bignum a == 0
           
    if (== so0) {   
              if (
    so0) {
                
    b.sign PLUS;    
                return 
    b;
              }
              else if (
    so0) {
                  
    b.sign MINUS;
                  return 
    b
              }
              else return 
    so0;
           }
           
    // if bignum a == b
           
    if (== b) return so0;
           
    //sign of bignum a == sign of bignum b
           
    if (a.sign == b.sign) {
                 
    c.sign a.sign;     
           } else {
               
    // sign of bignum *this is MINUS and sing of bignum b is PLUS
               
    if (a.sign == MINUS) {
                   
    a.sign PLUS;
                   
    b;
                   
    c.sign MINUS;  a.sign MINUS;      
                   return 
    c;
               } else {
                   
    b.sign PLUS;
                   
    b;
                   
    c.sign PLUS;   b.sign MINUS;     
                   return 
    c;
               }
           }
           
    // bignum a sign == bignum b sign : PLUS
           
    if (a.sign == PLUS
           {
               if (
    >= b) {
                   
    c.sign PLUS;         
                   
    c.lastdigits max(a.lastdigitsb.lastdigits);
                   for (
    0<= c.lastdigits++) {
                       
    div a.digits[i] - borrow b.digits[i];
                       
    //if (a.digits[i] > 0) borrow = 0;
                       
    if (div 0) {
                           
    div += COSO;
                           
    borrow 1
                       } else {
                           
    borrow 0;   
                       }  
                       
    c.digits[i] = div COSO;
                   }
               } else {
                   
    c.sign MINUS;
                   
    c.lastdigits max(a.lastdigitsb.lastdigits);
                   for (
    0<= c.lastdigits++) {
                       
    div b.digits[i] - borrow a.digits[i];
                       
    //if (b.digits[i] > 0) borrow = 0;
                       
    if (div 0) {
                           
    div += COSO;
                           
    borrow 1
                       } else {
                           
    borrow 0;   
                       }
                       
    c.digits[i] = div COSO;
                   }   
               }
           } else 
    // bignum a sign == bignum b sign : MINUS
           
    {
                
    a.sign PLUS;
                
    b.sign PLUS;
                
    a;  
                if (
    bc.sign PLUS;
                else 
    c.sign MINUS;
           }
           
    // removezero 0 
           // Example 1000000000000000000 - 999999999 = 0999999999000000001
           
    removezero(c);
           return 
    c;
        } 
         
        
    // operator -= (with a bignum)
        
    bignum operator -= (const bignumb) {
            
            return (*
    this = *this b);
        }  
        
        
    // operator shift left bit (b is number)
        // Example 1000000000  <<= 1 return 1000000000000000000
        //         1000000000  <<= 2 return 1000000000000000000000000000
        
    const bignum operator <<= (int b) {
           
    int i;        // counter
           
    int n;        // this->lastdigits + 1
           
    bignum so0;    // bignum 0  
           
           // if bignum is 0 then return 0 (do nothing)
           
    so0 0;
           if ((
    this->lastdigits) == && (this->digits[0] == 0)) return so0;
           
           
    //for (i = lastdigits; i >=0; i --) this->digits[i + b] = this->digits[i];
           //for (i = 0; i < b; i ++) this->digits[i] = 0;
           
           
    this->lastdigits 1;
           
    memmove(this->digits bthis->digitsnsizeof (this->digits[0]));
           
    memset(this->digits0sizeof (this->digits[0]));
           
    this->lastdigits += b;
           
           return *
    this;
        }
        
        
    // operator * (between two bignum)
        
    bignum operator * (const bignumy) {
            
    bignum b ytichtong;
            
    int i;   //counter
            
    tong 0;
        
            for (
    0<= b.lastdigits++) {
               
    tich = *this
               
    tich *= b.digits[i];
               
    tich <<= i;
               
    tong += tich;
            }
             
    // sign
            
    tong.sign = (this->sign) * (b.sign);

            return 
    tong;  
        }
        
        
    // operator *= (with a bignum)
        
    bignumoperator *= (const bignumb) {
           
           return (*
    this = *this b); 
        }

        
        
    // operator < (with a bignum)
        
    bool operator < (const bignumc) {
              
    bignum a = *this,cso0so0 0
              
    int i;    // counter
              
              // bignum b == 0
              
    if (== so0) {
                   if (
    this->sign 0) return false;
                   else return 
    true
              }
              
    // check == 
              
    if (== b) return false;
              
    // check sign
              
    if (a.sign b.sign) return true;
              else if (
    a.sign b.sign) return false;
              else {
                   
    // +
                  
    if ((a.sign == PLUS) && (b.sign == PLUS)) {
                       if (
    a.lastdigits b.lastdigits) return false;
                       if (
    a.lastdigits b.lastdigits) return true;
                       for (
    a.lastdigits>=0--) {
                           if (
    a.digits[i] < b.digits[i]) return true;
                           if (
    a.digits[i] > b.digits[i]) return false;
                       } 
                       return 
    false;       
                  }
                  
    // -
                  
    if ((a.sign == MINUS) && (b.sign == MINUS)) {
                       if (
    a.lastdigits b.lastdigits) return true;
                       if (
    a.lastdigits b.lastdigits) return false;
                       for (
    a.lastdigits>=0--) {
                           if (
    a.digits[i] < b.digits[i]) return false;
                           if (
    a.digits[i] > b.digits[i]) return true;
                       }
                       return 
    false;       
                  }
              }
          }
        
    // operator > (with a bignum)
        
    bool operator > (const bignumb) {
            
    bignum a = *this;
            if (
    b) return false;
            if (
    == b) return false;
            
            return 
    true
        }
        
    // operator >= (with a bignum)
        
    bool operator >= (const bignumb) {
            
    bignum a = *this;
            if (
    b) return false;
            
            return 
    true
        } 
        
    // operator <= (with a bignum)
         
    bool operator <= (const bignumb) {
             
    bignum a = *this
             if (
    b) return false;
             
             return 
    true
         }  
        
    // operator / (between two bignum) 
        
    bignum operator / (const bignumy) {
            
    bignum c= *thissochiaso0so1;
            
    bignum b removezero(y);
            
    int asignbsign;  // sign 
            
    int i;             // counter
            
            
    try {
                
    // bignum b == 0
                
    if (== so0cout << "Error ! Could not div 0!" << endl;
                
    // sign
                
    c.sign = (a.sign) * (b.sign);
                
    asign a.signbsign b.sign;
                
                
    so0 0so1 1;
                
    a.sign PLUS;
                
    b.sign PLUS;
                
    // bignum b == 1 or b == -1
                // exam a = "1000000000000000000";  b = "-1";
                // a div b = -a;
                
    if(== so1) {
                      if (
    bsign == MINUS) return (so0 - *this);
                      return *
    this;
                }
                
    // bignum a == bignum b
                
    else if (== b) return so1;
                else if (
    b) return so0;
                else {  
                    
    c.lastdigits a.lastdigits;
                    
    sochia 0;
                    for (
    c.lastdigits>= 0--) {
                        
    sochia <<= 1;
                        
    sochia.digits[0] = a.digits[i];
                        
    c.digits[i] = 0;                   
                        while (
    true) {
                                 if (
    sochia b) break;            
                                 
    c.digits[i] ++;
                                 
    sochia -= b;
                        }  
                    }
                    
    a.sign asign
                    
    b.sign bsign;
              }
            } catch (
    exception &e) {
                    
    cout << "Error !" << endl;  
            }
            
    // Example 1000000000000000000 div 999999999 = 000000001000000001
            // Example 999999999 div 1000000000000000000 = 0
            
    removezero(c);
            return 
    c;          
        }
        
        
    // operator /= (with a bignum)
        
    bignumoperator /= (const bignumb) {
           
           return (*
    this = *this b); 
        }
        
        
    // operator -()
        
    bignum operator -() {       
           
    bignum so0so0 0
           
           return (
    so0 - *this);
        }
        
        
    // operator get abs() (absolute value)
         
    bignum abs() {
            
    bignum so0so0 0;  
            
            if (*
    this so0) return (so0 - *this);  
            else return *
    this;
        }
        
        
    // operator % (with a bignum)
        
    bignum operator % (const bignumc) {
            
    bignum a = *thiscdso0;  
            
    so0 0int dsign;
            if (
    b) {
               if (
    a.sign == b.sign) {
                    if (
    a.sign == PLUSdsign PLUS;
                    else 
    dsign MINUS;      
               } else  
    dsign PLUS;
               
    a.sign PLUS;
               
    b.sign PLUS;
               
    - (b) * b;
               
    d.sign dsign;
               return 
    d;  
            } else if (
    b) {
               
    d.sign a.sign;    
               
    removezero(a);
               return 
    d;    
            }
            else return 
    so0;
        }
        
        
    // operator % (with a bignum)
        
    bignumoperator %= (const bignumb) {
           
           return (*
    this = *this b); 
        }
    }; 
    File test1.cpp
    PHP Code:
    #include <bignum1.h>
    #include <fstream>

    using namespace std;
    int main() {
        
    bignum abcd;
        
        
    ifstream cin("b1.inp");
        
    cin >> a;
        
    cin >> b;
        
    cin.close();
        
        
    cout << b;
        
    cout << b;
        
    cout << b;
        
    cout << b;
        
    cout << b;

        
    /*
        cout << b /a;
        b /= a;
        cout << b;
          */   
             
    getchar();

    File test2.cpp
    PHP Code:
    #include <bignum2.h>

    bignum factorial(int a)
    {      
    int i
           
    bignum fac;
           
           
    fac 1;
           if ( 
    == || == 1) return fac;
           for (
    2<= a++) fac *= i;
           return 
    fac;
    }

    int main()
    {
        
    bignum ab;
        
    /*
        ifstream cin("b1.inp");
        cin >> a;
        cin >> b;
        cin.close();
        */
        
        
    int start clock();
        
    ofstream cout("b12.out");
        
    cout << factorial(100000);
        
    /*
        cout << "a + b = " << a + b;
        cout << "a - b = " << a - b;
        cout << "a * b = " << a * b;
        */
        
    cout << "Time : " << clock()- start << endl;
        
    cout.close();

    HỌC DỐT RẤT KHỔ ....
    Đã được chỉnh sửa lần cuối bởi tinhyeumangtheo88 : 15-04-2010 lúc 08:56 PM.

  7. #7
    Ngày gia nhập
    03 2010
    Bài viết
    41

    Code:
    #define MAXDIGITS 10000
    #define PLUS     +1
    #define MINUS    -1
    #define COSO     10
    
    class bignum {
      private :      
        int  digits[MAXDIGITS];   // Array int 
        int  sign;                // Sign bignum   
        int  lastdigits;          // Length bignum 
      
      public :
        // function constructor
        bignum() {
             memset (this->digits, 0, MAXDIGITS * sizeof (this->digits[0]));    
        }
    
        // function operator >> (input)
        friend istream& operator >> (istream& cin, bignum& a) {
             string line;    // string bignum
             getline(cin, line); 
             a = line;
             return cin;  
        }
        
        // function operator << (output) 
        friend ostream& operator << (ostream& cout, const bignum& a) {
            int i;          // counter
            
            if (a.sign == MINUS) cout << "-";   
            for (i = a.lastdigits; i >=0; i --) cout << a.digits[i];
            cout << endl;
            
            return cout;   
        }
        
        // operator bignum = string (line)
        void operator = (const string& lineinput) {
            int i, j = 0;   // counter
            string line;    
            
            string signbignum = string(lineinput.begin() + 0, lineinput.begin() + 1);
             if (signbignum == "+") {
                 this->sign = PLUS;          
                 line = string(lineinput.begin() + 1, lineinput.end());        
             }
             else if (signbignum == "-") {
                 this->sign = MINUS; 
                 line = string(lineinput.begin() + 1, lineinput.end());   
             }
             else {
                 this->sign = PLUS;  
                 line = lineinput;
             }
             
            this->lastdigits = line.size() - 1;   
            for (i = line.size() - 1; i >=0; i --) this->digits[j ++] = line[i] - '0';           
        }
        
        // operator == (between two bignum)
        bool operator == (const bignum& b) {
            int i;    // counter
            
            if (this->sign != b.sign) return false;
            if (this->lastdigits != b.lastdigits) return false;
            for (i = this->lastdigits; i >= 0; i --) {
                if (this->digits[i] != b.digits[i]) return false;
            }
            
            return true;
        }
        
        // operator != (between two bignum)
        bool operator != (const bignum& b) {
            static bignum a = *this;
            if (a == b) return false;
            
            return true; 
        }
        
        // operator = (between two bignum)
        bignum& operator = (const bignum& b) {
            int i;    // counter
            
            this->sign = b.sign;
            this->lastdigits = b.lastdigits;
            for (i = b.lastdigits; i >=0; i --) this->digits[i] = b.digits[i];
            
            return *this;  
        }
        
        // function Remove zero in bignum
        bignum removezero(const bignum& b) {
            bignum a = b;  
            while ( (a.lastdigits > 0) && (a.digits[a.lastdigits] == 0)) a.lastdigits --;
            // - 0 = 0
            if ( (a.lastdigits == 0) && (a.digits[0] == 0)) a.sign = PLUS;
            return a;
        }
        
        // oprerator + (between two bignum)
         bignum operator + (const bignum& y) {
           bignum a = *this, c, b = y;    
           int carry = 0, i;    // carry and counter
           
           // sign of bignum  == sign of bignum b (PLUS, MINUS)
           if (a.sign == b.sign) c.sign = a.sign;
           else { 
               // sign of bignum *this is MINUS and sing of bignum b is PLUS
               if (a.sign == MINUS) {
                   a.sign = PLUS;
                   c = b - a;
                   a.sign = MINUS;      
               } else {
                   b.sign = PLUS;
                   c = a - b;
                   b.sign = MINUS;     
               }
               return c;
           }
           // length of bignum
           c.lastdigits = max(a.lastdigits, b.lastdigits) + 1;
           for (i = 0; i <= c.lastdigits; i ++) {
               c.digits[i] = (carry + a.digits[i] + b.digits[i]) % COSO;
               carry = (carry + a.digits[i] + b.digits[i]) / COSO;
           }
           c = removezero(c);
           return c;
        } 
        
        // operator += (with a bignum)
        bignum operator += (const bignum& b) {
            
            return (*this = *this + b); 
        }
        
        // operator - (between two bignum)
        bignum operator - (const bignum& y) {
           bignum a = *this, c, b = removezero(y), so0;
           so0 = "0";
           int borrow = 0, div, i;    // counter
           // bignum b == 0
           if (b == so0) return a;
           
           // bignum a == 0
           if (a == so0) {   
              if (b < so0) {
                b.sign = PLUS;    
                return b;
              }
              else if (b > so0) {
                  b.sign = MINUS;
                  return b; 
              }
              else return so0;
           }
           
           //sign of bignum a == sign of bignum b
           if (a.sign == b.sign) {
                 c.sign = a.sign;     
           } else {
               // sign of bignum *this is MINUS and sing of bignum b is PLUS
               if (a.sign == MINUS) {
                   a.sign = PLUS;
                   c = a + b;
                   c.sign = MINUS; a.sign = MINUS;      
                   return c;
               } else {
                   b.sign = PLUS;
                   c = a + b;
                   c.sign = PLUS;  b.sign = MINUS;     
                   return c;
               }
           }
           if (a.sign == PLUS) 
           {
               if (a >= b) {
                   c.sign = PLUS;  
                   
                   c.lastdigits = max(a.lastdigits, b.lastdigits);
                   
                   for (i = 0; i <= c.lastdigits; i ++) {
                       div = a.digits[i] - borrow - b.digits[i];
                       if (a.digits[i] > 0) borrow = 0;
                       if (div < 0) {
                           div += COSO; borrow = 1; 
                       } 
                       c.digits[i] = div % COSO;
                   }
               } else {
                   c.sign = MINUS;
                   c.lastdigits = max(a.lastdigits, b.lastdigits);
                   for (i = 0; i <= c.lastdigits; i ++) {
                       div = b.digits[i] - borrow - a.digits[i];
                       if (b.digits[i] > 0) borrow = 0;
                       if (div < 0) {
                           div += COSO; borrow = 1; 
                       } 
                       c.digits[i] = div % COSO;
                   }   
               }
           } else {
                a.sign = PLUS;
                b.sign = PLUS;
                c = b - a;  
                if (a < b) c.sign = PLUS;
                else c.sign = MINUS;
           }
           c = removezero(c);
           return c;
        } 
         
        // operator -= (with a bignum)
        bignum operator -= (const bignum& b) {
            
            return (*this = *this - b);
        }  
        
        // operator shift left bit (b is number)
        const bignum operator <<= (int b) {
           int i, n;        // counter
           bignum so0;    // bignum 0  
           
           // if bignum is 0 then return 0 (do nothing)
           so0 = "0";
           if ((this->lastdigits) == 0 && (this->digits[0] == 0)) return so0;
           n = this->lastdigits + 1;
           memmove(this->digits + b, this->digits, n * sizeof (this->digits[0]));
           memset(this->digits, 0, b * sizeof (this->digits[0]));
           /*
           for (i = lastdigits; i >=0; i --) this->digits[i + b] = this->digits[i];
           for (i = 0; i < b; i ++) this->digits[i] = 0;
           */
           this->lastdigits += b;
           
           return *this;
        }
        
        // operator * (between two bignum
        bignum operator * (const bignum& b) {
            bignum c, a = b, sonhan = *this, tong;
            int i, j;
            c = "0";
        
            for (i = 0; i <= a.lastdigits; i ++) {
                for (j = 1; j <= a.digits[i]; j ++) {
                    tong = sonhan + c;
                    c = tong;    
                }
                sonhan <<= 1;
            }
             // sign
            c.sign = (this->sign) * (a.sign);
    
            return c;  
        }
        
        // operator *= (with a bignum)
        bignum operator *= (const bignum& b) {
           
           return (*this = *this * b); 
        }
        
        // operator < (with a bignum)
        bool operator < (const bignum& b) {
              bignum a = *this,c = b, so0; so0 ="0"; 
              int i;    // counter
              
              // bignum b == 0
              if (c == so0) {
                   if (this->sign > 0) return false;
                   else return true; 
              }
              // check == 
              if (a == b) return false;
              // check sign
              if (a.sign < b.sign) return true;
              else if (a.sign > b.sign) return false;
              else {
                   // +
                  if ((a.sign == PLUS) && (b.sign == PLUS)) {
                       if (a.lastdigits > b.lastdigits) return false;
                       if (a.lastdigits < b.lastdigits) return true;
                       for (i = a.lastdigits; i >=0; i --) {
                           if (a.digits[i] < b.digits[i]) return true;
                           if (a.digits[i] > b.digits[i]) return false;
                       } 
                       return false;       
                  }
                  // -
                  if ((a.sign == MINUS) && (b.sign == MINUS)) {
                       if (a.lastdigits > b.lastdigits) return true;
                       if (a.lastdigits < b.lastdigits) return false;
                       for (i = a.lastdigits; i >=0; i --) {
                           if (a.digits[i] < b.digits[i]) return false;
                           if (a.digits[i] > b.digits[i]) return true;
                       }
                       return false;       
                  }
              }
          }
          
        // operator > (with a bignum)
        bool operator > (const bignum& b) {
            bignum a = *this;
            if (a < b) return false;
            if (a == b) return false;
            
            return true; 
        }
        
        // operator >= (with a bignum)
        bool operator >= (const bignum& b) {
            bignum a = *this;
            if (a < b) return false;
            
            return true; 
        } 
        
        // operator <= (with a bignum)
         bool operator <= (const bignum& b) {
             bignum a = *this; 
             if (a > b) return false;
             
             return true; 
         } 
          
        // operator / (between two bignum) 
        bignum operator / (const bignum& y) {
            bignum c, a = *this, b = removezero(y), sochia, so0, so1;
            int asign, bsign;  // sign 
            int i;             // counter
            
            try {
                // bignum b == 0
                if (b == so0) { 
                      cout << "Could not divide zero !" << endl;
                }
                // sign
                c.sign = (a.sign) * (b.sign);
                asign = a.sign; bsign = b.sign;
                
                sochia = "0"; so0 = "0", so1 = "1";
                a.sign = PLUS;
                b.sign = PLUS;
                // bignum b == 1
                if(b == so1) return *this;
                // bignum a == bignum b
                if (a == b) return so1;
                if (a < b)  return so0;          
                else {  
                    c.lastdigits = a.lastdigits;
                    for (i = c.lastdigits; i >= 0; i --) {
                        sochia <<= 1;
                        sochia.digits[0] = a.digits[i];
                        c.digits[i] = 0;     
                        while (true) {
                                 if (sochia < b) break;
                                 c.digits[i] ++;
                                 sochia -= b;
                        }  
                    }
                    a.sign = asign; 
                    b.sign = bsign;
                }
            } catch (exception &e) {
                    cout << "Error !" << endl;  
            }
            c = removezero(c);
            return c;          
        }
        
        // operator /= (with a bignum)
        bignum operator /= (const bignum& b) {
           
           return (*this = *this / b); 
        }
        
        // operator -()
        bignum operator -() {       
           bignum so0; so0 = "0"; 
           
           return (so0 - *this);
        }
        
        // operator get abs() (absolute)
         bignum abs() {
            bignum so0; so0 = "0";  
            
            if (*this < so0) return (so0 - *this);  
            else return *this;
        }
        
        // operator % (with a bignum)
        bignum operator % (const bignum& c) {
               
            bignum a = *this, b = c, d, so0;  
            so0 = "0"; int dsign;
            if (a > b) {
               if (a.sign == b.sign) {
                    if (a.sign == PLUS) dsign = PLUS;
                    else dsign = MINUS;      
               } else {
                      dsign = PLUS;
               }
               a.sign = PLUS;
               b.sign = PLUS;
               d = a - (a / b) * b;
               d.sign = dsign;
               
               d = removezero(d);
               return d;  
            } else if (a < b) {
               d.sign = a.sign;    
               d = removezero(a);
               return d;    
            }
            else return so0;
        }
        
        // operator % (with a bignum)
        bignum operator %= (const bignum& b) {
           
           return (*this = *this % b); 
        }
    };

  8. #8
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Tại sao không xây dựng số nguyên lớn theo kiểu như các trình compiler vẫn làm hả các cậu. Tức là sử dụng bit nhị phân ấy mà cứ phải lưu theo cái kiểu char chữ số trong hệ 10:
    Ví dụ :
    Xây dựng số nguyên 64bit ta sử dụng 2 số nguyên unsigned 32 bit là 2 phần, bit cao và bit thấp.

    Sau đó cài đặt việc thực hiện,toán tử .... bằng các phép toán tử trên bit với 2 phần này. Như vậy có phải là tốt hơn không.

    Tối ưu về tốc độ, hỉu bản chất về cách biểu diễn số trong máy tính và thứ 3 là mang tính chuyên nghiệp cực kỳ cao. Cái này sao đó mới có thể sử dụng gọi là thư viện thực sự được, chứ làm kiểu char xử lý 2 đên 3 phút mới ra một phép toán thì tớ chịu,chương trình sử dụng thư viện mà cần làm cỡ 1000 phép tính kiểu đó thì chờ chắc phờ râu mất.

  9. #9
    Ngày gia nhập
    01 2008
    Bài viết
    6

    Làm theo kiểu bit ý tớ đọc ko hiểu. cái này tình 100.000! (sửa MAXDIGITS lên 80.000 bignum2.h) mất khoảng hơn 1 phút đối với máy tớ. (2G Ram)..

    Hay cậu làm thử đi post cho mọi người !

Các đề tài tương tự

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên.
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 19-06-2011, 01:05 PM
  3. Game Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên trên C#?
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 18
    Bài viết cuối: 08-06-2011, 11:12 PM
  4. Bài tập C++ chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được
    Gửi bởi nghiapro512 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-01-2011, 02:14 PM
  5. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn