呵呵 原理你表哥是校友啊 巧

[quote]模拟自然除法是不可能的[/quote]
我倒认为模拟自然除法是可能的,而且是第一选择.

可以的。只要你实现了乘法的运算，就可以用乘法来试探。
想象一下你用手算除法，比如1569/36, 要先算15/36，知道取的数字为0，余15，跟着用156/36，试探0，试探1，试探2....发觉到5时候，5*36>156,故取4，余12。跟着用129/36.....如此一直下去。
上面的试探是从0，1，2...这样下去，效率较低。可以改成2分查找的试探。要是10进制，4次之内一定可以得出那个数位的值。

下面给你一段代码。这段代码取自我写的一个Integer类，可以支持无穷精度的计算。总的代码如下，不知道你学过C++没有，没有学过就白搭了。
[url]http://upload.programfan.com/upfile/200702261536767.rar[/url]


// val1, val2都是用string表示的两个数值, 不为负, 不能以"0..."开头("0"除外)
// base是它们所共同采用的基底, 返回val1,val2相除的商
string divide(const string& val1, const string& val2, Base base = 10)
{
        if (val2 == "0")
                throw illegal_value("Divide by 0.");

        if (compare(val1, val2) < 0 || val1 == "0")
                return "0";

        string quotient;
        string dividend_part = val1.substr(0, val2.length()-1);
        string product_part;

        for (int index = val2.length()-1; index<val1.length(); index++)
        {
                dividend_part.append(1, val1[index]);
                clearTheZerosAtFront(dividend_part);

                //下面一段代码采用2分查法，找到商的每一个数位上的值
                //整个过程请联想一下手算除法
                unsigned int first = 0;
                unsigned int last = base;              
                while (true)
                {
                        unsigned int mid = (first+last)/2;                      
                        product_part = multiply(val2, mid, base);

                        if (first == mid)
                                break ;

                        if (compare(product_part, dividend_part) > 0)
                                last = mid;

                        else    first = mid;
                }
                dividend_part = sub(dividend_part, product_part, base);
                quotient.append(1, numToChar(first));
        }

        clearTheZerosAtFront(quotient);
        return quotient;
}

组成原理里面补码除法，加减交替法，不用试除的，不过比较麻烦，尤其是余数的处理，照着书可能我编得出来


另外，我问一下，那个乘法可以用fft，但是在精度误差怎么处理？fft是实数，要算的是整数~就算每一位我用4舍5入，但是如果精度丢失了，比如膨胀得很大，个位不精确了怎么办？

[quote]组成原理里面补码除法，加减交替法，不用试除的，不过比较麻烦，尤其是余数的处理，照着书可能我编得出来


另外，我问一下，那个乘法可以用fft，但是在精度误差怎么处理？fft是实数，要算的是整数~就算每一位我用4舍5入，但是如果精度丢失了，比如膨胀得很大，个位不精确了怎么办？[/quote]

补码除法？马上去google一下看看

有个问题
余数的位数怎么和数组（或string格式字符串）对齐？
自然除法需要把余数按位数和后面的相加再继续除
需要把余数向左移动一位（或几位，这个要看商在这一位是否为0）
也可以使用string风格直接拼接。
我认为最好把被除数分开单独提取到另一个地方进行除法（若位数不够则提取下一位）
也可以先把除数的位数先加一（因为商是0~9的数）再和被除数比较。用除数的位数加一后再减去余数的位数，就是需要向被除数借位的位数

对齐，只要心里对齐就可以了，操作的时候‘对齐’就可以了，不是非要费劲地移动。

用std::string吗，感觉还是直接用C的数组吧，用stl的容器只怕速度有不行；PS高精我一直想做，但都没坚持下来，每次都觉得没什么大用处，long不行就long long，做数学运算用浮点数都够了，圆周率算个几亿位出来，摆在你面前，好像也只能满足一下自己的成就感而已，拿到实际中工程中还不都是浮点数。。

我参加NOIP考试可能会考到的，我也不想做高精度运算啊……………………

好东西，顶一下，学习一下

[quote]可以的。只要你实现了乘法的运算，就可以用乘法来试探。
想象一下你用手算除法，比如1569/36, 要先算15/36，知道取的数字为0，余15，跟着用156/36，试探0，试探1，试探2....发觉到5时候，5*36>156,故取4，余12。跟着用129/36.....如此一直下去。
上面的试探是从0，1，2...这样下去，效率较低。可以改成2分查找的试探。要是10进制，4次之内一定可以得出那个数位的值。

[/quote]
   toyasimple 说的方法可行，但是效率较低。
   实际上，可以用操作数的前导数字之间的商来近似实际的商。前导数字的意思是：一个数的前面N位组成的数。
   举例来说：856991/365442，令前导数字为前3位，则被除数与除数的前导数字依次为：856，365；因此得近似商为2，而实际商的确为2。
   容易看到，前导数字的位数越大，精度越高。若想要增大精度，前导数字的位数可以尽量取得大一些，如取8位等等。