Số học điểm cố định trong Lập trình C

Question

Tôi đang cố gắng tạo một ứng dụng lưu trữ giá cổ phiếu với độ chính xác cao. Hiện tại tôi đang sử dụng một đôi để làm như vậy. Để tiết kiệm bộ nhớ, tôi có thể sử dụng bất kỳ loại dữ liệu nào khác không? Tôi biết điều này có một cái gì đó để làm với số học điểm cố định, nhưng tôi không thể tìm ra nó.

Answer 1

Ý tưởng đằng sau số học điểm cố định là bạn lưu trữ các giá trị nhân với một số tiền nhất định, sử dụng giá trị nhân cho tất cả phép tính và chia cho cùng một số tiền khi bạn muốn kết quả. Mục đích của kỹ thuật này là sử dụng số học số nguyên (int, long ...) trong khi có thể biểu diễn các phân số.

Cách thông thường và hiệu quả nhất để thực hiện điều này trong C là sử dụng toán tử dịch chuyển bit (< < và >>).Chuyển bit là một hoạt động khá đơn giản và nhanh chóng cho ALU và làm điều này có thuộc tính nhân (< <) và chia (>>) giá trị số nguyên cho 2 trên mỗi ca (bên cạnh đó, nhiều ca có thể được thực hiện cho chính xác giá của một đơn). Tất nhiên, nhược điểm là hệ số nhân phải là một lũy thừa của 2 (thường không phải là vấn đề bởi chính chúng ta không thực sự quan tâm đến giá trị số nhân chính xác đó).

Bây giờ, giả sử chúng tôi muốn sử dụng các số nguyên 32 bit để lưu trữ các giá trị của chúng tôi. Chúng ta phải chọn một sức mạnh của 2 nhân. Hãy chia bánh thành hai, vì vậy hãy nói 65536 (đây là trường hợp phổ biến nhất, nhưng bạn thực sự có thể sử dụng bất kỳ sức mạnh nào của 2 tùy theo nhu cầu của bạn về độ chính xác). Đây là 2 và 16 ở đây có nghĩa là chúng ta sẽ sử dụng 16 bit quan trọng nhất (LSB) cho phần phân đoạn. Phần còn lại (32 - 16 = 16) là số bit quan trọng nhất (MSB), phần nguyên.

 integer (MSB) fraction (LSB) 
      v     v 
    0000000000000000.0000000000000000 

Hãy đặt này trong mã:

#define SHIFT_AMOUNT 16 // 2^16 = 65536 
#define SHIFT_MASK ((1 << SHIFT_AMOUNT) - 1) // 65535 (all LSB set, all MSB clear) 

int price = 500 << SHIFT_AMOUNT; 

Đây là giá trị bạn phải đặt tại cửa hàng (cấu trúc, cơ sở dữ liệu, bất cứ điều gì). Lưu ý rằng int không nhất thiết phải là 32 bit trong C mặc dù nó chủ yếu là trường hợp ngày nay. Cũng không cần khai báo thêm, nó được ký theo mặc định. Bạn có thể thêm unsigned vào khai báo để chắc chắn. Tốt hơn thế, bạn có thể sử dụng uint32_t hoặc uint_least32_t (được khai báo trong stdint.h) nếu mã của bạn rất phụ thuộc vào kích thước bit nguyên (bạn có thể giới thiệu một số hacks về nó). Nghi ngờ, sử dụng typedef cho loại điểm cố định của bạn và bạn an toàn hơn.

Khi bạn muốn thực hiện phép tính trên giá trị này, bạn có thể sử dụng 4 toán tử cơ bản: +, -, * và /. Bạn phải ghi nhớ rằng khi cộng và trừ một giá trị (+ và -), giá trị đó cũng phải được dịch chuyển. Giả sử chúng tôi muốn thêm 10 vào giá 500 của chúng tôi:

price += 10 << SHIFT_AMOUNT; 

Nhưng để nhân và chia (* và /), hệ số nhân/số chia không được dịch chuyển. Hãy nói rằng chúng tôi muốn nhân với 3:

price *= 3; 

Bây giờ chúng ta hãy làm cho mọi việc thú vị hơn bằng cách chia giá bởi 4 vì vậy chúng tôi bù đắp cho một tổ chức phi zero phần phân đoạn:

price /= 4; // now our price is ((500 + 10) * 3)/4 = 382.5 

Đó là tất cả về các quy tắc. Khi bạn muốn lấy giá thực tế tại thời điểm bất kỳ, bạn phải phải thay đổi:

printf("price integer is %d\n", price >> SHIFT_AMOUNT); 

Nếu bạn cần các phần phân đoạn, bạn phải che giấu nó ra:

