C 프로그래밍의 고정점 연산

C 프로그래밍의 고정점 연산

저는 주가를 고정밀로 저장하는 앱을 만들려고 합니다.현재 저는 그렇게 하기 위해 더블을 사용하고 있습니다.메모리를 절약하기 위해 다른 데이터 유형을 사용할 수 있습니까?이것이 고정 소수점 연산과 관련이 있다는 것을 알지만, 저는 그것을 알아낼 수 없습니다.

고정점 산술의 개념은 값에 일정량을 곱한 값을 저장하고, 모든 미적분에 곱한 값을 사용하고, 결과를 원할 때 같은 양으로 나눈다는 것입니다.이 기법의 목적은 분수를 나타낼 수 있는 동안 정수 산술(int, long...)을 사용하는 것입니다.

C에서 이를 수행하는 일반적이고 가장 효율적인 방법은 비트 이동 연산자(< 및 >>)를 사용하는 것입니다.비트 이동은 ALU에 매우 간단하고 빠른 작업이며, 이 작업은 각 시프트에서 정수 값을 2로 곱(<)하고 나눗셈(>)하는 특성이 있습니다(게다가 많은 이동은 단일의 정확한 가격으로 수행될 수 있습니다).물론, 단점은 승수가 2의 거듭제곱이어야 한다는 것입니다(일반적으로 정확한 승수 값은 신경 쓰지 않으므로 그 자체로는 문제가 되지 않습니다).

이제 32비트 정수를 사용하여 값을 저장하려고 합니다.우리는 2 곱하기의 거듭제곱을 선택해야 합니다.케이크를 둘로 나누자, 65536이라고 하자 (이것은 가장 일반적인 경우이지만, 당신은 정말로 당신의 필요에 따라 2의 어떤 거듭제곱도 사용할 수 있습니다).이것은 2이고¹⁶ 여기서 16은 분수 부분에 16개의 최하위 비트(LSB)를 사용한다는 것을 의미합니다.나머지(32 - 16 = 16)는 정수 부분인 최상위 비트(MSB)에 대한 것입니다.

     integer (MSB)    fraction (LSB)
           v                 v
    0000000000000000.0000000000000000

코드로 입력해 보겠습니다.

#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;

이 값은 저장해야 하는 값입니다(구조, 데이터베이스 등).참고로 요즘은 대부분이지만 int가 반드시 C에서 32비트는 아닙니다.또한 추가 선언 없이 기본적으로 서명됩니다.서명되지 않은 항목을 선언에 추가하여 확인할 수 있습니다.그보다 더 나은 것은 코드가 정수 비트 크기에 크게 의존하는 경우 unt32_t 또는 uint_list32_t(stdint.h로 선언됨)를 사용할 수 있다는 것입니다.확실하지 않은 것은 고정점 유형에 typedef를 사용하면 안전하다는 것입니다.

이 값에 대해 미적분을 수행하려면 +, -, * 및 /의 4가지 기본 연산자를 사용할 수 있습니다.값(+ 및 -)을 추가하거나 뺄 때는 해당 값도 이동해야 합니다.500개 가격에 10개를 추가하고 싶다고 가정해 보겠습니다.

price += 10 << SHIFT_AMOUNT;

그러나 곱셈 및 나눗셈(* 및 /)의 경우 승수/나눗셈을 이동해서는 안 됩니다.3을 곱한다고 가정해 보겠습니다.

price *= 3;

이제 가격을 4로 나누어 0이 아닌 부분을 보충함으로써 상황을 더 흥미롭게 만들어 보겠습니다.

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

규칙은 여기까지입니다.언제든지 실제 가격을 검색하려면 오른쪽으로 이동해야 합니다.

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

부분 부분이 필요한 경우 다음과 같이 마스크해야 합니다.

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

물론 이 값은 소수점 분수라고 할 수 있는 값이 아닙니다. 실제로는 [0 - 65535] 범위의 정수입니다.그러나 소수 부분 범위 [0 - 0.9999...]와 정확히 일치합니다.즉, 매핑은 다음과 같습니다. 0 => 0, 32768 => 0.5, 65535 => 0.9999...

이를 소수점으로 보는 쉬운 방법은 다음과 같이 C 내장 부동 소수점 연산에 의존하는 것입니다.

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

그러나 FPU 지원(하드웨어 또는 소프트웨어)이 없는 경우 다음과 같은 새로운 기술을 완전한 가격에 사용할 수 있습니다.

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

식에서 0의 숫자는 대략 소수점 뒤에 원하는 자릿수입니다.분수 정밀도가 주어진 0의 수를 과대평가하지 마십시오(여기에는 실제 함정이 없습니다. 매우 명백합니다).size of(long)가 size of(int)와 같을 수 있는 한 단순을 사용하지 마십시오.long long은 int가 32비트인 경우 사용합니다. long long은 64비트 이상이어야 합니다(또는 int64_t, int_limest64_t 등을 사용하며 stdint.h로 선언됩니다).즉, 고정점 유형의 두 배 크기의 유형을 사용하는 것이 좋습니다.마지막으로, >= 64비트 유형에 액세스할 수 없다면 적어도 출력을 위해 에뮬레이션을 연습해야 할 때입니다.

