DIV指令除法溢出-算法推广

今天看汇编语言时了解到DIV指令可能会导致除法溢出，王爽老师提供了一种不会溢出的算法,一时间突发奇想，想到了大整数除法的问题.

一、DIV指令除法溢出以及解决方案

我们知道在进行16位除法时,也就是被除数为32位除数位16位的除法,运算结果是AX存放除法操作的商,DX存放的是除法操作的余数，举一个最简单的例子:若被除数大于65536,除数恰好为1，此时AX无法存放大于65536的值，除法溢出.

那么，如何解决这个问题呢?王爽老师给出一个公式:X/n = int(H/n)65536+(rem(H/n)65536+L)/n 除法操作的商将存在两个寄存器中，现假设A,B寄存器,A寄存器存放高16位，B寄存器存放低16位[其中,int代表取整,rem代表求余数,H代表被除数X的高16位,L代表被除数X的低16位]，下面给出证明:

• 注意到 X/n = (H*65536 + L) / n = (H*65536)/n + L/n [此处不是整数除法，故等式成立]
• 我们知道 H = int(H/n)*n + rem(H/n) 
• 带入步骤一的等式,我们得到:X/n = (H*65536)/n + L/n = [(int(H/n)*n + rem(H/n)) * 65536] / n + L/n
• 化简等式得到:X/n = int(H/n)*65536+(rem(H/n)*65536+L)/n 公式证毕
• 现在证明不会出现溢出:
• 这里会进行两次除法 H/n 和 (rem(H/n)*65536+L)/n
• H/n 显然不会溢出，此时可将操作结果放在A寄存器
• 因为 rem(H/n) < n,L < 65536，要证明除法不会溢出只需证明被除数的最大值((n-1)*65536+65535)/n除n不会溢出
• 显然该结果一定小于65536,不会溢出 证毕

汇编算法实现(AX,DX分别存放商的低位和高位，CX存放余数，算法为DX，AX除CX)

divdw:
    push bx
    push ax
    mov ax,dx
    mov dx,0
    div word ptr cx 
    mov bx,ax
    pop ax
    div word ptr cx
    mov cx,dx
    mov dx,bx
    pop bx
    ret

二、大整数除法

根据上面的思路，我们很容易有推广的想法在更大数据的除法上(虽然效率并不如现有算法)，若大整数除法的除数过小，我们也可以进行上述的算法，用同样的方法可以证明算法的正确性.

static class R{
    ArrayList<Integer> ret = new ArrayList<Integer>();
    int rem = 0 ;
    @Override
    public String toString() {
        return "R [ret=" + ret + ", rem=" + rem + "]";
    }
}
public static R calculate(ArrayList<Integer> arr,int num){
    R r = new R() ;
    int t,l ,f = 1;
    for (int i = 0; i < arr.size(); ++i) {
        r.rem *= 10;
        l = ( arr.get(i) + r.rem ) ;
        t = l / num ;
        if(t == 0 && f == 1 ) {}
        else {
            r.ret.add(t);
            f = 0 ;
        }
        r.rem = l % num ;
    }
    return r ; 
}

calculate函数用一个数组结构arr存放大整数除法被除数的每一位(十进制存储),而num代表除数，采用上面同样的算法.

我们知道Java中一个BigInteger类.点击它的除法源代码，我们可以看到:

    public BigInteger[] divideAndRemainder(BigInteger val) {
        if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
                mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
            return divideAndRemainderKnuth(val);
        } else {
            return divideAndRemainderBurnikelZiegler(val);
        }
    }

这里根据数的大小采用两种不同的算法，当被除数小于80位或者当两个数位数相差小于80位采用Knuth算法，其他情况采用Burnikel-Ziegler算法

• Knuth 大概是一种估算商的减法算法(商比较小的情况)
• Burnikel-Ziegler 与上述算法类似，只是划分方式不同(商比较大的情况)

当然calculate算法是完全比不过这两种算法的，不过也算是一个简单的算法吧，经过测试与JDK的算法相差一个系数相差5-10倍的样子

