Арифметика с фиксированной точкой в ​​программировании на языке С

Question

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

Answer 1

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

Обычный и наиболее эффективный способ сделать это на С - с помощью операторов сдвига битов (< < и >>).Сдвиговые биты - это довольно простая и быстрая операция для 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 не обязательно 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 ...

простой способ, чтобы увидеть его в виде десятичной дроби прибегать к С встроенным поплавковым арифметике в этой точке:

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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