이것들은 고정점 산술의 기본 아이디어입니다.

음수 값에 주의하십시오.때로는 까다로워질 수 있습니다. 특히 최종 가치를 보여줄 때가 그렇습니다.게다가, C는 서명된 정수에 대해 구현 정의되어 있습니다(이것이 문제가 되는 플랫폼은 현재 매우 드물지만).모든 것이 예상대로 진행되는지 확인하기 위해 항상 환경에서 최소한의 테스트를 수행해야 합니다.만약 그렇지 않다면, 당신이 무엇을 하는지 안다면 그것을 해킹할 수 있습니다(이것에 대해 개발하지는 않겠지만, 이것은 산술 시프트 대 논리 시프트 및 2의 보완 표현과 관련이 있습니다).그러나 부호가 없는 정수를 사용하면 행동이 잘 정의되어 있기 때문에 무엇을 하든 대부분 안전합니다.

또한 32비트 정수가 2 - 1보다³² 큰 값을 나타낼 수 없는 경우 2로 고정점¹⁶ 산술을 사용하면 범위가 2 - 1로 제한됩니다¹⁶!(그리고 이 모든 것을 부호 있는 정수로 2로 나눕니다. 이 예에서는 2 - 1의 사용¹⁵ 가능한 범위가 남게 됩니다.)그런 다음 상황에 적합한 SHIFT_AMOUNT를 선택하는 것이 목표입니다.이것은 정수 부품 크기와 부분 부품 정밀도 간의 균형입니다.

이제 실제 경고를 위해: 이 기술은 정확성이 최우선인 분야(재정, 과학, 군사 등)에서는 절대적으로 적합하지 않습니다.일반적인 부동 소수점(부동/이중)도 전체적으로 고정 소수점보다 더 나은 특성을 가지고 있음에도 불구하고 충분히 정밀하지 않은 경우가 많습니다.고정점의 정밀도는 값과 상관없이 동일합니다(경우에 따라 이점이 될 수 있음). 여기서 부동 정밀도는 값 크기(즉, 값 크기)에 반비례합니다.크기가 작을수록 정밀도가 높아집니다...음, 이것은 그것보다 더 복잡하지만 요점을 이해합니다.)또한 부동소수점은 높은 값을 가진 정밀도 손실의 비용에 비해 동등한 (비트 수) 정수(고정점이든 아니든)보다 훨씬 더 큰 크기를 갖습니다(1개 이상의 값을 추가해도 전혀 영향을 미치지 않는 크기의 지점에 도달할 수도 있습니다(정수에서는 발생할 수 없는 일).

만약 당신이 그런 합리적인 분야에서 일한다면, 당신은 임의적인 정밀도의 목적을 위해 전용 도서관을 사용하는 것이 더 낫습니다(gmplib를 보러 가세요, 무료입니다).컴퓨팅 과학에서, 본질적으로 정확성을 얻는 것은 여러분의 가치를 저장하기 위해 사용하는 비트의 수에 관한 것입니다.높은 정밀도를 원하십니까?비트를 사용합니다.이상입니다.

두 가지 방법이 있습니다.금융 서비스 업계에서 일하고 있다면 코드가 정확성과 정확성을 위해 준수해야 하는 표준이 있을 수 있으므로 메모리 비용에 관계없이 이를 준수해야 합니다.그 사업은 일반적으로 자금이 충분하기 때문에 더 많은 메모리를 구입하는 것은 문제가 되지 않을 것으로 알고 있습니다.:)

만약 이것이 개인적인 용도라면, 최대한 정확하게는 정수를 사용하고 저장하기 전에 모든 가격에 고정 계수를 곱하는 것이 좋습니다.예를 들어, 1페니만큼 정확한 것을 원한다면(아마도 충분하지 않을 것이다) 모든 가격에 100을 곱하여 단위가 달러가 아닌 센트가 되도록 한 다음 거기서 사용합니다.더 정확하게 하려면 더 많이 곱하세요.예를 들어, 100분의 1센트(일반적으로 적용되는 표준)까지 정확하게 계산하려면 가격에 10000(100 * 100)을 곱합니다.

32비트 정수를 사용하면 10000을 곱하면 많은 금액을 사용할 수 있는 공간이 거의 없습니다.실제 32비트 제한이 20억이라는 것은 2000000000 / 1000000 = 20000달러의 높은 가격만 표시할 수 있다는 것을 의미합니다.이 2만을 곱하면 결과를 저장할 공간이 없을 수 있기 때문에 더 나빠집니다.이유로 정수64비트 정수)를 사용하는 것을 추천합니다.long long 곱셈을 값을 할 수 있는 모든 가격에 10000을 곱하더라도 곱셈 간에도 큰 값을 유지할 수 있는 여유가 충분합니다.

