Tôi có một chuỗi có độ dài tùy ý biểu thị giá trị số thập phân và chuyển chuỗi này thành số nguyên lớn ở định dạng nhị phân đơn thuần (không phải BCD, hơn 64 bit).Tôi cần có bao nhiêu byte để giữ N chữ số thập phân
Tôi đang tìm kiếm một ước tính đơn giản, có bao nhiêu byte sẽ giữ N chữ số thập phân cho chắc chắn mà không cần sử dụng dấu chấm động.
Nếu không sử dụng dấu chấm động số học: Đối với N chữ số thập phân, bạn cần
(98981 * N)/238370 + 1
byte. 98981/238370 là một xấp xỉ hợp lý tốt (từ trên) đến log(10)/log(256) (số 9 thứ hội tụ), cắt phân chia số nguyên, do đó thêm 1. Công thức là chặt chẽ cho N < 238370, số byte cần thiết để đại diện cho 10^N - 1 rằng, nó đánh giá cao cho N một bội số của 238370 và thực sự lớnN. Nếu bạn không quá phân bổ byte lẻ quá nhiều, bạn cũng có thể sử dụng (267 * N)/643 + 1, (49 * N)/118 + 1, (5 * N)/12 + 1 hoặc lãng phí khoảng 10% không gian, (N + 1)/2.
Như @Henrick Hellström chỉ ra, trong Delphi người ta sẽ phải sử dụng toán tử div để phân chia số nguyên (bỏ thẻ delphi).
Để rõ ràng, toán tử/sẽ dẫn đến một phân chia dấu phẩy động. Sử dụng toán tử div. –
Bạn có thể tìm kiếm fixed point arithmetic
Giá trị lớn nhất của một loại điểm cố định chỉ đơn giản là giá trị lớn nhất có thể được biểu diễn trong các loại nguyên cơ bản, nhân các yếu tố rộng; và tương tự cho giá trị tối thiểu. Ví dụ, xem xét một loại điểm cố định được biểu diễn dưới dạng số nhị phân với bit b trong định dạng bổ sung của hai, với hệ số tỷ lệ của 1/2f (nghĩa là, bit cuối cùng là bit phân số): tối thiểu thể hiện giá trị là −2b-1/2f và giá trị lớn nhất là (2b-1-1)/2f.
Bạn cần nhiều bit này: ceil(N/log10(2)). Làm tròn đến bội số tiếp theo của 8, tức là, ceil((N/log10(2))/8)+1 byte.
Tôi sẽ thêm một bit an toàn vào tài khoản để làm tròn lỗi. – CodesInChaos
Không có số học dấu phẩy động: kể từ log10 (2) = ~ 3.3, bạn chỉ có thể tính toán 'N * 3.5/8 = (N * 3 + N/2)/8'. @CodeInChaos: 'ceil' là nghĩa vụ phải làm tròn lên. Trong mọi trường hợp, công thức chỉ số nguyên sẽ đánh giá quá cao. – zvrba
Tôi nghĩ rằng một ước tính đơn giản có thể dựa trên thực tế là 10 bit giữ 3 chữ số thập phân cho chắc chắn. – kludg
((size_t)ceil(N/log10(2)) + CHAR_BIT - 1)/CHAR_BIT
Bây giờ, 1/log10(2) ~ = 3.32 có thể xấp xỉ như 10.0/3 = 3.3(3).
Vì vậy, không có điểm động, nó sẽ có tối đa là (((size_t)N*10+2)/3 + CHAR_BIT - 1)/CHAR_BIT C byte.
Xem phần tràn khi N lớn.
1) Thư viện int lớn của bạn có chức năng 'Length' không? 2) Tại sao bạn muốn tránh điểm nổi? – CodesInChaos
Nó sẽ phụ thuộc vào cách nó được lưu trữ. Đối với mã hóa chuẩn, mỗi chữ số sử dụng 4 bit, vì vậy nBytes = (nDigits + 1)/2. Bạn cũng nên xem xét sử dụng nén, ngay cả trong bộ nhớ nén, với một số thuật toán nhanh. Tỷ lệ sẽ khác nhau, nhưng bạn sẽ tiết kiệm không gian cho chắc chắn. Xem thêm liệu dữ liệu của bạn có thể có một số mẫu hay không, như lưu trữ đồng bằng giữa các giá trị (sau khi sắp xếp, ví dụ), điều này thậm chí sẽ tăng cường nén hơn. –