Tôi nên sử dụng cấu trúc dữ liệu nào để tạo lớp "BigInteger" của riêng mình?

Question

Là bài tập tùy chọn, tôi đang nghĩ đến việc viết bài thực hành của riêng mình cho lớp BigInteger, nơi tôi sẽ cung cấp các phương pháp riêng để cộng, trừ, nhân, v.v.

Điều này sẽ dành cho số nguyên dài tùy ý, thậm chí hàng trăm chữ số.

Trong khi thực hiện toán học về các con số này, chữ số theo chữ số không khó, bạn nghĩ cơ sở hạ tầng nào tốt nhất sẽ đại diện cho "BigInteger" của tôi?

Lúc đầu, tôi đã xem xét sử dụng một mảng nhưng sau đó tôi đã nghĩ rằng tôi vẫn có khả năng tràn (hết các vùng mảng) sau khi thêm hoặc nhân lớn. Đây có phải là một trường hợp tốt để sử dụng một danh sách liên kết, kể từ khi tôi có thể tack trên chữ số với O (1) thời gian phức tạp?

Có cấu trúc dữ liệu nào khác phù hợp hơn một danh sách được liên kết không? Loại dữ liệu mà cấu trúc dữ liệu của tôi có phải là loại số nguyên nhỏ nhất có thể mà tôi có sẵn cho tôi không?

Ngoài ra, tôi có nên cẩn thận về cách lưu trữ biến "carry" của mình không? Nên nó, chính nó, là loại "BigInteger" của tôi?

Answer 1

Tôi sẽ nói một mảng int.

Answer 2

tôi sẽ nói một std :: vector của char (vì nó có chỉ 0-9 giữ) (nếu bạn có kế hoạch làm việc trong BCD)

Nếu không BCD sau đó sử dụng vector của int (bạn didnt làm nó rõ ràng)

ít nhiều không gian trên cao liên kết danh sách

Và tất cả những lời khuyên nói 'vector sử dụng trừ khi bạn có lý do chính đáng không phải là quá'

Answer 3

một mảng thực sự là một sự phù hợp tự nhiên. Tôi nghĩ rằng nó có thể chấp nhận để ném OverflowException, khi bạn chạy ra khỏi vị trí trong bộ nhớ của bạn. Giáo viên sẽ chú ý đến từng chi tiết.

Nhân giống gần gấp đôi số chữ số, số tăng thêm tối đa là 1. Dễ dàng tạo một mảng đủ lớn để lưu trữ kết quả hoạt động của bạn.

Việc mang theo nhiều nhất là một số có một chữ số trong phép nhân (9 * 9 = 1, mang 8). Một int sẽ làm.

Answer 4

Luôn sử dụng loại int nhỏ nhất sẽ thực hiện công việc bạn cần (byte). Danh sách được liên kết sẽ hoạt động tốt vì bạn sẽ không phải lo lắng về việc bị tràn.

Answer 5

Kiểm tra sách C Interfaces and Implementations của David R. Hanson. Nó có 2 chương về chủ đề, bao gồm cấu trúc vectơ, kích thước chữ và nhiều vấn đề khác mà bạn có thể gặp phải.

Nó được viết cho C, nhưng hầu hết đều được áp dụng cho C++ và/hoặc Java. Và nếu bạn sử dụng C++ nó sẽ đơn giản hơn một chút bởi vì bạn có thể sử dụng một cái gì đó như std::vector để quản lý việc phân bổ mảng cho bạn.

Answer 6

Nếu bạn sử dụng cây nhị phân (có lá là int), bạn sẽ có được tất cả ưu điểm của danh sách được liên kết (số chữ số không bị chặn, vv) với thuật toán phân chia và conquer đơn giản hơn. Bạn không có trong trường hợp này một cơ sở duy nhất nhưng nhiều tùy thuộc vào mức độ mà bạn đang làm việc.

