Арифметика с фиксированной точкой в ​​программировании на C

Я пытаюсь создать приложение, которое сохраняет цены на акции с высокой точностью. В настоящее время я использую double для этого. Для сохранения в памяти можно использовать любой другой тип данных? Я знаю, что это имеет какое-то отношение к арифметике с фиксированной точкой, но я не могу понять это.

Ответы

Ответ 1

Идея арифметики с фиксированной точкой состоит в том, что вы храните значения, умноженные на определенную сумму, используйте умноженные значения для всего исчисления и делите их на ту же сумму, когда вы хотите получить результат. Целью этого метода является использование целочисленной арифметики (int, long...), которая может представлять фракции.

Обычный и наиболее эффективный способ сделать это на C заключается в использовании операторов сдвига битов (< < и → ). Сдвиговые биты - это довольно простая и быстрая операция для ALU, и для этого необходимо, чтобы свойство умножало (< <) и делит ( → ) целочисленное значение на 2 на каждую смену (кроме того, многие сдвиги могут быть выполнены точно одна и та же цена одного). Конечно, недостаток заключается в том, что множитель должен быть степенью 2 (что обычно не является проблемой само по себе, поскольку мы действительно не заботимся об этом точном значении множителя).

Теперь скажем, мы хотим использовать 32-битные целые числа для хранения наших значений. Мы должны выбрать мощность 2 множителя. Позвольте разделить торт на две части, так скажем 65536 (это самый распространенный случай, но вы действительно можете использовать любую силу 2 в зависимости от ваших потребностей в точности). Это 2 16 а здесь 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 не обязательно 32 бит в C, хотя в большинстве случаев это происходит в настоящее время. Также без дальнейшего объявления он подписан по умолчанию. Вы можете добавить unsigned в объявление, чтобы быть уверенным. Более того, вы можете использовать uint32_t или uint_least32_t (объявленный в stdint.h), если ваш код сильно зависит от размера целочисленного бита (вы можете ввести некоторые хаки об этом). В сомнении, используйте typedef для вашего типа с фиксированной точкой, и вы будете более безопасны.

Если вы хотите сделать исчисление по этому значению, вы можете использовать 4 основных оператора: +, -, * и /. Вы должны иметь в виду, что при добавлении и вычитании значения (+ и -) это значение также должно быть смещено. Скажем, мы хотим добавить 10 к нашей цене 500:

price += 10 << SHIFT_AMOUNT;

Но для умножения и деления (* и /) делитель/делитель НЕ должен быть сдвинут. Пусть говорят, что мы хотим умножить на 3:

price *= 3;

Теперь сделайте вещи более интересными, разделив цену на 4, чтобы мы восполнили ненулевую дробную часть:

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, учитывая точность фракции (здесь нет настоящей ловушки, что вполне очевидно). Не используйте простую длину, так как sizeof (long) может быть равно sizeof (int). Используйте long long в случае, если int 32 бит, как долго, должен быть минимальным 64 бита (или использовать int64_t, int_least64_t и т.д., Объявленный в stdint.h). Другими словами, используйте тип, который в два раза больше вашего фиксированного типа, что достаточно справедливо. Наконец, если у вас нет доступа к >= 64 битным типам, возможно, это время для имитации ими эмуляции, по крайней мере для вашего вывода.

Это основные идеи арифметики с фиксированной точкой.

Будьте осторожны с отрицательными значениями. Иногда бывает сложно, особенно когда пришло время показать окончательное значение. Кроме того, C определяется реализацией целых чисел со знаком (даже если платформы, где это проблема, очень редко встречаются в настоящее время). Вы всегда должны делать минимальные тесты в своей среде, чтобы убедиться, что все идет так, как ожидалось. Если нет, вы можете взломать его, если знаете, что делаете (я не буду развиваться по этому поводу, но это как-то связано с арифметическим сдвигом по сравнению с логическим сдвигом и представлением из двух дополнений). Однако с целыми числами без знака, вы в основном безопасны, что бы вы ни делали, так как поведение в любом случае хорошо определено.

Также обратите внимание, что если 32-битное целое число не может представлять значения больше 2 32 - 1, использование арифметики с фиксированной точкой с 2 ​​ 16 ограничивает ваш диапазон до 2 16 - 1! (и разделим все это на 2 со знаками целых чисел, которые в нашем примере оставят нам доступный диапазон 2 15 - 1). Цель состоит в том, чтобы выбрать SHIFT_AMOUNT, подходящий для ситуации. Это компромисс между величиной целочисленной части и точностью дробной части.