printf ("price fraction is %d\n", price & SHIFT_MASK); 

Tất nhiên, giá trị này không phải là những gì chúng ta có thể gọi một phần thập phân, trên thực tế nó là một số nguyên trong phạm vi [0 - 65535]. Nhưng nó ánh xạ chính xác với phạm vi phân số thập phân [0 - 0.9999 ...]. Nói cách khác, ánh xạ trông giống như: 0 => 0, 32768 => 0,5, 65535 => 0,9999 ...

Một cách dễ dàng để xem nó như là một phần thập phân là phải nhờ đến C built-in số học nổi vào thời điểm này:

printf("price fraction in decimal is %f\n", ((double)(price & SHIFT_MASK)/(1 << SHIFT_AMOUNT))); 

Nhưng nếu bạn không có hỗ trợ FPU (hoặc phần cứng hoặc phần mềm) , bạn có thể sử dụng các kỹ năng mới của mình như thế này để biết giá đầy đủ:

printf("price is roughly %d.%lld\n", price >> SHIFT_AMOUNT, (long long)(price & SHIFT_MASK) * 100000/(1 << SHIFT_AMOUNT)); 

Số lượng 0 trong biểu thức xấp xỉ số chữ số bạn muốn sau dấu thập phân. Đừng đánh giá quá cao số 0 cho độ chính xác phân số của bạn (không có cái bẫy thực sự ở đây, điều đó khá rõ ràng). Không sử dụng đơn giản miễn là sizeof (long) có thể bằng sizeof (int). Sử dụng dài dài trong trường hợp int là 32 bit là dài dài được đảm bảo tối thiểu 64 bit (hoặc sử dụng int64_t, int_least64_t và như vậy, được khai báo trong stdint.h). Nói cách khác, hãy sử dụng loại gấp hai lần kích thước của loại điểm cố định của bạn, điều đó đủ công bằng. Cuối cùng, nếu bạn không có quyền truy cập vào các loại> 64 bit, có thể đã đến lúc tập luyện để mô phỏng chúng, ít nhất là cho đầu ra của bạn.

Đây là những ý tưởng cơ bản đằng sau arithmetics điểm cố định.

Hãy cẩn thận với các giá trị âm. Đôi khi nó có thể trở nên phức tạp, nhất là khi đến lúc hiển thị giá trị cuối cùng. Bên cạnh đó, C được thực hiện xác định về số nguyên đã ký (mặc dù nền tảng mà đây là một vấn đề rất phổ biến hiện nay). Bạn nên luôn thực hiện các bài kiểm tra tối thiểu trong môi trường của mình để đảm bảo mọi thứ diễn ra như mong đợi. Nếu không, bạn có thể hack xung quanh nó nếu bạn biết những gì bạn làm (tôi sẽ không phát triển về điều này, nhưng điều này có một cái gì đó để làm với sự thay đổi số học vs thay đổi hợp lý và đại diện bổ sung 2). Tuy nhiên, với số nguyên chưa được ký, bạn hầu như an toàn dù bạn làm gì vì hành vi cũng được xác định rõ.

Ngoài ra hãy lưu ý rằng nếu một số nguyên 32 bit không thể đại diện giá trị lớn hơn 2 -1, sử dụng cố định điểm số học với 2 giới hạn phạm vi của bạn để 2 -1! (và chia tất cả điều này cho 2 với các số nguyên đã ký, trong ví dụ của chúng tôi sẽ để lại cho chúng tôi phạm vi có sẵn là 2 - 1). Mục tiêu là sau đó chọn SHIFT_AMOUNT phù hợp với tình huống. Đây là một sự cân bằng giữa độ lớn phần nguyên và độ chính xác phần phân đoạn.

Bây giờ cho cảnh báo thực sự: kỹ thuật này chắc chắn không phù hợp ở những khu vực có độ chính xác cao (tài chính, khoa học, quân sự ...). Điểm nổi thông thường (float/double) cũng thường không đủ chính xác, mặc dù chúng có các thuộc tính tốt hơn so với tổng điểm cố định. Điểm cố định có cùng độ chính xác bất kỳ giá trị nào (điều này có thể là lợi thế trong một số trường hợp), khi độ chính xác nổi tỷ lệ nghịch với giá trị độ lớn (nghĩa là độ lớn càng thấp, độ chính xác càng cao ... tốt, điều này phức tạp hơn thế nhưng bạn có được điểm). Ngoài ra phao có độ lớn lớn hơn số nguyên tương đương (số bit) (điểm cố định hoặc không), với chi phí mất chính xác với giá trị cao (thậm chí bạn có thể đạt đến một điểm lớn khi thêm 1 hoặc thậm chí giá trị lớn hơn sẽ không có tác dụng gì cả, cái gì đó không thể xảy ra với số nguyên).

