Máy tính đánh giá số lượng lớn như thế nào?

Question

Nếu tôi nhập một giá trị, ví dụ 1234567^98787878 vào Wolfram Alpha, nó có thể cung cấp cho tôi một số chi tiết. Điều này bao gồm xấp xỉ thập phân, tổng chiều dài, chữ số cuối cùng vv Làm thế nào để bạn đánh giá số lượng lớn như vậy? Theo tôi hiểu nó một ngôn ngữ lập trình sẽ phải có một kiểu dữ liệu đặc biệt để lưu trữ số, hãy để một mình thêm nó vào cái gì khác. Trong khi tôi có thể thấy làm thế nào người ta có thể tiếp cận việc bổ sung hai con số rất lớn, tôi không thể thấy những con số khổng lồ được đánh giá như thế nào.

10^2 có thể được tính toán thông qua việc thêm lặp lại. Tuy nhiên một số như ví dụ trên sẽ yêu cầu một vòng lặp khổng lồ. Ai đó có thể giải thích làm thế nào số lượng lớn như vậy được đánh giá? Ngoài ra, làm thế nào có thể ai đó tạo ra một kiểu dữ liệu lớn tùy chỉnh để hỗ trợ số lượng lớn trong C# ví dụ?

Answer 1

Vâng nó khá dễ dàng và bạn có thể đã làm điều đó cho mình

1. Số chữ số có thể thu được qua logarit:

   từ A^B = 10^(B * log(A, 10))

   chúng ta có thể tính toán (A = 1234567; B = 98787878) trong trường hợp của chúng tôi là

   B * log(A, 10)=98787878 * log(1234567, 10)=601767807.4709646...

   integer part + 1(601767807 + 1 =) là số chữ số

2. Đầu tiên, nói, lăm, chữ số cũng có thể nhận được qua lôgarit; bây giờ chúng ta nên phân tích phần phân đoạn của

   B * log(A, 10)=98787878 * log(1234567, 10)=601767807.4709646...

   f = 0.4709646...

   chữ số đầu tiên được 10^f (dấu thập phân bị loại bỏ) = 29.577 ...

3. cuối, nói, lăm, chữ số có thể thu được như một còn lại tương ứng:

   năm chữ số cuối cùng = A^B rem 10^5

   A rem 10^5=1234567 rem 10^5= `34567

   A^B rem 10^5 **=** ((Một rem 10^5)^B) rem 10^5 **=** (34567^98787878) rem 10^5 = 45009`

   năm chữ số cuối cùng là

   Bạn có thể tìm BigInteger.ModPow (C#) rất hữu ích ở đây

Cuối cùng

1234567^98787878 = 29577 ... 45.009 (601.767.808 chữ số)

Answer 2

Thường có các thư viện cung cấp kiểu dữ liệu bignum cho số nguyên lớn tùy ý (ví dụ: số bản đồ k*n...(k+1)*n-1, k=0..<some m depending on n and number magnitude> cho từ máy có kích thước n xác định lại hoạt động số học). đối với C#, bạn có thể quan tâm đến BigInteger.

lũy thừa có thể được đệ quy chia nhỏ:

pow(a,2*b) = pow(a,b) * pow(a,b); 
pow(a,2*b+1) = pow(a,b) * pow(a,b) * a; 

cũng có kết quả số lý thuyết đã engenedered thuật toán đặc biệt để xác định tính chất của một số lượng lớn mà không thực sự tính toán họ (để được chính xác: mở rộng số thập phân đầy đủ của họ) .

Answer 3

Để tính toán có bao nhiêu chữ số có, người ta sử dụng các biểu thức sau đây:

decimal_digits(n) = 1 + floor(log_10(n)) 

Điều này cho phép:

decimal_digits(1234567^98787878) = 1 + floor(log_10(1234567^98787878)) 
           = 1 + floor(98787878 * log_10(1234567)) 
           = 1 + floor(98787878 * 6.0915146640862625) 
           = 1 + floor(601767807.4709647) 
           = 601767808 

Các trailing k chữ số được tính bằng cách làm lũy thừa mod 10^k, mà giữ cho kết quả trung gian không bao giờ trở nên quá lớn.

Tính xấp xỉ sẽ được tính bằng cách sử dụng phần mềm nổi (phần mềm) để đánh giá hiệu quả^(98787878 log_a (1234567)) cho một số độ chính xác cố định cho một số số làm cho số học hoạt động độc đáo (thường là 2 hoặc e hoặc 10). Điều này cũng tránh được sự cần thiết phải thực sự làm việc với hàng triệu chữ số tại bất kỳ thời điểm nào.

Answer 4

Tôi nghĩ một phần của câu trả lời nằm trong câu hỏi chính nó :) Để lưu trữ các biểu thức này, bạn có thể lưu trữ cơ sở (hoặc phần chú thích) và số mũ riêng biệt, như ký hiệu khoa học. Mở rộng đến đó, bạn không thể đánh giá hoàn toàn biểu thức và lưu trữ các số lớn như vậy, mặc dù, bạn có thể dự đoán về mặt lý thuyết các thuộc tính nhất định của biểu thức hậu quả. Tôi sẽ đưa bạn qua từng thuộc tính mà bạn đã nói về:

