一个任意长整数的除数的算法？？！！

pinktopone

已知正整数m, 一定存在一个非负整数n, 使得2的n次方小于等于m, 并且m小于2的n+1次方, 即2^n <= m < 2^(n+1); (不等式 1)

现求a/b！ a, b都为正整数！ 可设a = bm + r, m为商，r为余数, 满足 0<= r < b。  又根据上面的不等式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)    其实不等式2的右边可缩小范围为 a < b*(2^(n+1));
因为如果 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), 然后再利用折半查找（当然也可以用其它更好的方法）查找满足条件的m！

除法的非递归算法伪代码如下：
       Divide: a, b
       //注意所有变量和常量都是任意长整数，它们之间的各种操作和比较都应另外实现，这里的描述只是为了方便说明
       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有多大,当然n远比m小得多
            }
            //从2^n到2^(n+1)中折半查找,总共有2^n+1个元素(当然2^(n+1)不会
        low = power1;  high = power2;
            while(low<=high){
                  mid = (low + high) / 2;           //这里另外写一个除以2的函数(比较简单)，不过也启发我们可以用递归实现，可能又不一样了
            if(0 <= (a - b * mid) && (a - b * mid) < b)     return mid;    //找到m
                  else  if((a - b * mid) < 0)  high = mid;                                //继续在前半区进行查找
            else  low = mid;                                                                 //继续在后半区进行查找
        }
               
以上就是我的一点思路，提出来让大家看看，希望大牛们给提提意见！！( 前面说了那么多，只是为了让大家更好理解，敬请原谅！)
当然本人是个菜鸟，编程能力不行，只好写伪代码，也不知写得对不对，请大家不要砸鸡蛋石头，多提点宝贵意见！谢谢！！

openq

不知道你这个任意长，怎么个实现法。如果任意长是数字长度，不知道你这个算法如何适应2048位的除法？

pinktopone

是的,任意长是指数字长度,当然在现实中不可能是任意长,只要能满足一定的需求就行了!
至于您说的2048位是指被除数还是商? 我的本意是如果n是几百,几千或者更大,那么2^n已经是很大了, 而我个人分析认为那个算法的复杂度是n+log2(2^n+1)≈2n(不知是否正确),那么你得到m
只需线性次加,减,乘和比较的操作就行了. 具体实现时,如果整数很大的话,连怎样存储都要仔细考虑,更不用说其它方面啦! 如果您说的是指n=2048的话,不知我是否可认为大概只需4096次就可以算出m(2^n <= m < 2^(n+1))?? 我提出这个问题是为了知道这个算法是否可行??效率有多高???
希望大家多多指点!!