亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 一個任意長整數(shù)的除數(shù)的算法？？�。� [打印本頁]

作者: pinktopone 時間: 2008-05-14 01:50
標(biāo)題: 一個任意長整數(shù)的除數(shù)的算法？？�。�
已知正整數(shù)m, 一定存在一個非負(fù)整數(shù)n, 使得2的n次方小于等于m, 并且m小于2的n+1次方, 即2^n <= m < 2^(n+1); (不等式 1)

現(xiàn)求a/b！ a, b都為正整數(shù)！可設(shè)a = bm + r, m為商，r為余數(shù), 滿足 0<= r < b。  又根據(jù)上面的不等式1，
有 (b*(2^n) + r) <= (bm + r) < (b*(2^(n+1)) + r);    而 0 <= r < b;
   b*(2^n) <= (b*(2^n) + r) <= a < (b*(2^(n+1)) + r) < (b*(2^(n+1)) + b);
有 b * (2^n) <= a < b * (2^(n+1)) + b; (不等式 2) 其實(shí)不等式2的右邊可縮小范圍為 a < b*(2^(n+1));
因?yàn)槿绻?a >= b*(2^(n+1)), 則m >= 2^(n+1)  明顯與不等式1矛盾.  我們有 b*(2^n) <= a < b*(2^(n+1)); (不等式3）
利用不等式3可求得2^n 和2^(n+1), 然后再利用折半查找（當(dāng)然也可以用其它更好的方法）查找滿足條件的m！

除法的非遞歸算法偽代碼如下：
   Divide: a, b
   //注意所有變量和常量都是任意長整數(shù)，它們之間的各種操作和比較都應(yīng)另外實(shí)現(xiàn)，這里的描述只是為了方便說明
   if(a < b) return 0;
   power1 = 1; power2= 2;  n = 0; value1 = b * power1; value2 = b * power2;
         while( !(value1 <= a && a < value2))          //利用不等式3，得到2^n和2^(n+1)
         {
               power1 = power2;    power2 *= 2;    //power1,power2 分別代表2^n和2^(n+1)
               value1 = b * power1;          // value1 =  b * (2^n)
               value2 = b * power2;          // value2 =  b * (2^(n+1))
               n++;                                     // 通過n來估計m有多大,當(dāng)然n遠(yuǎn)比m小得多
         }
         //從2^n到2^(n+1)中折半查找,總共有2^n+1個元素(當(dāng)然2^(n+1)不會
      low = power1;  high = power2;
         while(low<=high){
               mid = (low + high) / 2;          //這里另外寫一個除以2的函數(shù)(比較簡單)，不過也啟發(fā)我們可以用遞歸實(shí)現(xiàn)，可能又不一樣了
         if(0 <= (a - b * mid) && (a - b * mid) < b)    return mid; //找到m
               else  if((a - b * mid) < 0)  high = mid;                               //繼續(xù)在前半?yún)^(qū)進(jìn)行查找
         else  low = mid;                                                                //繼續(xù)在后半?yún)^(qū)進(jìn)行查找
      }

以上就是我的一點(diǎn)思路，提出來讓大家看看，希望大牛們給提提意見！！( 前面說了那么多，只是為了讓大家更好理解，敬請原諒！)
當(dāng)然本人是個菜鳥，編程能力不行，只好寫偽代碼，也不知寫得對不對，請大家不要砸雞蛋石頭，多提點(diǎn)寶貴意見！謝謝��！

作者: openq 時間: 2008-05-14 10:07
不知道你這個任意長，怎么個實(shí)現(xiàn)法。如果任意長是數(shù)字長度，不知道你這個算法如何適應(yīng)2048位的除法？

作者: pinktopone 時間: 2008-05-14 12:43
是的,任意長是指數(shù)字長度,當(dāng)然在現(xiàn)實(shí)中不可能是任意長,只要能滿足一定的需求就行了!
至于您說的2048位是指被除數(shù)還是商? 我的本意是如果n是幾百,幾千或者更大,那么2^n已經(jīng)是很大了, 而我個人分析認(rèn)為那個算法的復(fù)雜度是n+log2(2^n+1)≈2n(不知是否正確),那么你得到m
只需線性次加,減,乘和比較的操作就行了. 具體實(shí)現(xiàn)時,如果整數(shù)很大的話,連怎樣存儲都要仔細(xì)考慮,更不用說其它方面啦! 如果您說的是指n=2048的話,不知我是否可認(rèn)為大概只需4096次就可以算出m(2^n <= m < 2^(n+1))?? 我提出這個問題是為了知道這個算法是否可行??效率有多高???
希望大家多多指點(diǎn)!!

歡迎光臨 Chinaunix (http://www.72891.cn/)