Nếu bạn thực hiện việc này, bạn cần sử dụng BigInteger để thực hiện.Bạn có thể coi nó là một lợi thế của phương pháp "liên kết danh sách ints" mà carry có thể luôn được biểu diễn dưới dạng int (và điều này đúng với bất kỳ cơ sở nào, không chỉ cho cơ sở 10 vì hầu hết các câu trả lời dường như giả định rằng bạn nên sử dụng. .. Trong bất kỳ cơ sở nào, việc mang luôn luôn là một chữ số)

Tôi cũng có thể nói rằng: nó sẽ là một sự lãng phí khủng khiếp khi sử dụng cơ sở 10 khi bạn có thể sử dụng 2^30 hoặc 2^31.

Answer 7

Truy cập các yếu tố của danh sách được liên kết chậm. Tôi nghĩ rằng mảng là con đường để đi, với rất nhiều ràng buộc kiểm tra và chạy thời gian thay đổi kích thước mảng khi cần thiết.

---

Làm rõ: Vượt qua một danh sách liên kết và vượt qua một mảng đều O (n ) hoạt động. Nhưng việc duyệt qua danh sách được liên kết yêu cầu deferencing một con trỏ ở mỗi bước. Chỉ vì hai thuật toán đều có cùng độ phức tạp nên không có nghĩa là cả hai đều chạy cùng một lúc. Chi phí phân bổ và deallocating các nút n trong danh sách được liên kết cũng sẽ nặng hơn nhiều so với quản lý bộ nhớ của một mảng có kích thước n, ngay cả khi mảng đã được thay đổi kích thước vài lần.

Answer 8

std::vector<bool> hoặc std::vector<unsigned int> có lẽ là những gì bạn muốn. Bạn sẽ phải push_back() hoặc resize() trên chúng khi bạn cần nhiều không gian hơn cho nhân, v.v. Ngoài ra, hãy nhớ push_back các bit dấu chính xác nếu bạn đang sử dụng hai lời khen.

Answer 9

Theo quy tắc chung, hãy sử dụng std::vector thay vì std::list, trừ khi bạn cần chèn phần tử vào giữa chuỗi rất thường xuyên. Vectơ có xu hướng nhanh hơn, vì chúng được lưu trữ liên tục và do đó được hưởng lợi từ địa phương không gian tốt hơn (một yếu tố hiệu suất chính trên nền tảng hiện đại).

Đảm bảo bạn sử dụng các yếu tố tự nhiên cho nền tảng. Nếu bạn muốn là nền tảng độc lập, hãy sử dụng long. Hãy nhớ rằng trừ khi bạn có một số trình biên dịch nội tại đặc biệt có sẵn, bạn sẽ cần một loại ít nhất hai lần lớn để thực hiện phép nhân.

Tôi không hiểu tại sao bạn muốn mang theo số nguyên lớn. Carry là một bit để bổ sung và kích thước phần tử cho phép nhân.

Đảm bảo rằng bạn đã đọc Nghệ thuật lập trình máy tính của Knuth, các thuật toán liên quan đến số học chính xác tùy ý được mô tả ở mức độ lớn.

Answer 10

Chà, có một số câu trả lời thú vị ở đây. Tôi khuyên bạn nên đọc một cuốn sách thay vì cố gắng sắp xếp thông qua tất cả các lời khuyên mâu thuẫn này.

Điều đó nói rằng, C/C++ cũng không phù hợp với tác vụ này. Big-integer là một loại toán học có độ chính xác mở rộng. Hầu hết các CPU cung cấp các hướng dẫn để xử lý phép toán mở rộng có độ chính xác ở tốc độ tương đương hoặc tương đương (bit trên mỗi lệnh) như toán học thông thường. Khi bạn thêm 2^32 + 2^32, câu trả lời là 0… nhưng cũng có một đầu ra mang đặc biệt từ ALU của bộ xử lý mà một chương trình có thể đọc và sử dụng.

C++ không thể truy cập cờ đó và cũng không có cách nào trong C. Bạn phải sử dụng assembler.

Chỉ để thỏa mãn sự tò mò, bạn có thể sử dụng số học Boolean chuẩn để phục hồi các bit mang theo vv Nhưng bạn sẽ tốt hơn khi tải xuống một thư viện hiện có.