floating point 에서 integer로 가장 빠르게 변환할 수 있는 방법
(정리를 위해서 남긴 글임.. 틀린부분있을수있음ㅠ)
http:////stereopsis.com/sree/fpu2006.html 참조.
FPU (floating point unit)
- 부동소수점 연산을 효율적으로 처리하기 위한 하드웨어 모듈
- IEEE754의 표준에 따른다.
Floating point를 integer로 변환하는 방식 3가지 (더 있지만 나머지 생략)
1) simple cast
2) fistp (x86 instruction)
3) xs_CRound (rounding with 'Magic Number')
simple cast는 의외로 시간이 가장 오래걸림. ( C spec을 맞춰 항상 올바르게 동작하기 위해 여러가지 일을 함..)
fistp는 x86 assembly instruction.
빠르고 정확하다. 하지만 반올림이 됨에 따라 simple cast와 다른결과가 나올수 있다.
반올림 방식은 mode를 전환함으로써 바꿀 수 있지만 쓰레드 단위로 global하게 적용된다.
즉, 내가 적용하고 싶은 lib의 일부 로직만 적용할 수 없다
+ 다른 lib이나 dll에서 모드를 바꾸면 그에 따른 영향을 받는다.
+ 다른 floating point 연산에까지 적용된다 ( 곱하기, 나누기, normalization 등)
+ not portable.
[IEEE754]에서 정의한 float round 규칙
- round up : 무한대방향으로 올림처리.
- round down : -무한대 방향으로 버림처리.
- round toward zero : 0의 방향으로 버림처리.
- round to nearest, ties to even : 가장 가까운 값으로 반올림.
0.5의 경우 가수부가 짝수인 수를 선택한다. (0선택).
Banker's Rounding 방식이다.
- round to nearest, ties away from zero :
0.5의 경우 절대값 기준으로 가장 큰 값 선택. (-0.5 -> -1 / 0.5 -> 1)
FPU의 rounding mode를 변경하려면 Control Word 레지스터의 RC field의 값을 바꾼다 (10,11번째 bit) [링크참조]
MagicNumber 방식은 내가 로직을 적용시키고 싶은 hotspot에만 적용가능.
속도도 빠름.
round/truncate도 fpu의 모드를 바꾸지 않고 구현가능
scientific math를 사용하지 않는 코드라면 이 방식 추천
(하지만 약간 부정확한듯? 혹은 precision 한계?)
magic number 방식의 원리.
floating point는 (가수부) x (밑수) ^ (지수)로 표현된다.
double-precision (64bit) 수의 경우 밑수는 2로 고정.
부호(1bit) / 지수부(11bit) / 가수부(52bit)으로 표현됨.
표현식을 정규화하면
1.xxxx * 2^n이 된다.
가수부의 정수는 항상 1이므로 bit로 저장할때 생략함.
(따라서 가수부는 2^-1부터 ... 2^-n까지 표현됨)
FPU에서 두수를 더할때
작은 수를 큰수에 자리수를 맞추고, 가수부를 integer 덧셈하듯이 더함.
ex.) 1.0101 * 2^4 + 1.0011 * 2^5의 경우 왼쪽수를 오른쪽수에 자리수를 맞춤.
1.0101 * 2^4 = 0.10101 * 2^5
이후 1.0011 + 0.10101해준다.
= 0.10101 * 2^5 + 1.0011 * 2^5
= (0.10101 + 1.0011) * 2^5
=
0 / 00..0110 / 0101010.......0
+ 0 / 00..0110 / 1001100.......0
여기서 Magic Number는 어떤 수 A를 integer로 만들고 싶을때, 매우 큰 수를 더해주는 것이다.
double-precision 에서 Magic Number = 1.5 * 2^52.
bit로 보면 가수부는 10000000..0 * 2^52가 됨.
(왼쪽 1bit빼고 전부 0으로 채워져있음)
A는 1.011이라고 하자. = 1.011 * 2^1 = 0.0000000..1 * 2^52
(가수부가 오른쪽으로 51bit 쉬프트됨)
ex.
1.011 * 2^1 = (1 * 2^0 + 0 * 2^-1 + 1 * 2^-2 + 1 * 2^-3) * 2^1
(1.011 * 2^-51) * 2^1 * 2^51 = (1 * 2^-51 + 0 * 2^-52 + 1 * 2^-53 + 1 * 2^-54 ) * 2^52
(1.011 * 2^-51) * 2^52 = (1 * 2^-51 + 0 * 2^-52 + 1 * 2^-53 + 1 * 2^-54 ) * 2^52
로 지수를 매직넘버에 맞춰 52로 만들어준다.
이를 Bit로 보면 2^-52 밑으로는 가수부 비트가 모자라기 때문에 없어지게 됨.
(반올림이 되든 버림이 되든 올림이 되든간에 사라짐. 비트가 모자라 표현불가)
Magic Number = 0 / 111111..11 / 100000.....0
A = 0 / 111111..11 / 000000001 (011) : (011은 없어졌다)
----------------------------------------------------
더한결과 = 0 / 111111..11 / 10000.....01
덧셈을 한 결과에서 가수부의 오른쪽 32bit만 읽으면 integer가 됨.
Fixed로 바꾸고 싶다면?
ex. FixedDot6로 바꾸고싶다면
MagicNumber를 1.5 * 2^52에서 1.5 * 2^(52-6)으로 바꾼다.
이후 위에서 한것처럼 똑같이 32bit을 읽으면 오른쪽 6bit은 소수부가 된다.
지수부를 줄인만큼 magic number와 소수점을 맞추는 단계(lines up)에서 쉬프트를 덜하게 되므로 소수점 이하로 숫자가 남게된다.
MagicNumber는 fistp와 같은 결과를 낸다. (Bankers Ronding된다?)
그럼 버림을 하거나 arithmetic rounding을 하고싶다면? (0.5 ->1)
버림의 경우 원래 value -= 0.5f - epsilon; 를 하고 반올림계산.
Arithmetic Rounding의 경우 value += epsilon을 하고 반올림계산.
(Bankers Rounding에서 0.5 => 0이지만 0.51은 1이 되는듯?)
