Tôi đã tự hỏi loại phương pháp nào được sử dụng để nhân các số trong C++. Đó có phải là cuốn sách giáo khoa truyền thống dài? Fürer's algorithm? Toom-Cook?Làm cách nào để số nguyên nhân trong C++?
Tôi đã tự hỏi vì tôi sẽ cần nhân các số cực kỳ lớn và cần một mức độ hiệu quả cao. Do đó, sách giáo khoa truyền thống nhân dài O(n^2) có thể quá kém hiệu quả, và tôi sẽ cần phải sử dụng phương pháp nhân giống khác.
Vậy C++ sử dụng loại phép nhân nào?
Bạn dường như thiếu một vài điều quan trọng ở đây:
Để nhận được số học bignum (tùy ý), bạn cần tự mình thực hiện hoặc sử dụng thư viện. (chẳng hạn như GMP) Không giống như Java và C# (trong số những người khác), C++ không có thư viện cho phép tính số học chính xác tùy ý.
Tất cả những thuật toán ưa thích:
O(n^1.585)< O(n^1.465)~ O(n log(n))chỉ áp dụng đối với bignum số học được thực hiện trong thư viện bignum. Những gì bộ vi xử lý sử dụng cho các phép tính số học bản địa của nó có phần không liên quan vì nó là thường là thời gian không đổi.
Trong mọi trường hợp, tôi không khuyên bạn cố gắng triển khai thư viện bignum. Tôi đã thực hiện nó trước và nó khá đòi hỏi (đặc biệt là toán học). Vì vậy, bạn nên sử dụng thư viện tốt hơn.
+1 để đoán ý định của OP :-) – hirschhornsalz
Cho đến khi bạn nhận được số lượng rất lớn, phương pháp bạn học được ở trường cấp sẽ thực hiện tốt hơn trong thực tế. Tất nhiên bạn sử dụng một cơ sở lớn hơn 10.:-) Tùy thuộc vào nhu cầu của bạn, 2^32, 2^64 hoặc 10^9 tạo cơ sở thuận tiện (sức mạnh 10 hữu ích là phân tích cú pháp/in số của bạn trong cơ sở 10 là quan trọng để tối ưu hóa và 10^9 là công suất lớn nhất phù hợp với 32 bit). –
Tất cả phụ thuộc vào thư viện và trình biên dịch được sử dụng.
Trong phép nhân số nguyên C++ được xử lý bởi chip. Không có tương đương với BigNum của Perl trong ngôn ngữ chuẩn, mặc dù tôi chắc chắn rằng các thư viện đó tồn tại.
Để nitpick: Không nhất thiết. Hoàn toàn có thể thực hiện để bao gồm các kiểu số (thậm chí 'int', mặc dù * đó là khá hiếm) mà kiến trúc được nhắm mục tiêu không hỗ trợ, và thay vào đó thực hiện các phép tính số học trên chúng như các cuộc gọi vào một thư viện thời gian chạy. Xem xét các số nguyên 128 bit hoặc có thể là các số nguyên 64 bit trên các hệ thống 32 bit. Ngoài ra, có sử dụng nhiều chip mà không có đơn vị điểm động (FPU). – delnan
@delnan: Hiếm nhưng không tồn tại: bộ vi xử lý 8 bit 6502 không có hướng dẫn số học 16 bit, do đó trình biên dịch CC65 C phải triển khai số học 'int' thông qua chuỗi các lệnh 8 bit và các cuộc gọi thư viện. – han
Bạn có ý nghĩa gì với "số lượng cực lớn"?
C++, giống như hầu hết các ngôn ngữ lập trình khác, sử dụng phần cứng nhân được tích hợp trong bộ xử lý. Chính xác cách hoạt động không được chỉ định bằng ngôn ngữ C++. Nhưng đối với số nguyên bình thường và số dấu phẩy động, bạn sẽ không thể viết một cái gì đó nhanh hơn trong phần mềm.
Những con số lớn nhất có thể được thể hiện bằng các kiểu dữ liệu khác nhau có thể khác nhau giữa hiện thực khác nhau, nhưng một số giá trị điển hình là 2147483647 cho int, 9223372036854775807 cho dài và 1.79769e + 308 cho đôi.
Nó được thực hiện bằng phần cứng. cho cùng một lý do số lượng lớn sẽ không hoạt động. Số lớn nhất C++ có thể đại diện cho phần cứng 64 bit là 18446744073709551616. nếu bạn cần số lớn hơn, bạn cần một thư viện chính xác tùy ý.
Điều gì về tăng gấp đôi? Bên cạnh đó, kích thước chính xác của hầu hết các kiểu dữ liệu là tùy thuộc vào trình biên dịch. Tôi cũng tin rằng một số trình biên dịch cung cấp các loại số nguyên 128 bit. – delnan
đồng bằng C++ sử dụng hướng dẫn CPU mult (hoặc sách giáo khoa nhân sử dụng bitshifts và bổ sung nếu CPU của bạn không có một lệnh như vậy.)
nếu bạn cần nhân nhanh cho số lượng lớn, tôi sẽ đề nghị xem xét gmp (http://gmplib.org) và sử dụng C++ giao diện từ gmpxx.h
Nếu bạn làm việc với một số lượng lớn các nhân nguyên tiêu chuẩn trong C++ sẽ không còn làm việc và bạn nên sử dụng một thư viện cung cấp tùy ý nhân chính xác, như GMP http://gmplib.org/
Ngoài ra, bạn không nên lo lắng về hiệu suất trước khi viết ứng dụng của bạn (= tối ưu hóa sớm). Những phép nhân này sẽ nhanh chóng và rất có thể nhiều thành phần khác trong phần mềm của bạn sẽ làm chậm hơn nhiều.
Các con số này sẽ lớn tới mức nào? Ngay cả các ngôn ngữ như python cũng có thể thực hiện 1e100*1e100 với các số nguyên chính xác tùy ý trên 3 triệu lần một giây trên một bộ xử lý chuẩn. Đó là phép nhân với 100 địa điểm quan trọng chỉ mất chưa đến một phần triệu giây. Để đưa vào bối cảnh, chỉ có khoảng 10^80 nguyên tử trong vũ trụ quan sát được.
Viết nội dung bạn muốn đạt được trước và tối ưu hóa sau nếu cần.
Bất kể chip nào cũng vậy. – bmargulies
Tiêu đề khiến tôi nghĩ về số nguyên sao chép :) – harold
@harold Đầu tiên, họ phải làm một cái gì đó gọi là "hẹn hò". – Manish