Теперь для реальных предупреждений: этот метод определенно не подходит в тех областях, где точность является главным приоритетом (финансовая, научная, военная...). Обычная с плавающей запятой (float/double) также часто недостаточно точна, хотя у них лучшие свойства, чем общая точка с фиксированной точкой. Фиксированная точка имеет ту же точность, что и значение (в некоторых случаях это может быть преимуществом), где точность поплавков обратно пропорциональна величине величины (т.е. Чем ниже величина, тем больше точность вы получаете... ну, это сложнее, чем вы, но вы понимаете). Кроме того, поплавки имеют гораздо большую величину, чем эквивалентные (по числу бит) целые числа (фиксированная точка или нет), к стоимости потери точности с высокими значениями (вы даже можете достичь точки, где добавление 1 или даже более высокие значения не будут иметь никакого эффекта вообще, что не может произойти с целыми числами).

Если вы работаете в этих разумных областях, вам лучше использовать библиотеки, предназначенные для произвольной точности (см. gmplib, он бесплатный). В вычислительной науке, по сути, получение точности - это количество бит, которое вы используете для хранения ваших значений. Вы хотите высокой точности? Используйте биты. Это все.

Ответ 2

Я вижу два варианта для вас. Если вы работаете в отрасли финансовых услуг, вероятно, есть стандарты, которые ваш код должен соблюдать для точности и точности, поэтому вам просто нужно согласиться с этим, независимо от стоимости памяти. Я понимаю, что этот бизнес в целом хорошо финансируется, поэтому платить больше за память не должно быть проблемой.:)

Если это для личного использования, то для максимальной точности я рекомендую вам использовать целые числа и умножать все цены на фиксированный коэффициент перед хранением. Например, если вы хотите, чтобы вещи были точными по отношению к копейке (возможно, недостаточно хороши), умножьте все цены на 100, чтобы ваше подразделение было фактически центами вместо долларов и оттуда. Если вы хотите больше точности, умножьте ее на большее. Например, чтобы быть точным до сотых процента (стандарт, который я слышал, обычно применяется), умножьте цены на 10000 (100 * 100).

Теперь с 32-битными целыми числами, умножая на 10000, мало места для большого количества долларов. Практический 32-битный лимит в 2 миллиарда означает, что могут быть выражены только цены до $20000: 2000000000/10000 = 20000. Это ухудшается, если вы умножаете это 20000 на что-то, так как не может быть места для хранения результата. По этой причине я рекомендую использовать 64-битные целые числа (long long). Даже если вы умножаете все цены на 10000, по-прежнему остается большой запас для хранения больших значений, даже при умножении.

Трюк с фиксированной точкой заключается в том, что всякий раз, когда вы делаете расчет, вам нужно помнить, что каждое значение действительно является базовым значением, умноженным на константу. Перед добавлением или вычитанием вам нужно умножить значения с меньшей константой, чтобы они соответствовали значениям с большей константой. После умножения вам нужно разделить что-то, чтобы вернуть результат к умножению на нужную константу. Если вы используете не-силу двух в качестве константы, вам придется делать целочисленное разделение, что дорого, по времени. Многие люди используют две силы в качестве своих констант, поэтому они могут смещаться вместо разделения.

Если все это кажется сложным, это так. Я думаю, что самый простой вариант - использовать удвоения и купить больше оперативной памяти, если вам это нужно. Они имеют 53 бит точности, что составляет примерно 9 квадриллионов, или почти 16 десятичных цифр. Да, вы все равно можете потерять гроши, когда работаете с миллиардами, но если вам это все равно, вы не являетесь миллиардером.:)

Ответ 3

Я бы не рекомендовал вам это делать, если ваша единственная цель - сохранить память. Ошибка в вычислении цены может накапливаться, и вы собираетесь ее испортить.

Если вы действительно хотите реализовать похожие вещи, можете ли вы просто взять минимальный интервал цены, а затем напрямую использовать операцию int и integer для управления вашим номером? Вам нужно только преобразовать его в число с плавающей запятой при отображении, что упростит вашу жизнь.