고정점의 비결은 계산을 할 때마다 각 값에 상수를 곱한 기본 값이라는 것을 기억해야 한다는 것입니다.더하기 또는 빼기 전에 상수가 큰 값과 일치하도록 상수가 작은 값을 곱해야 합니다.곱셈을 한 후에는 원하는 상수를 곱한 값으로 결과를 되돌리려면 어떤 값으로 나누어야 합니다.만약 여러분이 2의 거듭제곱이 아닌 정수를 상수로 사용한다면, 여러분은 시간적으로 값비싼 정수 나누기를 해야 할 것입니다.많은 사람들이 2의 거듭제곱을 상수로 사용하기 때문에 분할 대신 이동할 수 있습니다.

만약 이 모든 것이 복잡해 보인다면, 그렇습니다.가장 쉬운 방법은 더블을 사용하고 필요하다면 램을 더 사는 것이라고 생각합니다.그들은 53비트의 정밀도를 가지고 있습니다. 대략 9,000조, 즉 거의 16자리 숫자입니다.네, 수십억 달러를 가지고 일을 할 때에도 여전히 페니를 잃을 수 있지만, 만약 당신이 그것에 신경 쓴다면, 당신은 올바른 방식으로 억만장자가 되는 것이 아닙니다.:)

@알렉스는 여기서 환상적인 대답을 했습니다.하지만, 저는 예를 들어, 원하는 소수점으로 반올림하는 에뮬레이트 플로트(정수를 사용하여 플로트처럼 행동함)를 하는 방법을 보여줌으로써 그가 한 일에 몇 가지 개선점을 추가하고 싶었습니다.나는 그것을 아래의 나의 코드에서 증명합니다.하지만 저는 훨씬 더 멀리 가서 스스로에게 고정점 수학을 가르치기 위해 전체 코드 튜토리얼을 작성하게 되었습니다.여기 있습니다.

fixed_point_math 튜토리얼:고정점 연산, 정수만 사용하는 수동 "부동"과 같은 인쇄, "부동"과 같은 정수 반올림 및 큰 정수에 대한 부분 고정점 연산을 학습하는 튜토리얼과 같은 연습 코드입니다.

만약 여러분이 정말로 고정점 수학을 배우고 싶다면, 저는 이것이 주의 깊게 살펴볼 가치가 있는 코드라고 생각합니다. 하지만 저는 주말 내내 글을 쓰느라 걸렸기 때문에, 여러분이 이 모든 것을 완전히 이해하는 데 몇 시간이 걸릴 것으로 예상합니다.그러나 반올림의 기본 사항은 맨 위 섹션에서 바로 찾을 수 있으며 몇 분 안에 배울 수 있습니다.

GitHub에 대한 나의 전체 코드: https://github.com/ElectricRCAircraftGuy/fixed_point_math .

또는 아래(Stack Overflow는 그렇게 많은 문자를 허용하지 않기 때문에 잘림)

/*
fixed_point_math tutorial
- A tutorial-like practice code to learn how to do fixed-point math, manual "float"-like prints using integers only,
  "float"-like integer rounding, and fractional fixed-point math on large integers. 

By Gabriel Staples
www.ElectricRCAircraftGuy.com
- email available via the Contact Me link at the top of my website.
Started: 22 Dec. 2018 
Updated: 25 Dec. 2018 

References:
- https://stackoverflow.com/questions/10067510/fixed-point-arithmetic-in-c-programming

Commands to Compile & Run:
As a C program (the file must NOT have a C++ file extension or it will be automatically compiled as C++, so we will
make a copy of it and change the file extension to .c first):
See here: https://stackoverflow.com/a/3206195/4561887. 
    cp fixed_point_math.cpp fixed_point_math_copy.c && gcc -Wall -std=c99 -o ./bin/fixed_point_math_c fixed_point_math_copy.c && ./bin/fixed_point_math_c
As a C++ program:
    g++ -Wall -o ./bin/fixed_point_math_cpp fixed_point_math.cpp && ./bin/fixed_point_math_cpp

*/

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>

// Define our fixed point type.
typedef uint32_t fixed_point_t;

#define BITS_PER_BYTE 8

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

// // Conversions [NEVERMIND, LET'S DO THIS MANUALLY INSTEAD OF USING THESE MACROS TO HELP ENGRAIN IT IN US BETTER]:
// #define INT_2_FIXED_PT_NUM(num)     (num << FRACTION_BITS)      // Regular integer number to fixed point number
// #define FIXED_PT_NUM_2_INT(fp_num)  (fp_num >> FRACTION_BITS)   // Fixed point number back to regular integer number

// Private function prototypes:
static void print_if_error_introduced(uint8_t num_digits_after_decimal);

