多倍無符號減法，用C

我想實現多倍無符號減法，在在C有限域（P = 2^191-19），但我無法弄清楚如何處理借位！我的操作數在基數2^16表示爲：多倍無符號減法，用C

typedef unsigned long long T[12];

這意味着T型陣列的每個元件具有完全相同的16比特數據（基數2^16表示）。現在我想減去T形的兩個操作數，但我不知道哪一個是小！如果結果爲負數，我想將結果添加到素數值以在模算術中獲得積極結果。這裏是基於this書頁-30（多倍減法算法）我的實現：

void bigint192_sub(T r, const T a, const T b){ 
    int i; 
    int borrow; 
    r[0] = a[0] - b[0]; 
    borrow = r[0] >> 16; 
    r[0] &= 0xFFFF; 
    for(i=1;i<12;++i){ 
     r[i] = a[i] - b[i] - borrow; 
     borrow = r[i] >> 16; 
     r[i] &= 0xFFFF; 
    } 
}

但我答錯了！

My inputs: 
a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576 
b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72 
Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604 
Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604

來源

2017-03-25 A23149577

你的投入是什麼，你的預期產出和實際產出是多少？ –

這看起來不對。如果a [i]小於'b [i]'，你會不會從'0x10000'借錢？ –

@KerrekSB我在我的問題中提到了一個參考。我知道它似乎也連接到了我，但這正是書中顯示的方式！ – A23149577

您應該修復borrow評價，因爲這可能只是0或1。所以，你應該把下溢borrow等於1：

borrow = (r[i] >> 16) != 0;

而且我已經重寫功能多一點的一般形式，因爲我們會將首次通過像我們沒有借：

void bigint192_sub(T r, const T a, const T b){ 
    int i; 
    int borrow; 
    for (borrow = 0, i = 0; i < 12; ++i) { 
     r[i] = a[i] - b[i] - borrow; 
     borrow = (r[i] >> 16) != 0; 
     r[i] &= 0xFFFF; 
    } 
}

來源

2017-03-26 00:27:57 Sergio

你也可以寫'borrow =（r [i] >> 16）！= 0; //不需要招comment' – Darklighter

@Darklighter哦，是的，這是更簡單。謝謝！ – Sergio

多倍無符號減法，用C

回答

相關問題