Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: [C++] Cùng xây dựng một lớp xử lý số lớn.

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định [C++] Cùng xây dựng một lớp xử lý số lớn.

    Chào các bác.

    Em xin đưa ra 1 bài toán, sau đó đưa ra thiết kế cấu trúc dữ liệu và từng bước code từng phần một. Các bác giúp em một tay nhé.

    Bài toán:
    Viết ra 1 class, đặt tên là CNumber để phục vụ việc tính toán với các số cực lớn. Trên đó định ra các phép toán để tính toán như với số nguyên thông thường.

    Mục đích:Rèn luyện kỹ năng lập trình cho các bạn mới học và áp dụng trong các thuật toán mã hóa yêu cầu sử dụng các số cực lớn như RSA.

    Để cho khoa học và dễ đọc, thiết kế em xin viết ở bài sau.
    Các bác giúp em viết thì xin hãy post mỗi bài 1 method thôi nhé, để theo dõi nó dễ ấy mà. (SPAM luôn).
    Đã được chỉnh sửa lần cuối bởi Tarzan : 10-10-2006 lúc 08:49 AM.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    trước tiên phải xác định rõ, xây dựng số cực lớn tới chừng nào: 8byte(~18*10^18 = 18 tỷ tỷ), 12byte (~5*10^27 = 5 tỷ tỷ tỷ), 16byte ...hay độ lớn không giới hạn, nói thêm là số int/long trong VC chừng 4 tỷ
    nếu là số có dấu thì giá trịmax giảm 1 nửa
    tức là 8 byte có dấu = 9 tỷ tỷ

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định Cấu trúc dữ liệu.

    Đi từ một một ý tưởng rất tự nhiên, ta sẽ lưu các chữ số (digit) của lớp này vào 1 mảng các chữ số, như vậy độ lớn tối đa của CNumber sẽ phụ thuộc độ dài của mảng các chữ số này.
    Mảng digit này không chứa các chữ số thông thường (0..9 -> ở hệ decimal) mà sẽ phụ thuộc vào kiểu phần tử của mảng. Tức là, nếu 1 phần tử của mảng có kiểu unsigned char thì mỗi digit sẽ là 1 chữ số trong khoảng (0...255) -> CNumber được lưu trữ ở hệ cơ số 256. Việc thiết kế như vậy giúp tiết kiệm bộ nhớ và xử lý tính toán nhanh hơn. Trong chương trình sẽ có định nghĩa 2 kiểu dữ liệu và 2 hằng số giúp tùy biến điều này. (Trong chương trình em để kiểu digit 16 bit. (kiểu 32 bit để lưu kết quả phép tính +,-,*,/ từ 2 số 16 bit).

    Number.h
    C++ Code:
    1. /*************************************************
    2.  
    3. FILE: Number.h
    4. This file declara about class CNumber.
    5.  
    6. DATA STRUCTURE:
    7. A CNumber will be store as an array of digits.
    8. This array has DIGIT_NUMBER elements.
    9.  
    10. digit type: type of an digit
    11. _digit type: type of data which contains result of operator
    12.     between 2 digits. (sizeof(_digit) = 2*sizeof(digit))
    13. NUMBER_BASE = base of number
    14. *************************************************/
    15.  
    16. #ifndef __NUMBER_H__
    17. #define __NUMBER_H__
    18.  
    19. #define DIGIT_NUMBER 50
    20. #define NUMBER_BASE 0x10000
    21. typedef unsigned __int16 digit;
    22. typedef unsigned __int32 _digit;
    23.  
    24. class CNumber
    25. {
    26. public:
    27.     CNumber(void);
    28.     ~CNumber(void);
    29.  
    30.     // IMPORT OPERATORS
    31.     // import value from an integer
    32.     const CNumber & operator =(int num);
    33.     // import value from string (this string will be stored in hexa format).
    34.     const CNumber & operator =(char *str);
    35.     const CNumber & operator =(const CNumber &num);
    36.  
    37.     // EXPORT METHODS
    38.     // export to a string, this string contains all hexa digits
    39.     int ToString(char *str);
    40.    
    41.     // COMPARE OPERATORS
    42.     friend const int operator > (const CNumber & left, const CNumber & right);
    43.     friend const int operator >= (const CNumber & left, const CNumber & right);
    44.     friend const int operator < (const CNumber & left, const CNumber & right);
    45.     friend const int operator <= (const CNumber & left, const CNumber & right);
    46.     friend const int operator != (const CNumber & left, const CNumber & right);
    47.     friend const int operator == (const CNumber & left, const CNumber & right);
    48.  
    49.     // CALCULATION OPERATORS
    50.     const CNumber & operator += (const CNumber & num);
    51.     const CNumber & operator -= (const CNumber & num);
    52.     const CNumber & operator *= (const CNumber & num);
    53.     const CNumber & operator /= (const CNumber & num);
    54.     const CNumber & operator %= (const CNumber & num);
    55.     friend const CNumber operator + (const CNumber & left, const CNumber & right);
    56.     friend const CNumber operator - (const CNumber & left, const CNumber & right);
    57.     friend const CNumber operator * (const CNumber & left, const CNumber & right);
    58.     friend const CNumber operator / (const CNumber & left, const CNumber & right);
    59.     friend const CNumber operator % (const CNumber & left, const CNumber & right);
    60.  
    61.     // SHIFT OPERATORS
    62.     // shift left or right CNumber 'count' digits
    63.     const CNumber & operator >>= (const int count);
    64.     const CNumber & operator <<= (const int count);
    65.    
    66.     friend const CNumber operator >> (const CNumber & num, const int count);
    67.     friend const CNumber operator << (const CNumber & num, const int count);
    68.  
    69. private:
    70.     digit m_arrDigit[DIGIT_NUMBER];
    71.  
    72.     // set number to 0
    73.     void ClearNumber();
    74. };
    75.  
    76. #endif
    Đã được chỉnh sửa lần cuối bởi Tarzan : 10-10-2006 lúc 09:32 AM.

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Éc, đã có người trả nhời. Nhanh thiệt.

    Bài trên em có trình bày là độ lớn của số phụ thuộc vào độ lớn của mảng đó.
    Mong muốn của em là xử lý được các số có độ lớn cỡ khoảng >1000 bit.
    Đã được chỉnh sửa lần cuối bởi Tarzan : 10-10-2006 lúc 08:52 AM.

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định Constructor, Destructor

    C++ Code:
    1. CNumber::CNumber(void)
    2. {
    3.     ClearNumber();
    4. }
    5.  
    6. CNumber::~CNumber(void)
    7. {
    8. }
    9.  
    10. void CNumber::ClearNumber()
    11. {
    12.     memset(m_arrDigit, 0x00, DIGIT_NUMBER*sizeof(digit));
    13. }

  6. #6
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Mặc định [C++] Cùng xây dựng một lớp xử lý số lớn.

    1. đề nghị thêm
    #ifdef _NUMBER_H
    #define _NUMBER_H
    ...
    #endif
    bao lấy file .h trên

    2. digit là unsigned long sẽ xử lý tốt hơn

    3. DIGIT_NUMBER là lũy thừa của 2 ví dụ 64,128 sẽ đỡ gặp phiền toái sau này

    4. tại sao khi khởi tạo cần clear về 0, như vậy tạo ra hiệu ứng khác C++. Trong C++ khi khai báo biến, nó sẽ có giá trị bất kỳ. Làm như vậy có vẻ giống java. Đây cũng chỉ là vấn đề quan điểm. Theo tui khi khởi tạo không cần clear, khi nào người lập trình gán về 0 thì clear
    Đã được chỉnh sửa lần cuối bởi nguyentuan2 : 10-10-2006 lúc 09:10 AM.

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định operator =

    C++ Code:
    1. const CNumber & CNumber::operator =(const CNumber &num)
    2. {
    3.     memcpy(m_arrDigit, num.m_arrDigit, DIGIT_NUMBER*sizeof(digit));
    4.     return *this;
    5. }
    6.  
    7. const CNumber & CNumber::operator = (int num)
    8. {
    9.     int i;
    10.     for (i=0;i<sizeof(int)/sizeof(digit);i++)
    11.     {
    12.         m_arrDigit[i] = (digit)num;
    13.         num >>= 8*sizeof(digit);
    14.     }
    15.     return *this;
    16. }

    Đồng ý với bác là thêm mấy cái chỉ thị tiền biên dịch. Tuy nhiên cái Clear thì theo em mình sẽ giả sử tại mọi thời điểm, các chữ số của CNumber đều = 0 (nếu không dùng tới), điều này sẽ thuận lợi cho mình khi làm các phép tính +,-,*,/. Mặc dù có thể để người dùng Clear sau khi khai báo nhưng mình để default = 0 kiểm soát không phải dễ hơn sao?
    Còn cái DIGIT_NUMBER ấy, các method của mình phải có khả năng thích ứng với sự thay đổi của nó. Ta cứ để thế, thỉnh thoảng thay đổi cái đó 1 cái xem còn chạy đúng không. :P.
    Đã được chỉnh sửa lần cuối bởi Tarzan : 10-10-2006 lúc 09:43 AM.

  8. #8
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định const CNumber & CNumber::operator =(char *str)

    C++ Code:
    1. inline digit HexCharToDigit(char ch)
    2. {
    3.     if ((ch >= '0') && (ch <= '9')) return ch - '0';
    4.     if ((ch >= 'A') && (ch <= 'Z')) return ch - 'A' + 0x0A;
    5.     if ((ch >= 'a') && (ch <= 'z')) return ch - 'a' + 0x0A;
    6.     return 0x00; // this case occurs when ch is not hexa character.
    7. }
    8.  
    9. const CNumber & CNumber::operator =(char *str)
    10. {
    11.     int i, istr = 0, idigit = 0;
    12.     digit d;
    13.     while (str[istr]) istr++; istr--; // istr points to last character
    14.     while (istr >= 0) // get all chars from last back to first
    15.     {
    16.         d = 0;
    17.         // each char will store a 4 bit number
    18.         // so, a digit equals to 2*sizeof(digit) chars
    19.         for (i=0;i<2*sizeof(digit);i++)
    20.         {
    21.             d |= HexCharToDigit(str[istr]) << (4*i);
    22.             if (--istr < 0) break;
    23.         }
    24.         m_arrDigit[idigit++] = d;
    25.     }
    26.     return *this;
    27. }

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Mặc định int CNumber::ToString(char *str)

    C++ Code:
    1. int CNumber::ToString(char *str)
    2. {
    3.     char HexChar[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    4.     int idigit = DIGIT_NUMBER-1, i, j;
    5.    
    6.     // set idigit points to first nonzero digit
    7.     while (idigit && !m_arrDigit[idigit]) idigit--;
    8.     idigit++;
    9.    
    10.     // str will store idigit digits = 2*sizeof(digit)*idigit characters
    11.     char *p = str + 2*sizeof(digit)*idigit;
    12.     *p = '\0'; // null character of string
    13.     p--;
    14.  
    15.     digit d;
    16.     for (i=0;i<idigit;i++)
    17.     {
    18.         d = m_arrDigit[i];
    19.         for (j=0;j<2*sizeof(digit);j++)
    20.         {          
    21.             *p = HexChar[d & 0x0F]; // *p = hex char of d's last 4 bit
    22.             d >>= 4; p--;
    23.         }
    24.     }
    25.  
    26.     return 2*sizeof(digit)*idigit; // return str'length
    27. }

    Tạm thế này đã, em đã cung cấp đủ các method để các bác import hoặc export giá trị cho lớp này (thuận tiện cho việc test các toán tử toán học). Chờ các bác góp ý rồi em viết thêm.

  10. #10
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    số 4. chỉ là vấn đề quan điểm, nếu bạn vẫn quyết định clear thì cũng không thành vấn đề

    tiếp tục nhé:

    5. bạn phí 1 phép nhân trong const CNumber & CNumber::operator =(const CNumber &num)
    DIGIT_NUMBER*sizeof(digit)) ~ sizeof(m_arrDigit)

    6. nếu typef unsigned long digit; thì
    C++ Code:
    1. const CNumber & CNumber::operator = (int num) nên được thay là :
    2. const CNumber & CNumber::operator = (long num)
    3. và phần hiện thực rất đơn giản
    4. {
    5.     m_arrDigit[0] = num;
    6.     return (*this);
    7. }

    7. hình như bạn thiếu thuộc tính dấu cho CNumber
    nên thêm property
    bool sign;
    vào lớp CNumber

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

  1. SoiKeo.com - Cùng STIP sôi động cùng EURO 2012
    Gửi bởi phuthanh7777 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 14
    Bài viết cuối: 15-05-2012, 07:46 AM
  2. ADO.NET Bị lỗi thực hiện câu lệnh update khi nhiều luồng cùng chạy câu lệnh cùng một lúc
    Gửi bởi tuandoi1 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 6
    Bài viết cuối: 20-07-2011, 06:51 PM
  3. Cách hiển thị các Sản phẩm cùng thể loại, và các tin cùng chủ đề
    Gửi bởi pvtam2a trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 6
    Bài viết cuối: 14-05-2011, 12:52 AM
  4. Khi Việt Nam là một siêu cường [Cùng uống Fristy - Cùng tưởng tượng]
    Gửi bởi thansautk trong diễn đàn Giải trí - Thư giãn
    Trả lời: 0
    Bài viết cuối: 30-08-2010, 10:41 PM
  5. Lập trình âm thanh trên C# | Chạy cùng lúc 2 sound player trên cùng 1 form???
    Gửi bởi KingOfBlade trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 5
    Bài viết cuối: 11-05-2009, 10:19 AM

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