• <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 閱讀(5284) 評論(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久久99这里只有免费的精品| 久久线看观看精品香蕉国产| 精品人妻伦九区久久AAA片69| 波多野结衣久久精品| 欧美精品一区二区精品久久 | 久久精品国产清高在天天线| 伊人久久精品线影院| 国产一区二区久久久| 国产精品久久久久一区二区三区 | 九九精品99久久久香蕉| 日韩亚洲国产综合久久久| 精品久久久久久亚洲| 亚洲中文字幕无码久久综合网| 91精品国产91久久久久久| 久久久久亚洲Av无码专| 18禁黄久久久AAA片| 97超级碰碰碰碰久久久久| 久久精品午夜一区二区福利| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 欧美大香线蕉线伊人久久| 久久精品国产欧美日韩99热| 久久免费高清视频| 久久精品国产第一区二区三区| 亚洲人成无码久久电影网站| 久久久噜噜噜久久中文字幕色伊伊| 久久中文字幕一区二区| 久久精品国产亚洲麻豆| 精品久久久久久久久午夜福利| 久久久噜噜噜久久中文字幕色伊伊| 精品熟女少妇aⅴ免费久久| AAA级久久久精品无码区| 久久青青草原综合伊人| 蜜桃麻豆www久久| 丁香久久婷婷国产午夜视频| 久久艹国产| 亚洲国产精品无码久久久久久曰|