1. Ước tính thập phân: Có thể được tính bằng cách đánh giá các giá trị nhật ký đơn giản.
2. Tổng số chữ số biểu thức a^b, có thể được tính theo công thức Chữ số = hàm sàn (1 + Log10 (a^b)), trong đó hàm sàn là số nguyên gần nhất nhỏ hơn số. Ví dụ: số chữ số trong 10^5 là 6.
3. Chữ số cuối cùng: Những chữ số này có thể được tính theo thực tế là biểu thức của số mũ tăng tuyến tính tạo thành một tiến trình số học. Ví dụ: tại đơn vị; 7, 9, 3, 1 được lặp lại cho số mũ 7^x. Vì vậy, bạn có thể tính toán rằng nếu x% 4 bằng 0, chữ số cuối cùng là 1. Ai đó có thể tạo kiểu dữ liệu tùy chỉnh cho số lớn, tôi không thể nói, nhưng tôi chắc chắn, số sẽ không được đánh giá và lưu trữ .

Answer 5

Có rất nhiều thư viện cho điều này và khả năng là built-in trong trường hợp của python. Bạn dường như chủ yếu quan tâm đến kích thước của các con số như vậy và thời gian nó có thể làm để tính toán như số mũ trong ví dụ của bạn. Vì vậy, tôi sẽ giải thích một chút.

Đại diện Bạn có thể sử dụng một mảng để giữ tất cả các chữ số có số lượng lớn. Một cách hiệu quả hơn sẽ là sử dụng một mảng các số nguyên không dấu 32 bit và lưu trữ "các khối bit 32" của số lượng lớn. Bạn có thể nghĩ các đoạn này là các chữ số riêng lẻ trong một hệ thống số có 2^32 chữ số hoặc ký tự riêng biệt. Tôi đã sử dụng một mảng các byte để làm điều này trên một Atari800 8 bit trở lại trong ngày.

Làm toán Bạn rõ ràng có thể thêm hai số đó bằng cách lặp qua tất cả các chữ số và thêm yếu tố của một mảng sang người kia và theo dõi mang. Một khi bạn biết cách thêm, bạn có thể viết mã để làm phép nhân "bằng tay" bằng cách nhân các chữ số và đặt kết quả vào đúng chỗ và nhiều bổ sung - nhưng phần mềm sẽ làm tất cả điều này khá nhanh chóng. Có thuật toán nhân nhanh hơn so với thuật toán bạn sử dụng trên giấy. Phép nhân giấy là O (n^2) trong đó các phương thức khác là O (n * log (n)). Đối với số mũ, bạn có thể nhân tất nhiên nhân với cùng một số hàng triệu lần nhưng mỗi số nhân đó sẽ sử dụng hàm đã đề cập trước đây để thực hiện phép nhân. Có những cách nhanh hơn để thực hiện lũy thừa yêu cầu nhân ít hơn nhiều. Ví dụ bạn có thể tính x^16 bằng cách tính toán (((x^2)^2)^2)^2 chỉ liên quan đến 4 số thực (số nguyên lớn).

Trong thực tế Thật thú vị và giáo dục để tự mình viết các hàm này, nhưng trong thực tế, bạn sẽ muốn sử dụng thư viện hiện có đã được tối ưu hóa và xác minh.