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




              回復  更多評論
              

            老司机国内精品久久久久| 欧洲性大片xxxxx久久久| 亚洲精品国产第一综合99久久 | 97精品久久天干天天天按摩| 青青草国产97免久久费观看| 久久综合久久鬼色| 久久伊人五月天论坛| 久久综合精品国产一区二区三区| 久久精品中文字幕一区| 香蕉久久AⅤ一区二区三区| 午夜精品久久久久久影视riav| 人妻少妇精品久久| 伊人久久精品无码av一区| 一本色道久久综合狠狠躁| 久久久老熟女一区二区三区| 久久国产精品久久精品国产| 91秦先生久久久久久久| 久久久久婷婷| 蜜臀av性久久久久蜜臀aⅴ| 国产精品一区二区久久| 久久久国产精品| 久久国产欧美日韩精品| 精品乱码久久久久久久| 国产A级毛片久久久精品毛片| 欧美成a人片免费看久久| 无码国内精品久久综合88 | 久久亚洲精品无码AV红樱桃| 国产Av激情久久无码天堂| 91久久九九无码成人网站| 国产精品中文久久久久久久| 久久综合九色综合网站| 亚洲国产成人久久综合一 | 久久久久久久综合日本亚洲 | 成人午夜精品久久久久久久小说| 国内精品久久久久久不卡影院| 亚州日韩精品专区久久久| 久久99久久99精品免视看动漫| 国产成人久久久精品二区三区| 中文字幕久久亚洲一区| 久久香蕉综合色一综合色88| 久久亚洲日韩看片无码|