int main(int argc, char * argv[])
{
    printf("Begin.\n");

    // We know how many bits we will use for the fraction, but how many bits are remaining for the whole number, 
    // and what's the whole number's max range? Let's calculate it.
    const uint8_t WHOLE_NUM_BITS = sizeof(fixed_point_t)*BITS_PER_BYTE - FRACTION_BITS;
    const fixed_point_t MAX_WHOLE_NUM = (1 << WHOLE_NUM_BITS) - 1;
    printf("fraction bits = %u.\n", FRACTION_BITS);
    printf("whole number bits = %u.\n", WHOLE_NUM_BITS);
    printf("max whole number = %u.\n\n", MAX_WHOLE_NUM);

    // Create a variable called `price`, and let's do some fixed point math on it.
    const fixed_point_t PRICE_ORIGINAL = 503;
    fixed_point_t price = PRICE_ORIGINAL << FRACTION_BITS;
    price += 10 << FRACTION_BITS;
    price *= 3;
    price /= 7; // now our price is ((503 + 10)*3/7) = 219.857142857.

    printf("price as a true double is %3.9f.\n", ((double)PRICE_ORIGINAL + 10)*3/7);
    printf("price as integer is %u.\n", price >> FRACTION_BITS);
    printf("price fractional part is %u (of %u).\n", price & FRACTION_MASK, FRACTION_DIVISOR);
    printf("price fractional part as decimal is %f (%u/%u).\n", (double)(price & FRACTION_MASK) / FRACTION_DIVISOR,
           price & FRACTION_MASK, FRACTION_DIVISOR);

    // Now, if you don't have float support (neither in hardware via a Floating Point Unit [FPU], nor in software
    // via built-in floating point math libraries as part of your processor's C implementation), then you may have
    // to manually print the whole number and fractional number parts separately as follows. Look for the patterns.
    // Be sure to make note of the following 2 points:
    // - 1) the digits after the decimal are determined by the multiplier: 
    //     0 digits: * 10^0 ==> * 1         <== 0 zeros
    //     1 digit : * 10^1 ==> * 10        <== 1 zero
    //     2 digits: * 10^2 ==> * 100       <== 2 zeros
    //     3 digits: * 10^3 ==> * 1000      <== 3 zeros
    //     4 digits: * 10^4 ==> * 10000     <== 4 zeros
    //     5 digits: * 10^5 ==> * 100000    <== 5 zeros
    // - 2) Be sure to use the proper printf format statement to enforce the proper number of leading zeros in front of
    //   the fractional part of the number. ie: refer to the "%01", "%02", "%03", etc. below.
    // Manual "floats":
    // 0 digits after the decimal
    printf("price (manual float, 0 digits after decimal) is %u.", 
           price >> FRACTION_BITS); print_if_error_introduced(0);
    // 1 digit after the decimal
    printf("price (manual float, 1 digit  after decimal) is %u.%01lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 10 / FRACTION_DIVISOR); 
    print_if_error_introduced(1);
    // 2 digits after decimal
    printf("price (manual float, 2 digits after decimal) is %u.%02lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 100 / FRACTION_DIVISOR); 
    print_if_error_introduced(2);
    // 3 digits after decimal
    printf("price (manual float, 3 digits after decimal) is %u.%03lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 1000 / FRACTION_DIVISOR); 
    print_if_error_introduced(3);
    // 4 digits after decimal
    printf("price (manual float, 4 digits after decimal) is %u.%04lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 10000 / FRACTION_DIVISOR); 
    print_if_error_introduced(4);
    // 5 digits after decimal
    printf("price (manual float, 5 digits after decimal) is %u.%05lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 100000 / FRACTION_DIVISOR); 
    print_if_error_introduced(5);
    // 6 digits after decimal
    printf("price (manual float, 6 digits after decimal) is %u.%06lu.", 
           price >> FRACTION_BITS, (uint64_t)(price & FRACTION_MASK) * 1000000 / FRACTION_DIVISOR); 
    print_if_error_introduced(6);
    printf("\n");


    // Manual "floats" ***with rounding now***:
    // - To do rounding with integers, the concept is best understood by examples: 
    // BASE 10 CONCEPT:
    // 1. To round to the nearest whole number: 
    //    Add 1/2 to the number, then let it be truncated since it is an integer. 
    //    Examples:
    //      1.5 + 1/2 = 1.5 + 0.5 = 2.0. Truncate it to 2. Good!
    //      1.99 + 0.5 = 2.49. Truncate it to 2. Good!
    //      1.49 + 0.5 = 1.99. Truncate it to 1. Good!
    // 2. To round to the nearest tenth place:
    //    Multiply by 10 (this is equivalent to doing a single base-10 left-shift), then add 1/2, then let 
    //    it be truncated since it is an integer, then divide by 10 (this is a base-10 right-shift).
    //    Example:
    //      1.57 x 10 + 1/2 = 15.7 + 0.5 = 16.2. Truncate to 16. Divide by 10 --> 1.6. Good.
    // 3. To round to the nearest hundredth place:
    //    Multiply by 100 (base-10 left-shift 2 places), add 1/2, truncate, divide by 100 (base-10 
    //    right-shift 2 places).
    //    Example:
    //      1.579 x 100 + 1/2 = 157.9 + 0.5 = 158.4. Truncate to 158. Divide by 100 --> 1.58. Good.
    //
    // BASE 2 CONCEPT:
    // - We are dealing with fractional numbers stored in base-2 binary bits, however, and we have already 
    //   left-shifted by FRACTION_BITS (num << FRACTION_BITS) when we converted our numbers to fixed-point 
    //   numbers. Therefore, *all we have to do* is add the proper value, and we get the same effect when we 
    //   right-shift by FRACTION_BITS (num >> FRACTION_BITS) in our conversion back from fixed-point to regular
    //   numbers. Here's what that looks like for us:
    // - Note: "addend" = "a number that is added to another".
    //   (see https://www.google.com/search?q=addend&oq=addend&aqs=chrome.0.0l6.1290j0j7&sourceid=chrome&ie=UTF-8).
    // - Rounding to 0 digits means simply rounding to the nearest whole number.
    // Round to:        Addends:
    // 0 digits: add 5/10 * FRACTION_DIVISOR       ==> + FRACTION_DIVISOR/2
    // 1 digits: add 5/100 * FRACTION_DIVISOR      ==> + FRACTION_DIVISOR/20
    // 2 digits: add 5/1000 * FRACTION_DIVISOR     ==> + FRACTION_DIVISOR/200
    // 3 digits: add 5/10000 * FRACTION_DIVISOR    ==> + FRACTION_DIVISOR/2000
    // 4 digits: add 5/100000 * FRACTION_DIVISOR   ==> + FRACTION_DIVISOR/20000
    // 5 digits: add 5/1000000 * FRACTION_DIVISOR  ==> + FRACTION_DIVISOR/200000
    // 6 digits: add 5/10000000 * FRACTION_DIVISOR ==> + FRACTION_DIVISOR/2000000
    // etc.

    printf("WITH MANUAL INTEGER-BASED ROUNDING:\n");

    // Calculate addends used for rounding (see definition of "addend" above).
    fixed_point_t addend0 = FRACTION_DIVISOR/2;
    fixed_point_t addend1 = FRACTION_DIVISOR/20;
    fixed_point_t addend2 = FRACTION_DIVISOR/200;
    fixed_point_t addend3 = FRACTION_DIVISOR/2000;
    fixed_point_t addend4 = FRACTION_DIVISOR/20000;
    fixed_point_t addend5 = FRACTION_DIVISOR/200000;

    // Print addends used for rounding.
    printf("addend0 = %u.\n", addend0);
    printf("addend1 = %u.\n", addend1);
    printf("addend2 = %u.\n", addend2);
    printf("addend3 = %u.\n", addend3);
    printf("addend4 = %u.\n", addend4);
    printf("addend5 = %u.\n", addend5);

    // Calculate rounded prices
    fixed_point_t price_rounded0 = price + addend0; // round to 0 decimal digits
    fixed_point_t price_rounded1 = price + addend1; // round to 1 decimal digits
    fixed_point_t price_rounded2 = price + addend2; // round to 2 decimal digits
    fixed_point_t price_rounded3 = price + addend3; // round to 3 decimal digits
    fixed_point_t price_rounded4 = price + addend4; // round to 4 decimal digits
    fixed_point_t price_rounded5 = price + addend5; // round to 5 decimal digits

    // Print manually rounded prices of manually-printed fixed point integers as though they were "floats".
    printf("rounded price (manual float, rounded to 0 digits after decimal) is %u.\n", 
           price_rounded0 >> FRACTION_BITS); 
    printf("rounded price (manual float, rounded to 1 digit  after decimal) is %u.%01lu.\n", 
           price_rounded1 >> FRACTION_BITS, (uint64_t)(price_rounded1 & FRACTION_MASK) * 10 / FRACTION_DIVISOR); 
    printf("rounded price (manual float, rounded to 2 digits after decimal) is %u.%02lu.\n", 
           price_rounded2 >> FRACTION_BITS, (uint64_t)(price_rounded2 & FRACTION_MASK) * 100 / FRACTION_DIVISOR); 
    printf("rounded price (manual float, rounded to 3 digits after decimal) is %u.%03lu.\n", 
           price_rounded3 >> FRACTION_BITS, (uint64_t)(price_rounded3 & FRACTION_MASK) * 1000 / FRACTION_DIVISOR); 
    printf("rounded price (manual float, rounded to 4 digits after decimal) is %u.%04lu.\n", 
           price_rounded4 >> FRACTION_BITS, (uint64_t)(price_rounded4 & FRACTION_MASK) * 10000 / FRACTION_DIVISOR); 
    printf("rounded price (manual float, rounded to 5 digits after decimal) is %u.%05lu.\n", 
           price_rounded5 >> FRACTION_BITS, (uint64_t)(price_rounded5 & FRACTION_MASK) * 100000 / FRACTION_DIVISOR); 


    // =================================================================================================================

    printf("\nRELATED CONCEPT: DOING LARGE-INTEGER MATH WITH SMALL INTEGER TYPES:\n");

    // RELATED CONCEPTS:
    // Now let's practice handling (doing math on) large integers (ie: large relative to their integer type),
    // withOUT resorting to using larger integer types (because they may not exist for our target processor), 
    // and withOUT using floating point math, since that might also either not exist for our processor, or be too
    // slow or program-space-intensive for our application.
    // - These concepts are especially useful when you hit the limits of your architecture's integer types: ex: 
    //   if you have a uint64_t nanosecond timestamp that is really large, and you need to multiply it by a fraction
    //   to convert it, but you don't have uint128_t types available to you to multiply by the numerator before 
    //   dividing by the denominator. What do you do?
    // - We can use fixed-point math to achieve desired results. Let's look at various approaches.
    // - Let's say my goal is to multiply a number by a fraction < 1 withOUT it ever growing into a larger type.
    // - Essentially we want to multiply some really large number (near its range limit for its integer type)
    //   by some_number/some_larger_number (ie: a fraction < 1). The problem is that if we multiply by the numerator
    //   first, it will overflow, and if we divide by the denominator first we will lose resolution via bits 
    //   right-shifting out.
    // Here are various examples and approaches.

    // -----------------------------------------------------
    // EXAMPLE 1
    // Goal: Use only 16-bit values & math to find 65401 * 16/127.
    // Result: Great! All 3 approaches work, with the 3rd being the best. To learn the techniques required for the 
    // absolute best approach of all, take a look at the 8th approach in Example 2 below.
    // -----------------------------------------------------
    uint16_t num16 = 65401; // 1111 1111 0111 1001 
    uint16_t times = 16;
    uint16_t divide = 127;
    
    printf("\nEXAMPLE 1\n");

    // Find the true answer.
    // First, let's cheat to know the right answer by letting it grow into a larger type. 
    // Multiply *first* (before doing the divide) to avoid losing resolution.
    printf("%u * %u/%u = %u. <== true answer\n", num16, times, divide, (uint32_t)num16*times/divide);
    
    // 1st approach: just divide first to prevent overflow, and lose precision right from the start.
    uint16_t num16_result = num16/divide * times;
    printf("1st approach (divide then multiply):\n");
    printf("  num16_result = %u. <== Loses bits that right-shift out during the initial divide.\n", num16_result);
    
    // 2nd approach: split the 16-bit number into 2 8-bit numbers stored in 16-bit numbers, 
    // placing all 8 bits of each sub-number to the ***far right***, with 8 bits on the left to grow
    // into when multiplying. Then, multiply and divide each part separately. 
    // - The problem, however, is that you'll lose meaningful resolution on the upper-8-bit number when you 
    //   do the division, since there's no bits to the right for the right-shifted bits during division to 
    //   be retained in.
    // Re-sum both sub-numbers at the end to get the final result. 
    // - NOTE THAT 257 IS THE HIGHEST *TIMES* VALUE I CAN USE SINCE 2^16/0b0000,0000,1111,1111 = 65536/255 = 257.00392.
    //   Therefore, any *times* value larger than this will cause overflow.
    uint16_t num16_upper8 = num16 >> 8; // 1111 1111
    uint16_t num16_lower8 = num16 & 0xFF; // 0111 1001
    num16_upper8 *= times;
    num16_lower8 *= times;
    num16_upper8 /= divide;
    num16_lower8 /= divide;
    num16_result = (num16_upper8 << 8) + num16_lower8;
    printf("2nd approach (split into 2 8-bit sub-numbers with bits at far right):\n");
    printf("  num16_result = %u. <== Loses bits that right-shift out during the divide.\n", num16_result);
    
    // 3rd approach: split the 16-bit number into 2 8-bit numbers stored in 16-bit numbers, 
    // placing all 8 bits of each sub-number ***in the center***, with 4 bits on the left to grow when 
    // multiplying and 4 bits on the right to not lose as many bits when dividing. 
    // This will help stop the loss of resolution when we divide, at the cost of overflowing more easily when we 
    // multiply.
    // - NOTE THAT 16 IS THE HIGHEST *TIMES* VALUE I CAN USE SINCE 2^16/0b0000,1111,1111,0000 = 65536/4080 = 16.0627.
    //   Therefore, any *times* value larger than this will cause overflow.
    num16_upper8 = (num16 >> 4) & 0x0FF0;
    num16_lower8 = (num16 << 4) & 0x0FF0;
    num16_upper8 *= times;
    num16_lower8 *= times;
    num16_upper8 /= divide;
    num16_lower8 /= divide;
    num16_result = (num16_upper8 << 4) + (num16_lower8 >> 4);
    printf("3rd approach (split into 2 8-bit sub-numbers with bits centered):\n");
    printf("  num16_result = %u. <== Perfect! Retains the bits that right-shift during the divide.\n", num16_result);

    // -----------------------------------------------------
    // EXAMPLE 2
    // Goal: Use only 16-bit values & math to find 65401 * 99/127.
    // Result: Many approaches work, so long as enough bits exist to the left to not allow overflow during the 
    // multiply. The best approach is the 8th one, however, which 1) right-shifts the minimum possible before the
    // multiply, in order to retain as much resolution as possible, and 2) does integer rounding during the divide
    // in order to be as accurate as possible. This is the best approach to use.
    // -----------------------------------------------------
    num16 = 65401; // 1111 1111 0111 1001 
    times = 99;
    divide = 127;

    printf("\nEXAMPLE 2\n");

    // Find the true answer by letting it grow into a larger type.
    printf("%u * %u/%u = %u. <== true answer\n", num16, times, divide, (uint32_t)num16*times/divide);

    // 1st approach: just divide first to prevent overflow, and lose precision right from the start.
    num16_result = num16/divide * times;
    printf("1st approach (divide then multiply):\n");
    printf("  num16_result = %u. <== Loses bits that right-shift out during the initial divide.\n", num16_result);

    // 2nd approach: split the 16-bit number into 2 8-bit numbers stored in 16-bit numbers, 
    // placing all 8 bits of each sub-number to the ***far right***, with 8 bits on the left to grow
    // into when multiplying. Then, multiply and divide each part separately. 
    // - The problem, however, is that you'll lose meaningful resolution on the upper-8-bit number when you 
    //   do the division, since there's no bits to the right for the right-shifted bits during division to 
    //   be retained in.
    // Re-sum both sub-numbers at the end to get the final result. 
    // - NOTE THAT 257 IS THE HIGHEST *TIMES* VALUE I CAN USE SINCE 2^16/0b0000,0000,1111,1111 = 65536/255 = 257.00392.
    //   Therefore, any *times* value larger than this will cause overflow.
    num16_upper8 = num16 >> 8; // 1111 1111
    num16_lower8 = num16 & 0xFF; // 0111 1001
    num16_upper8 *= times;
    num16_lower8 *= times;
    num16_upper8 /= divide;
    num16_lower8 /= divide;
    num16_result = (num16_upper8 << 8) + num16_lower8;
    printf("2nd approach (split into 2 8-bit sub-numbers with bits at far right):\n");
    printf("  num16_result = %u. <== Loses bits that right-shift out during the divide.\n", num16_result);
    
    /////////////////////////////////////////////////////////////////////////////////////////////////
    // TRUNCATED BECAUSE STACK OVERFLOW WON'T ALLOW THIS MANY CHARACTERS.
    // See the rest of the code on github: https://github.com/ElectricRCAircraftGuy/fixed_point_math
    /////////////////////////////////////////////////////////////////////////////////////////////////

    return 0;
} // main

// PRIVATE FUNCTION DEFINITIONS:

/// @brief A function to help identify at what decimal digit error is introduced, based on how many bits you are using
///        to represent the fractional portion of the number in your fixed-point number system.
/// @details    Note: this function relies on an internal static bool to keep track of if it has already
///             identified at what decimal digit error is introduced, so once it prints this fact once, it will never 
///             print again. This is by design just to simplify usage in this demo.
/// @param[in]  num_digits_after_decimal    The number of decimal digits we are printing after the decimal 
///             (0, 1, 2, 3, etc)
/// @return     None
static void print_if_error_introduced(uint8_t num_digits_after_decimal)
{
    static bool already_found = false;

    // Array of power base 10 values, where the value = 10^index:
    const uint32_t POW_BASE_10[] = 
    {
        1, // index 0 (10^0)
        10, 
        100, 
        1000, 
        10000, 
        100000,
        1000000,
        10000000,
        100000000,
        1000000000, // index 9 (10^9); 1 Billion: the max power of 10 that can be stored in a uint32_t
    };

    if (already_found == true)
    {
        goto done;
    }

    if (POW_BASE_10[num_digits_after_decimal] > FRACTION_DIVISOR)
    {
        already_found = true;
        printf(" <== Fixed-point math decimal error first\n"
               "    starts to get introduced here since the fixed point resolution (1/%u) now has lower resolution\n"
               "    than the base-10 resolution (which is 1/%u) at this decimal place. Decimal error may not show\n"
               "    up at this decimal location, per say, but definitely will for all decimal places hereafter.", 
               FRACTION_DIVISOR, POW_BASE_10[num_digits_after_decimal]);
    }

done:
    printf("\n");
}

출력:

gabriel$ cp fixed_point_math.cpp fixed_point_math_copy.c && gcc -Wall -std=c99 -o ./bin/fixed_point_math_c > fixed_point_math_copy.c && ./bin/fixed_point_math_c  
Begin.  
fraction bits = 16.  
whole number bits = 16.  
max whole number = 65535.  
  
price as a true double is 219.857142857.  
price as integer is 219.  
price fractional part is 56173 (of 65536).  
price fractional part as decimal is 0.857132 (56173/65536).  
price (manual float, 0 digits after decimal) is 219.  
price (manual float, 1 digit  after decimal) is 219.8.  
price (manual float, 2 digits after decimal) is 219.85.  
price (manual float, 3 digits after decimal) is 219.857.  
price (manual float, 4 digits after decimal) is 219.8571.  
price (manual float, 5 digits after decimal) is 219.85713. <== Fixed-point math decimal error first  
    starts to get introduced here since the fixed point resolution (1/65536) now has lower resolution  
    than the base-10 resolution (which is 1/100000) at this decimal place. Decimal error may not show  
    up at this decimal location, per say, but definitely will for all decimal places hereafter.  
price (manual float, 6 digits after decimal) is 219.857131.  
  
WITH MANUAL INTEGER-BASED ROUNDING:  
addend0 = 32768.  
addend1 = 3276.  
addend2 = 327.  
addend3 = 32.  
addend4 = 3.  
addend5 = 0.  
rounded price (manual float, rounded to 0 digits after decimal) is 220.  
rounded price (manual float, rounded to 1 digit  after decimal) is 219.9.  
rounded price (manual float, rounded to 2 digits after decimal) is 219.86.  
rounded price (manual float, rounded to 3 digits after decimal) is 219.857.  
rounded price (manual float, rounded to 4 digits after decimal) is 219.8571.  
rounded price (manual float, rounded to 5 digits after decimal) is 219.85713.  
  
RELATED CONCEPT: DOING LARGE-INTEGER MATH WITH SMALL INTEGER TYPES:  
  
EXAMPLE 1  
65401 * 16/127 = 8239. <== true answer  
1st approach (divide then multiply):  
  num16_result = 8224. <== Loses bits that right-shift out during the initial divide.  
2nd approach (split into 2 8-bit sub-numbers with bits at far right):  
  num16_result = 8207. <== Loses bits that right-shift out during the divide.  
3rd approach (split into 2 8-bit sub-numbers with bits centered):  
  num16_result = 8239. <== Perfect! Retains the bits that right-shift during the divide.  
  
EXAMPLE 2  
65401 * 99/127 = 50981. <== true answer  
1st approach (divide then multiply):  
  num16_result = 50886. <== Loses bits that right-shift out during the initial divide.  
2nd approach (split into 2 8-bit sub-numbers with bits at far right):  
  num16_result = 50782. <== Loses bits that right-shift out during the divide.  
3rd approach (split into 2 8-bit sub-numbers with bits centered):  
  num16_result = 1373. <== Completely wrong due to overflow during the multiply.  
4th approach (split into 4 4-bit sub-numbers with bits centered):  
  num16_result = 15870. <== Completely wrong due to overflow during the multiply.  
5th approach (split into 8 2-bit sub-numbers with bits centered):  
  num16_result = 50922. <== Loses a few bits that right-shift out during the divide.  
6th approach (split into 16 1-bit sub-numbers with bits skewed left):  
  num16_result = 50963. <== Loses the fewest possible bits that right-shift out during the divide.  
7th approach (split into 16 1-bit sub-numbers with bits skewed left):  
  num16_result = 50963. <== [same as 6th approach] Loses the fewest possible bits that right-shift out during the divide.  
[BEST APPROACH OF ALL] 8th approach (split into 16 1-bit sub-numbers with bits skewed left, w/integer rounding during division):  
  num16_result = 50967. <== Loses the fewest possible bits that right-shift out during the divide,   
  & has better accuracy due to rounding during the divide.  

참조:

• [myrepo] https://github.com/ElectricRCAircraftGuy/eRCaGuy_analogReadXXbit/blob/master/eRCaGuy_analogReadXXbit.cpp - 하단의 "정수 올림 노트"를 참조하십시오.

메모리를 절약하는 것이 유일한 목적이라면 권장하지 않습니다.가격 계산의 오류가 누적될 수 있고 당신은 그것을 망칠 것입니다.

만약 당신이 정말로 비슷한 것을 구현하고 싶다면, 당신은 단지 가격의 최소 간격을 취한 후 직접 int와 정수 연산을 사용하여 당신의 숫자를 조작할 수 있습니까?표시 시 부동 소수점 번호로 변환만 하면 되므로 생활이 편합니다.

언급URL : https://stackoverflow.com/questions/10067510/fixed-point-arithmetic-in-c-programming