Арифметика fixed-point на C++

4 Июн
2012

Сегодня расскажу Вам что такое fixed-point, зачем он нужен и как его можно использовать.
Существует такая проблема когда производительность приложения может заметно ухудшиться из-за особенностей вычисления на числах с плавающей точкой. Как правило CPU заточен под целочисленные операции, а сопроцессор FPU (floating point unit) в нем работает на порядке медленнее. Существую такие платформы где вообще отсутствует FPU и эмулирование операций с числами занимало бы много времени. Например, при наличии FPU, умножение чисел с плавающей точкой выполняется всего одной командой fmul, а при отсутствии FPU, умножение выполняется эмулирующей функцией __mulsf3. По сравнению с командой fmul, функция __mulsf3 эмулирует операции над числами с плавающей точкой, при этом вычисления производятся в целочисленном виде, что приводит к увеличению машинного кода и времени на его выполнение, в то время как команда fmul выполнит эту операцию быстро, с использованием аппаратных средств.
Данной проблеме существует решение, которое позволяет проводить вычисления с фиксированной точкой на целочисленном типе.
Принцип данного типа заключается в фиксированном сдвиге числа на N бит, в результате чего дробное число можно представить целым и оно будет иметь точность 2^N после точки. Пример преобразования числа с плавающей точкой в число с фиксированной точкой порядка 8 бит (2^8 = 1024).
Вот пример перевода числа с плавающей точкой в число с фиксированной точкой:
Fixed(12345,6789) = 1024 * 12345,6789 = 12641975,1936

Данное число, после точки, имеет точность 2^8 после запятой.
Пример обратного перевода числа с фиксированной точкой в число с плавающей точкой.
Float(12641975) = 12641975 / 1024 = 12345,6787109375

В данном случае число после обратного перевода имеет вид 12345,6787109375 и является точным в 3 знака после точки, максимальная точность на самом деле равна 2^8 = 1024.

Как происходят вычисления на типе с фиксированной точкой?

Операции суммы и разности эквивалентны обычным целочисленным операциям.
Fixed(x) + Fixed(y) и Fixed(x) - Fixed(y)
, с любым порядком
(1024 * x) + (1024 * y) и (1024 * x) - (1024 * y)

Умножение таких чисел производится в такой форме.
(Fixed(x) * Fixed(y)) / p
, это эквивалентно, с порядком 8 бит
((1024 * x) * (1024 * y)) / 1024

Деление.
(Fixed(x) * p) / Fixed(y)
, также с порядком 8 бит, это
(1024 * 1024 * x)*(1024 * y)

Переполнение

При выполнении операций умножения и деления возможен случай переполнения, что приведет к неверному результату. Это произойдет в том случае, если, например, будет использоваться 32 битный целочисленный тип и при вычислениях произойдет переполнение данного типа и в результате этого переполнения число потеряет старшие биты. Существует два способа устранения переполнения:
• Выполнить вычисления в 64-битном целочисленном типе.
• Выполнить вычисления в «разобранном» виде, например при умножении, (xi+xf)*(yi+yf) = xi*yi+xf*yf+xi*yf+yi*xf, приставки i и f означают целую часть и часть после точки.

Класс для работы с fixed-point на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#define DIGITS 1024 // экспонента
#define EPS 20 // константа устанавливающая границы приближенности вычисления корня
 
using namespace std;
typedef signed int __int32_t;
 
class Fixed {
signed int x;
 
Fixed(signed int a){
x = a;
}
public:
Fixed(){
x = 0;
}
static Fixed fromInt(signed int val){
return Fixed(val*DIGITS);
}
static Fixed fromFloat(float val){
return Fixed((signed int)(val*DIGITS));
}
float fixed2float(){
return ((float)x)/DIGITS;
}
Fixed sum(Fixed a,Fixed b){
return Fixed(a.x+b.x);
}
Fixed diff(Fixed a,Fixed b){
return Fixed(a.x-b.x);
}
Fixed mul(Fixed a,Fixed b){
signed int c=a.x*b.x;
if(c/b.x != a.x){
// Overflow!
signed int i1 = a.x/DIGITS;
signed int i2 = b.x/DIGITS;
signed int f1 = (a.x&(DIGITS-1));
signed int f2 = (b.x&(DIGITS-1));
return Fixed((i1*i2)*DIGITS+(f1*f2)/DIGITS+i1*f2+i2*f1);
}else{
return Fixed(c/DIGITS);
}
}
Fixed div(Fixed a,Fixed b){
if(a.x>(1<<21)){
// Overflow!
signed int i = a.x/DIGITS;
signed int f = (a.x&(DIGITS-1));
return Fixed(((i*DIGITS)/b.x)*DIGITS+(f*DIGITS)/b.x);
}else{
return Fixed((a.x*DIGITS)/b.x);
}
}
Fixed sqrt(Fixed k){
Fixed tmp(0);
tmp.x = k.x/2;
signed int min = 0;
signed int max = k.x;
Fixed quick(0);
do{
tmp.x = (min+max)/2;
quick = Fixed::mul(tmp,tmp);
if(abs(quick.x-k.x)<EPS) return Fixed(tmp);
if(quick.x>k.x){
max = tmp.x;
}else{
min = tmp.x;
}
}while(true);
}
};
По материалам Хабрахабр.



загрузка...

Комментарии:

Наверх