• <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 閱讀(5235) 評論(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.我想能看明白吧!




              回復  更多評論
              

            国产精品18久久久久久vr| 久久九九兔免费精品6| 国产精品99久久久久久宅男| 亚洲狠狠久久综合一区77777| 久久国产成人午夜AV影院| 久久久久久亚洲精品影院| 久久精品国产亚洲av麻豆色欲 | 久久久精品人妻一区二区三区四| 97热久久免费频精品99| 久久久黄色大片| 国产综合精品久久亚洲| 色妞色综合久久夜夜| 久久久久综合网久久| 久久精品极品盛宴观看| 日本福利片国产午夜久久| 久久国产劲爆AV内射—百度| 99久久免费只有精品国产| 久久棈精品久久久久久噜噜| 2021国内久久精品| 国产精品久久久久久久午夜片| 蜜臀av性久久久久蜜臀aⅴ麻豆| 91精品婷婷国产综合久久| 久久综合88熟人妻| 国产成人久久精品一区二区三区 | 无码超乳爆乳中文字幕久久| 欧美久久亚洲精品| 久久成人精品| 久久久精品国产亚洲成人满18免费网站 | 久久综合九色欧美综合狠狠| 日本免费一区二区久久人人澡| 人人狠狠综合久久88成人| 东方aⅴ免费观看久久av| 久久热这里只有精品在线观看| 色婷婷狠狠久久综合五月| 久久一区二区免费播放| 精品久久久久久国产牛牛app | 亚洲精品国产美女久久久 | 国产精品久久久久…| 精品久久香蕉国产线看观看亚洲| 国产精品9999久久久久| 国产成人久久精品区一区二区|