测试代码：

import java.math.BigInteger;
import java.util.ArrayList;

public class Main {
static class R{
    ArrayList<Integer> ret = new ArrayList<Integer>();
    int rem = 0 ;
    @Override
    public String toString() {
        return "R [ret=" + ret + ", rem=" + rem + "]";
    }
}
    public static int randomInt(){
        return (int)(Math.random() * 100) % 10  ;
    }
    public static ArrayList<Integer> randomNumber(int len){
        ArrayList<Integer> ret = new ArrayList<Integer>();
        int t = randomInt() ;
        while(t == 0 ) t = randomInt() ;
        ret.add(t);
        while(--len != 0) ret.add(randomInt());
        return ret ; 
    }
    public static String randomNumber(ArrayList<Integer> arr){
        StringBuffer sb = new StringBuffer() ;
        for (Integer integer : arr) {
            sb.append(integer) ;
        }
        return sb.toString() ;
    }
    public static R calculate(ArrayList<Integer> arr,int num){
        R r = new R() ;
        int t,l ,f = 1;
        for (int i = 0; i < arr.size(); ++i) {
            r.rem *= 10;
            l = ( arr.get(i) + r.rem ) ;
            t = l / num ;
            if(t == 0 && f == 1 ) {}
            else {
                r.ret.add(t);
                f = 0 ;
            }
            r.rem = l % num ;
        }
        return r ; 
    }
    public static BigInteger[] caculate(BigInteger a,BigInteger b){
        return a.divideAndRemainder(b);
    }
    public static boolean accuracyTest(BigInteger[] b,R r){
        return b[0].toString().equals(randomNumber(r.ret)) && (r.rem+"").equals(b[1].toString()) ;
    }
    public static void main(String[] args) {
        System.out.println("preparing data...");
        ArrayList<ArrayList<Integer>> testSet1 = new ArrayList<ArrayList<Integer>>() ;
        ArrayList<BigInteger> testSet2 = new ArrayList<BigInteger>();
        ArrayList<Integer> testSet3 = new ArrayList<Integer>() ;
        ArrayList<BigInteger> testSet4 = new ArrayList<BigInteger>() ;
        ArrayList<R> retSet1 = new ArrayList<Main.R>();
        ArrayList<BigInteger[]> retSet2 = new ArrayList<BigInteger[]>();
        for (int i = 0; i < 10; i++) {
            testSet1.add(randomNumber(40000));
        }
        for (int i = 0; i < testSet1.size(); i++) {
            testSet2.add(new BigInteger(randomNumber(testSet1.get(i))));
        }
        for (int i = 0; i < testSet1.size(); i++) {
            testSet3.add((int) (Math.random() * Integer.MAX_VALUE / 10) ) ;
            testSet4.add(new BigInteger(""+testSet3.get(i)));
        }
        System.out.println("------------------");
        System.out.println("start testing..");
        long start = System.currentTimeMillis() ; 
        for (int i = 0; i < testSet1.size(); i++) {
            retSet2.add(testSet2.get(i).divideAndRemainder(testSet4.get(i)));
//          retSet1.add(calculate(testSet1.get(i), testSet3.get(i)));

        }
        long end = System.currentTimeMillis() ; 
        System.out.println("calculate algorithm time-elapse : "+ (end - start ));
//      start = System.currentTimeMillis() ;
//      for (int i = 0; i < testSet1.size(); i++) {
//          retSet2.add(testSet2.get(i).divideAndRemainder(testSet4.get(i)));
//      }
//      end = System.currentTimeMillis() ; 
//      System.out.println("jdk algorithm time-elapse : "+ (end - start ));
//      System.out.println("accuracy testing...");
//      int errors = 0 ; 
//      for (int i = 0; i < testSet1.size(); i++) {
//          if(!accuracyTest(retSet2.get(i), retSet1.get(i))){errors++;}
//      }
//      System.out.println("Error count:"+errors);
    }
}