0

サイズが255バイトまでの整数を8ビット整数で除算するアルゴリズムを作成しました。これは、実行したテストで機能します。誰かがそれについてのコメントや改善の提案がありますか？この目的のためのより良いアルゴリズムはありますか？bignum by bignum除算アルゴリズムは必要ありません。2番目の整数は、8ビット整数です。

これまでの最良の解決策（スモールエンディアン）：

typedef struct{
    u_int8_t * data;
    u_int8_t length;
}CBBigInt;
void CBBigIntEqualsDivisionByUInt8(CBBigInt * a,u_int8_t b,u_int8_t * ans){
    // base-256 long division.
    u_int16_t temp = 0;
    for (u_int8_t x = a->length-1;; x--) {
        temp <<= 8;
        temp |= a->data[x];
        ans[x] = temp / b;
        temp -= ans[x] * b;
        if (!x)
            break;
    }
    a->length -= ans[a->length-1]? 0 : 1; // If last byte is zero, adjust length.
    memmove(a->data, ans, a->length); // Done calculation. Move ans to "a".
}

ビッグエンディアンを使用した古いソリューション：

それはによって動作します：

  1. 除数が2の累乗の場合は、少し右にシフトします。
  2. それ以外の場合は、除数が被除数より大きくなる前に左にシフトする必要がある量を計算し、16ビット整数を左にシフトしたかのように除数にします。これは減算に使用されます。
  3. 回答のシフト量に対応するビットを設定します。行われたのは、2の累乗までの除数に配当が収まる量が見つかったことです。
  4. シフトされたバイトを被除数から取り除き、剰余を作成します。
  5. 除数が剰余より大きくなるまで、剰余についてステップ2から繰り返します。これが発生すると、答えが見つかります。
typedef struct{
    u_int8_t * data;
    u_int8_t length;
}CBBigInt;
u_int8_t CBPowerOf2Log2(u_int8_t a){
    switch (a) {
        case 1:
            return 0;
        case 2:
            return 1;
        case 4:
            return 2;
        case 8:
            return 3;
        case 16:
            return 4;
        case 32:
            return 5;
        case 64:
            return 6;
    }
    return 7;
}
u_int8_t CBFloorLog2(u_int8_t a){
    if (a < 16){
        if (a < 4) {
            if (a == 1){
                return 0;
            }
            return 1;
        }
        if (a < 8){
            return 2;
        }
        return 3;
    }
    if (a < 64){
        if (a < 32) {
            return 4;
        }
        return 5;
    }
    if (a < 128){
        return 6;
    }
    return 7;
}
void CBBigIntEqualsRightShiftByUInt8(CBBigInt * a,u_int8_t b){
    u_int8_t deadBytes = b / 8; // These bytes fall off the side.
    a->length -= deadBytes; // Reduce length of bignum by the removed bytes
    u_int8_t remainderShift = b % 8;
    if (!remainderShift) { // No more work
        return;
    }
    u_int16_t splitter;
    u_int8_t toRight = 0; // Bits taken from the left to the next byte.
    for (u_int8_t x = 0; x < a->length; x++) {
        splitter = a->data[x] << 8 - remainderShift; // Splits data in splitters between first and second byte.
        a->data[x] = splitter >> 8; // First byte in splitter is the new data.
        a->data[x] |= toRight; // Take the bits from the left
        toRight = splitter; // Second byte is the data going to the right from this byte.
    }
}
void CBBigIntEqualsDivisionByUInt8(CBBigInt * a,u_int8_t b,u_int8_t * ans){
    if (!(b & (b - 1))){
        // For powers of two, division can be done through bit shifts.
        CBBigIntEqualsRightShiftByUInt8(a,CBPowerOf2Log2(b));
        return;
    }
    // Determine how many times b will fit into a as a power of two and repeat for the remainders
    u_int8_t begin = 0; // Begining of CBBigInt in calculations
    bool continuing = true;
    u_int8_t leftMost;
    bool first = true;
    while (continuing){
        // How much does b have to be shifted by before it becomes larger than a? Complete the shift into a shiftedByte
        int16_t shiftAmount;
        u_int16_t shiftedByte;
        if (a->data[begin] > b){
            shiftAmount = CBFloorLog2(a->data[begin]/b);
            shiftedByte = b << 8 + shiftAmount;
        }else if (a->data[begin] < b){
            shiftAmount = -CBFloorLog2(b/a->data[begin]);
            shiftedByte = b << 8 + shiftAmount;
            // Shift right once again if "shiftedByte > (a->data[begin] << 8) + a->data[begin+1]" as the shifted divisor should be smaller
            if (shiftedByte > ((a->data[begin] << 8) + a->data[begin+1])){
                shiftedByte >>= 1;
                shiftAmount--; // Do not forget about changing "shiftAmount" for calculations
            }
        }else{
            shiftAmount = 0;
            shiftedByte = b << 8;
        }
        // Set bit on "ans"
        if (shiftAmount < 0){ // If "shiftAmount" is negative then the byte moves right.
            ans[begin+1] |= 1 << (8 + shiftAmount);
            if (first) leftMost = 1;
        }else{
            ans[begin] |= 1 << shiftAmount; // No movement to right byte, jsut shift bit into place.
            if (first) leftMost = 0;
        }
        first = false; // Do not set "leftMost" from here on
        // Take away the shifted byte to give the remainder
        u_int16_t sub = (a->data[begin] << 8) + a->data[begin+1] - shiftedByte;
        a->data[begin] = sub >> 8;
        if (begin != a->length - 1) 
            a->data[begin + 1] = sub; // Move second byte into next data byte if exists.
        // Move along "begin" to byte with more data
        for (u_int8_t x = begin;; x++){
            if (a->data[x]){
                if (x == a->length - 1)
                    // Last byte
                    if (a->data[x] < b){
                        // b can fit no more
                        continuing = false;
                        break;
                    }
                begin = x;
                break;
            }
            if (x == a->length - 1){
                continuing = false; // No more data
                break;
            }
        }
    }
    a->length -= leftMost; // If the first bit was onto the 2nd byte then the length is less one
    memmove(a->data, ans + leftMost, a->length); // Done calculation. Move ans to "a".
}

ありがとう！

4

1 に答える 1

2

これを「基数 2 の長い除算」と表現します。より良い代替手段は、「base 256 long division」です。

これは（テストされておらず、おそらくバグのある）例です：

typedef struct{
    u_int8_t * data;
    u_int8_t length;
} CBBigInt;


u_int8_t CBBigIntEqualsDivisionByUInt8(CBBigInt * a, u_int8_t b, u_int8_t * ans) {
    int i;
    unsigned int temp = 0;

    i = a.length;
    while(i > 0) {
       i--;
       temp <<= 8;
       temp |= a.data[i];
       ans.data[i] = temp / b;
       temp -= ans.data[i] * b;
    }
    return temp;   // Return remainder
}
于 2012-05-09T23:22:35.730 に答える