Nếu bạn làm việc trong những khu vực hợp lý, bạn nên sử dụng thư viện dành riêng cho mục đích chính xác tùy ý (đi xem gmplib, miễn phí). Trong khoa học máy tính, về cơ bản, đạt được độ chính xác là về số bit bạn sử dụng để lưu trữ các giá trị của mình. Bạn muốn độ chính xác cao? Sử dụng bit. Đó là tất cả.

Answer 2

Tôi sẽ không khuyên bạn nên làm như vậy, nếu mục đích duy nhất của bạn là để tiết kiệm bộ nhớ. Các lỗi trong việc tính giá có thể được tích lũy và bạn sẽ vít lên trên nó.

Nếu bạn thực sự muốn triển khai nội dung tương tự, bạn có thể chỉ mất khoảng thời gian tối thiểu của giá và sau đó trực tiếp sử dụng hoạt động int và số nguyên để thao tác số của bạn không? Bạn chỉ cần chuyển đổi nó thành số dấu phẩy động khi hiển thị, điều này giúp cuộc sống của bạn dễ dàng hơn.

Answer 3

Tôi thấy hai tùy chọn cho bạn. Nếu bạn đang làm việc trong ngành dịch vụ tài chính, có lẽ các tiêu chuẩn mà mã của bạn phải tuân thủ chính xác và chính xác, vì vậy bạn sẽ phải đi cùng với điều đó, bất kể chi phí bộ nhớ. Tôi hiểu rằng doanh nghiệp đó thường được tài trợ tốt, vì vậy việc trả tiền cho nhiều bộ nhớ hơn không phải là vấn đề. :)

Nếu điều này là để sử dụng cá nhân, sau đó cho độ chính xác tối đa tôi khuyên bạn nên sử dụng số nguyên và nhân tất cả giá bởi một yếu tố cố định trước khi lưu trữ. Ví dụ: nếu bạn muốn mọi thứ chính xác với đồng xu (có thể không đủ tốt), hãy nhân tất cả giá với 100 để đơn vị của bạn có hiệu quả là cent thay vì đô la và chuyển từ đó. Nếu bạn muốn chính xác hơn, nhân với nhiều hơn. Ví dụ, để được chính xác đến hàng trăm của một xu (một tiêu chuẩn mà tôi đã nghe nói thường được áp dụng), nhân giá 10.000 (100 * 100).

Bây giờ với các số nguyên 32 bit, nhân với 10000 để lại ít chỗ cho số lượng lớn đô la. Giới hạn 32 bit thực tế là 2 tỷ đồng có nghĩa là chỉ có mức giá cao là 20000 đô la mới có thể được thể hiện: 2000000000/10000 = 20000. Điều này sẽ trở nên tệ hơn nếu bạn nhân số 20000 đó bởi vì có thể không có chỗ để giữ kết quả. Vì lý do này, tôi khuyên bạn nên sử dụng số nguyên 64 bit (long long). Ngay cả khi bạn nhân tất cả giá với 10000, vẫn còn rất nhiều khoảng không để giữ các giá trị lớn, thậm chí trên các phép nhân.

Bí quyết với điểm cố định là bất cứ khi nào bạn tính toán, bạn cần phải nhớ rằng mỗi giá trị thực sự là một giá trị cơ bản nhân với một hằng số. Trước khi bạn cộng hoặc trừ, bạn cần nhân các giá trị với một hằng số nhỏ hơn để khớp với các giá trị có hằng số lớn hơn. Sau khi bạn nhân, bạn cần chia cho một cái gì đó để có được kết quả trở lại được nhân với hằng số mong muốn. Nếu bạn sử dụng một sức mạnh không phải là hai là hằng số của bạn, bạn sẽ phải làm một số nguyên phân chia, đó là tốn kém, thời gian khôn ngoan. Nhiều người sử dụng quyền hạn của hai như hằng số của họ, vì vậy họ có thể thay đổi thay vì chia.

Nếu tất cả điều này có vẻ phức tạp, đúng vậy. Tôi nghĩ tùy chọn đơn giản nhất là sử dụng gấp đôi và mua thêm RAM nếu bạn cần. Chúng có 53 bit chính xác, xấp xỉ 9 nghìn tỷ, hay gần 16 chữ số thập phân. Có, bạn vẫn có thể mất đồng xu khi bạn đang làm việc với hàng tỷ, nhưng nếu bạn quan tâm về điều đó, bạn không phải là một tỷ phú đúng cách. :)