• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            KISS(Keep It Simple, Standard)

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              10 Posts :: 0 Stories :: 24 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(10)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            本算法只采用移位、加減法、判斷和循環實現,因為它不需要浮點運算,也不需要乘除運算,因此可以很方便地運用到各種芯片上去。

            我們先來看看10進制下是如何手工計算開方的。
            先看下面兩個算式,
            x = 10*p + q  (1)
            公式(1)左右平方之后得:
            x^2 = 100*p^2 + 20pq + q^2 (2)
            現在假設我們知道x^2和p,希望求出q來,求出了q也就求出了x^2的開方x了。
            我們把公式(2)改寫為如下格式:
            q = (x^2 - 100*p^2)/(20*p+q) (3)

            這個算式左右都有q,因此無法直接計算出q來,因此手工的開方算法和手工除法算法一樣有一步需要猜值。

            我們來一個手工計算的例子:計算1234567890的開方

            首先我們把這個數兩位兩位一組分開,計算出最高位為3。也就是(3)中的p,最下面一行的334為余數,也就是公式(3)中的(x^2 - 100*p^2)近似值
                3
              ---------------
             / 12 34 56 78 90
                9
              ---------------
             /  3 34

            下面我們要找到一個0-9的數q使它最接近滿足公式(3)。我們先把p乘以20寫在334左邊:
                                       3  q
                                     ---------------
                                    / 12 34 56 78 90
                                       9
                                     ---------------
            (20*3+q)*q      /  3 34

            我們看到q為5時(60+q)*q的值最接近334,而且不超過334。于是我們得到:
                  3  5
                ---------------
               / 12 34 56 78 90
                  9
                ---------------
            65 /  3 34
                  3 25
                ---------------
                     9 56

            接下來就是重復上面的步驟了,這里就不再啰嗦了。

            這個手工算法其實和10進制關系不大,因此我們可以很容易的把它改為二進制,改為二進制之后,公式(3)就變成了:
            q = (x^2 - 4*p^2)/(4*p+q) (4)

            我們來看一個例子,計算100(二進制1100100)的開方:
                   1  0  1  0
                  -----------
                 / 1 10 01 00
                   1
                  -----------
             100 / 0 10
                   0 00
                  -----------
            1001 /   10 01
                     10 01
                  -----------
                      0 00

            這里每一步不再是把p乘以20了,而是把p乘以4,也就是把p右移兩位,而由于q的值只能為0或者1,所以我們只需要判斷余數(x^2 - 4*p^2)和(4*p+1)的大小關系,如果余數大于等于(4*p+q)那么該上一個1,否則該上一個0。

            下面給出完成的C語言程序,其中root表示p,rem表示每步計算之后的余數,divisor表示(4*p+1),通過a>>30取a的最高 2位,通過a<<=2將計算后的最高2位剔除。其中root的兩次<<1相當于4*p。程序完全是按照手工計算改寫的,應該不難理解。
            unsigned short sqrt(unsigned long a){
              unsigned long rem = 0;
              unsigned long root = 0;
              unsigned long divisor = 0;
              for(int i=0; i<16; ++i){
                root <<= 1;
                rem = ((rem << 2) + (a >> 30));
                a <<= 2;
                divisor = (root<<1) + 1;
                if(divisor <= rem){
                  rem -= divisor;
                  root++;
                }
              }
              return (unsigned short)(root);
            }

            posted on 2008-01-23 14:21 QUIRE-0216 閱讀(5237) 評論(1)  編輯 收藏 引用 所屬分類: Arithmetic(算法)

            Feedback

            # re: 利用移位、加減法實現整數開平方算法的方法(轉) 2008-01-23 14:46 QUIRE-0216
            為了大家能理解我把上面 1234567890 給做完!
                          3 5 q
                           ---------------
                           / 12 34 56 78 90
                           9
                           ---------------
                           65 / 3 34
                           3 25
                           ---------------
            (20*35+q)*q /  9 56
            我們看到q為1時(700+q)*q的值最接近956,而且不超過956。于是我們得到:
                          3 5 1 q
                           ---------------
                           / 12 34 56 78 90
                           9
                           ---------------
                           65 / 3 34
                           3 25
                           ---------------
            701 /   9 56
            7 01
            ----------------
            (20*351+q)*q / 2 55 78

            我們看到q為3時(20*351+q)*q的值最接近25578,而且不超過25578。于是我們得到:

                          3 5 1 3 q
                           ---------------
                           / 12 34 56 78 90
                           9
                           ---------------
                           65 / 3 34
                           3 25
                           ---------------
            701 /   9 56
            7 01
            ----------------
            7023 / 2 55 78
            2 10 69
            ----------------
            (20*3513+q)*q / 45 0990

            我們看到q為6時(20*3513+q)*q的值最接近450990,而且不超過450990。于是我們得到:
                          3 5 1 3 6
                           ---------------
                           / 12 34 56 78 90
                           9
                           ---------------
                           65 / 3 34
                           3 25
                           ---------------
            701 /   9 56
            7 01
            ----------------
            7023 / 2 55 78
            2 10 69
            ----------------
            70266 / 45 0990
            42 1596
            ----------------
            2 9394

            至此1234567890的根為35136.我想能看明白吧!




              回復  更多評論
              

            久久中文骚妇内射| 亚洲美日韩Av中文字幕无码久久久妻妇 | 久久久久久综合一区中文字幕| 久久精品中文闷骚内射| 久久精品国产99国产精品澳门 | 久久亚洲国产精品123区| 伊人久久大香线蕉精品不卡| 亚洲日本va中文字幕久久| 91精品国产综合久久香蕉| 伊人久久无码精品中文字幕| 久久婷婷五月综合色高清| 久久精品亚洲乱码伦伦中文| 亚洲精品美女久久777777| 大美女久久久久久j久久| 99精品久久精品一区二区| 久久国产高清字幕中文| 亚洲婷婷国产精品电影人久久| 72种姿势欧美久久久久大黄蕉| 久久精品亚洲精品国产欧美| 久久久亚洲欧洲日产国码aⅴ| 国产精品99久久久久久猫咪 | 久久99久久99精品免视看动漫| 久久夜色精品国产亚洲av| 日韩一区二区久久久久久| 久久亚洲美女精品国产精品| 伊人久久精品影院| 久久国产精品偷99| 一本久久久久久久| 久久er热视频在这里精品| 国产精品久久久久AV福利动漫| 亚洲午夜久久久久久噜噜噜| 久久久这里有精品| 午夜精品久久久久久久无码| 国产精品99久久不卡| 国产精品久久久99| 成人精品一区二区久久| 久久青青草原综合伊人| 免费国产99久久久香蕉| 亚洲国产精品久久久久| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 97精品伊人久久久大香线蕉|