海闊天空

          I'm on my way!
          隨筆 - 17, 文章 - 69, 評(píng)論 - 21, 引用 - 0
          數(shù)據(jù)加載中……

          浮點(diǎn)數(shù)比較

          在數(shù)學(xué)運(yùn)算當(dāng)中經(jīng)常會(huì)涉及到判斷兩個(gè)數(shù)是否相等的情況
          對(duì)于整數(shù)很好處理 A==B這樣的一個(gè)語(yǔ)句就可以解決全部的問(wèn)題
          但是對(duì)于浮點(diǎn)數(shù)是不同的

          首先,浮點(diǎn)數(shù)在計(jì)算機(jī)當(dāng)中的二進(jìn)制表達(dá)方式就決定了大多數(shù)浮點(diǎn)數(shù)都是無(wú)法精確的表達(dá)的
          現(xiàn)在的計(jì)算機(jī)大部分都是數(shù)字計(jì)算機(jī),不是模擬機(jī),數(shù)字機(jī)的離散化的數(shù)據(jù)表示方法自然無(wú)法精確表達(dá)大部分的數(shù)據(jù)量的。

          其次計(jì)算機(jī)浮點(diǎn)數(shù)的精度在單精度f(wàn)loat類(lèi)型下,只有7位,在進(jìn)行浮點(diǎn)運(yùn)算的時(shí)候,這個(gè)精度往往會(huì)導(dǎo)致運(yùn)算的結(jié)果和實(shí)際期望的結(jié)果之間有誤差

          因?yàn)榍皟蓚€(gè)原因,我們很難用 A==B來(lái)判定兩個(gè)浮點(diǎn)數(shù)是否相同

          很自然,我們可以想到 fabs(A-B) < epsilon 這樣的一種判別方法
          但是這種判別方法穩(wěn)妥嗎?
          它也不穩(wěn)妥。

          首先, epsilon是一個(gè)絕對(duì)的數(shù)據(jù),也就是誤差分析當(dāng)中說(shuō)說(shuō)的絕對(duì)誤差
          使用一個(gè)固定的數(shù)值,對(duì)于float類(lèi)型可以表達(dá)的整個(gè)數(shù)域來(lái)說(shuō)是不可以的
          比如epsilon取值為0.0001,而a和b的數(shù)值大小也是0.0001附近的,那么顯然不合適
          另外對(duì)于a和b大小是10000這樣的數(shù)據(jù)的時(shí)候,它也不合適,因?yàn)?0000和10001也可以認(rèn)為是相等的呢
          適合它的情況只是a或者b在1或者0附近的時(shí)候

          既然絕對(duì)誤差不可以,那么自然的我們就會(huì)想到了相對(duì)誤差
          bool IsEqual(float a, float b, float relError ) {
                 return ( fabs ( (a-b)/a ) < relError ) ? true : false;
          }
          這樣寫(xiě)還不完善,因?yàn)槭悄霉潭ǖ牡谝粋€(gè)參數(shù)做比較的,那么在調(diào)用
          IsEqual(a, b, relError ) 和 IsEqual(b, a, relError ) 的時(shí)候,可能得到不同的結(jié)果
          同時(shí)如果第一個(gè)參數(shù)是0的話,就有可能是除0溢出
          這個(gè)可以改造
          把除數(shù)選取為a和b當(dāng)中絕對(duì)數(shù)值較大的即可
          bool IsEqual(float a, float b, relError )
          {
                if (fabs(a)<fabs(b)) return ( fabs((a-b)/a) > relError ) ? true : false;
                return (fabs( (a-b)/b) > relError ) ? true : false;
          };

          使用相對(duì)誤差就很完善嗎?
          也不是, 在某些特殊情況下, 相對(duì)誤差也不能代表全部
          比如在判斷空間三點(diǎn)是否共線的時(shí)候,使用判斷點(diǎn)到另外兩個(gè)點(diǎn)形成的線段的距離的方法的時(shí)候
          只用相對(duì)誤差是不夠的,應(yīng)為線段距離可能很段,也可能很長(zhǎng),點(diǎn)到線段的距離,以及線段的長(zhǎng)度做綜合比較的時(shí)候,需要相對(duì)誤差和絕對(duì)誤差結(jié)合的方式才可以
          相對(duì)完整的比較算法應(yīng)該如下:
          bool IsEqual(float a, float b, float absError, float relError )
          {
                   if (a==b) return true;
                  if (fabs(a-b)<absError ) return true;
                  if (fabs(a>b) return (fabs((a-b)/a>relError ) ? true : false;
                  return (fabs((a-b)/b>relError ) ? true : false;
          }
          這樣才相對(duì)完整

          這僅僅是浮點(diǎn)數(shù)之間最初級(jí)的比較方法
          高級(jí)的方法看 浮點(diǎn)數(shù)比較(二) 這個(gè)文章 —— 如何把兩個(gè)浮點(diǎn)數(shù)之間的比較轉(zhuǎn)化成為兩個(gè)整數(shù)之間的比較。
          -------------------------------------

          浮點(diǎn)數(shù)的內(nèi)存結(jié)構(gòu)


          根據(jù)IEEE的標(biāo)準(zhǔn),浮點(diǎn)數(shù)的定義如下

          符號(hào)位 指數(shù)位 小數(shù)部分 指數(shù)偏移量
          單精度浮點(diǎn)數(shù) 1 位[31] 8位 [30-23] 23位 [22-00] 127
          雙精度浮點(diǎn)數(shù) 1 位[63] 11 位[62-52] 52 位[51-00] 1023

          我們以單精度浮點(diǎn)數(shù)來(lái)說(shuō)明:
          符號(hào)位,表述浮點(diǎn)數(shù)的正或者負(fù)
          指數(shù)實(shí)際也有正負(fù)的,但是沒(méi)有單獨(dú)的符號(hào)位,而是采用了一個(gè)偏移來(lái)表示
          在計(jì)算機(jī)的世界里,進(jìn)位都是二進(jìn)制的,指數(shù)表示的也是2的N次冪
          這個(gè)數(shù)據(jù)格式當(dāng)中的,指數(shù)是8位,可表達(dá)的范圍是0到255
          而對(duì)應(yīng)的實(shí)際的指數(shù)是-127到+128
          這里特殊說(shuō)明,-127和+128這兩個(gè)數(shù)據(jù)在IEEE當(dāng)中是保留的用作多種用途的
          -127表示的數(shù)字是0
          128和其他位數(shù)組合表示多種意義,最典型的就是NAN狀態(tài)

          小數(shù)部分,并不是一個(gè)浮點(diǎn)數(shù)的實(shí)際的小數(shù)
          實(shí)際的小數(shù)在這個(gè)小數(shù)前面還保留了一個(gè)1
          拿浮點(diǎn)數(shù)1.0來(lái)說(shuō)
          符號(hào)位是0, 實(shí)際指數(shù)是0,對(duì)應(yīng)這里的指數(shù)就是127了,也就是0x7f
          而小數(shù)部分就是1.0了, 1是暗含的不存儲(chǔ),實(shí)際的小數(shù)部分就是0了
          因此組合起來(lái)的數(shù)據(jù)就是,0x3f80000

          可以用一個(gè)類(lèi)來(lái)表示:
          class FloatType
          {
          public:
                union {
                   DWORD m_dwInt;
                   float          m_fFloat;
                 struct {  

                  int    m_nFra: 23;

                    int    m_nExp : 8;

                    bool m_bSign : 1;

                };
          };

          -----------------------------

          參考IEEE的浮點(diǎn)數(shù)格式說(shuō)明
          對(duì)于0到1范圍內(nèi)的浮點(diǎn)數(shù)是可以壓縮的

          顯然在0到1的范圍內(nèi),一個(gè)單精度的浮點(diǎn)數(shù),指數(shù)和符號(hào)位占據(jù)9個(gè)bit
          而這9個(gè)bit是可以不用的,把它去除,只保留小數(shù)部分的23bit就可以達(dá)到壓縮的目的
          可以把一個(gè)浮點(diǎn)數(shù)從32bit,4字節(jié)壓縮到23bit,3字節(jié)的范圍內(nèi)

          這也是在3dmax等一些工具軟件當(dāng)中對(duì)浮點(diǎn)數(shù)進(jìn)行壓縮存儲(chǔ)的方法。
          比如,在單位化的法向量當(dāng)中,每個(gè)浮點(diǎn)數(shù)都是0,1范圍之間的數(shù)據(jù)
          正常情況下表示三維空間當(dāng)中的單位化法向量就需要12個(gè)字節(jié)
          而經(jīng)過(guò)這個(gè)壓縮處理,只需要9個(gè)字節(jié)

          -----------------------------


          在寫(xiě)了上篇 浮點(diǎn)數(shù)的比較 以及 浮點(diǎn)數(shù)內(nèi)存結(jié)構(gòu) 兩篇文章后
          對(duì)于浮點(diǎn)數(shù)的比較有新的想法

          我們先看正數(shù)的情況
          根據(jù)IEEE的內(nèi)存結(jié)構(gòu), 指數(shù)在高位,尾數(shù)在低位
          浮點(diǎn)數(shù)大的對(duì)應(yīng)的把其內(nèi)存結(jié)構(gòu)按照整數(shù)來(lái)理解進(jìn)行比較的時(shí)候,情況也是成立的
          因此在這里如果把他們進(jìn)行比較的話,作為整數(shù)運(yùn)算效率會(huì)非常的高,比如
          float f1 = 1.23;
          float f2 = 1.24
          f1 > f2 成立
          (int&)f1 > (int&)f2 也是成立的

          而且,仔細(xì)研究IEEE的浮點(diǎn)結(jié)構(gòu),可以發(fā)現(xiàn)在《浮點(diǎn)數(shù)比較》當(dāng)中提到的浮點(diǎn)數(shù)精度的問(wèn)題——不是所有的浮點(diǎn)數(shù)都可以精確的表達(dá)
          可以精確表達(dá)的浮點(diǎn)數(shù)實(shí)際上是有限的,就是那些IEEE的各種情況的枚舉了 2^32個(gè)。不能表達(dá)的占據(jù)了大多數(shù)

          IEEE在32位的情況下,尾數(shù)是23位的(暗含了第一個(gè)位數(shù)是1)
          對(duì)于可以精確表達(dá)的浮點(diǎn)數(shù)來(lái)說(shuō),如果我們把這23位當(dāng)作整數(shù)來(lái)理解, 它加1,就意味著可以找到比當(dāng)前對(duì)應(yīng)浮點(diǎn)數(shù)大的最小的浮點(diǎn)數(shù)了
          反之,我們把兩個(gè)浮點(diǎn)數(shù),對(duì)應(yīng)的整數(shù)做差值運(yùn)算,得到的整數(shù)表明的是兩個(gè)浮點(diǎn)數(shù)之間有多少個(gè)實(shí)際可以表達(dá)的浮點(diǎn)數(shù)(對(duì)應(yīng)的指數(shù)相同的情況下很好理解;指數(shù)不同的時(shí)候,也是同樣有效的)

          這樣,對(duì)于兩個(gè)正的浮點(diǎn)數(shù),他們的大小比較就可以用 (int&)f1 - (int&)f2 來(lái)進(jìn)行比較了
          差值的結(jié)果實(shí)際上就應(yīng)該是相對(duì)誤差了
          這個(gè)相對(duì)誤差,不等同于普遍意義上的相對(duì)誤差
          它所表達(dá)的是,兩個(gè)浮點(diǎn)數(shù)之間可能還有多少個(gè)可以精確表達(dá)的浮點(diǎn)數(shù)
          這樣通過(guò)指定這個(gè)閾值來(lái)控制兩個(gè)浮點(diǎn)數(shù)的比較就更有效了
          對(duì)于兩個(gè)正的浮點(diǎn)數(shù)
          bool IsEqual(float f1, float f2, int absDelta)
          {
               if ( abs ( (int&)f1 - (int&)f2 ) < absDelta ) return true;
          }
          這里用abs而不是fabs這在asm上面的運(yùn)算差距也是很大的了

          對(duì)于兩個(gè)負(fù)數(shù)進(jìn)行比較的情況也是相同的
          只不過(guò)負(fù)數(shù)內(nèi)存對(duì)應(yīng)的整數(shù)加1,相應(yīng)的找到的是更小的負(fù)數(shù)而已

          但是負(fù)數(shù)和整數(shù)之間現(xiàn)在還不能進(jìn)行直接的比較,因?yàn)楦鶕?jù)IEEE的內(nèi)存結(jié)構(gòu)
          正數(shù)和負(fù)數(shù)是不同的,對(duì)應(yīng)的整數(shù)不能連續(xù)
          正的最小的數(shù)就是0了,對(duì)應(yīng)的整數(shù)也是0x00000000
          負(fù)的最小的數(shù)就是-0,對(duì)應(yīng)的整數(shù)則是0x 80000000
          不用奇怪-0
          在IEEE的表達(dá)當(dāng)中是有兩個(gè)0的,一個(gè)是 +0 一個(gè)是-0

          有趣的是,按照 f1 == f2 的判斷 +0和-0是相等的

          通過(guò)對(duì)比我們可以發(fā)現(xiàn),
          +0 和正的浮點(diǎn)數(shù)可以按照轉(zhuǎn)換成為整數(shù)的方式直接進(jìn)行比較
          -0 和負(fù)的浮點(diǎn)數(shù)可以按照轉(zhuǎn)換成為整數(shù)的方式直接進(jìn)行比較

          如果我們能夠把他們連接起來(lái),整個(gè)整數(shù)方式的直接比較就完備了
          對(duì)比一下負(fù)數(shù)的結(jié)構(gòu), 可以找到一個(gè)簡(jiǎn)單的辦法了:
                  把負(fù)數(shù)內(nèi)存對(duì)應(yīng)的整數(shù)減去 -0 ,他們就連續(xù)了
          而且更好的結(jié)果是,所有的負(fù)數(shù)經(jīng)過(guò)這次減法后,對(duì)應(yīng)的整數(shù)也都是負(fù)數(shù)了
          這樣整個(gè)整數(shù)比較就變得連續(xù)了,而且在整個(gè)浮點(diǎn)數(shù)范圍內(nèi)都是有效的了

          最后的比較算法就是:
          // 函數(shù):   bool IsEqual(float f1, float f2, int absDelta)
          // 功能:把比較兩個(gè)浮點(diǎn)數(shù)是否近似相同
          // 輸入:f1, f2參與比較的兩個(gè)浮點(diǎn)數(shù)
          //               absDelta 兩個(gè)浮點(diǎn)數(shù)之間允許有多少個(gè)其他可以精確表達(dá)的浮點(diǎn)數(shù)存在,相當(dāng)于相對(duì)誤差
          // 輸出:   true,兩個(gè)浮點(diǎn)數(shù)進(jìn)行相等; false 兩個(gè)浮點(diǎn)數(shù)不等
          // 注意:僅僅適合IEEE 32位浮點(diǎn)數(shù)結(jié)構(gòu)
          bool IsEqual(float f1, float f2, int absDelta)
          {
                 int i1, i2;
                 i1 = ( f1>0) ? ((int&)f1) : ( (int&) f1 - 0x80000000 );
                 i2 = (f2>0) ? ((int&)f2) : ( (int&) f2 - 0x80000000 );
                 return   ((abs(i1-i2))<absDelta) ? true : false;
          }

          posted on 2009-07-05 21:52 石頭@ 閱讀(4080) 評(píng)論(0)  編輯  收藏 所屬分類(lèi): java_base

          主站蜘蛛池模板: 威信县| 雅江县| 洛南县| 丽江市| 安阳县| 墨江| 磐安县| 高清| 云和县| 沈丘县| 富民县| 伊宁市| 景谷| 宝兴县| 郁南县| 澄迈县| 东至县| 绥棱县| 行唐县| 新河县| 凤山市| 富宁县| 广州市| 石楼县| 册亨县| 常熟市| 思茅市| 通化县| 苍溪县| 安新县| 丰城市| 小金县| 黄大仙区| 康保县| 富宁县| 图木舒克市| 桑日县| 平泉县| 丰镇市| 苏尼特右旗| 赣州市|