[發(fā)明專利]一種計(jì)算整數(shù)的模數(shù)除法的余數(shù)的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 200810097696.9
• 申請(qǐng)日: 2008-05-23
• 公開（公告）號(hào): CN101276268A
• 公開（公告）日: 2008-10-01
• 發(fā)明（設(shè)計(jì)）人: 黃建;徐晶;丁國(guó)榮;許煒;范兵;汪進(jìn);陳麗萍;張偉偉
• 申請(qǐng)（專利權(quán)）人: 武漢飛思科技有限公司
• 主分類號(hào): G06F7/72
• 分類號(hào): G06F7/72;G06F7/535
• 代理公司: 北京捷誠(chéng)信通專利事務(wù)所
• 代理人: 魏殿紳;龐炳良

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算模數(shù)的方法，具體的說(shuō)是一種計(jì)算整數(shù)的模數(shù)除法的余數(shù)的方法。

背景技術(shù)

整數(shù)m的模數(shù)值n，通常將其記為m?mod?n。求整數(shù)的模數(shù)有很大的現(xiàn)實(shí)意義，因?yàn)樵诤芏嗲闆r下都需要求整數(shù)的模數(shù)，比如在某些負(fù)載均衡方法，分組交換和傳輸，數(shù)字消息編/譯碼，計(jì)算機(jī)圖形學(xué)，除法運(yùn)算中等。

在現(xiàn)有的取模的算法中存在兩個(gè)方面的問(wèn)題：

1)傳統(tǒng)的算法是通過(guò)迭代來(lái)實(shí)現(xiàn)的，這種迭代的方式使得計(jì)算需要很大的計(jì)算量。如果除數(shù)D＝2N-1(N為自然數(shù))為n位整數(shù)，被除數(shù)M為小于或等于(D-1)²的任何正整數(shù)，即M最大時(shí)為2n位整數(shù)，傳統(tǒng)的迭代方法需要6n次條件測(cè)試，2n次的乘法(或移位)和2n次加法。因此整個(gè)方法需要10n次還不包括賦值操作。由此可見計(jì)算量之大，不過(guò)被除數(shù)和除數(shù)可以取任意值。

2)專利99109437.9提出一種計(jì)算模數(shù)除法的余數(shù)的非迭代方法，解決了由于迭代導(dǎo)致的計(jì)算量大的問(wèn)題，該算法不依賴于模數(shù)運(yùn)算除數(shù)的位數(shù)。但是這個(gè)算法有兩個(gè)前提條件就是除數(shù)的值必須等于2N-1(N為自然數(shù))，被除數(shù)的值應(yīng)當(dāng)小于或等于(D-1)²，但是大于或等于0。這就說(shuō)明這種計(jì)算方法不能應(yīng)用于被除數(shù)和除數(shù)為任意值得情況。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服上述不足之處，提供一種計(jì)算整數(shù)的模數(shù)除法的余數(shù)的方法，該方法采用流水線處理方式，便于硬件實(shí)現(xiàn)，克服了傳統(tǒng)迭代方法的計(jì)算量大的不足，而且對(duì)于除數(shù)和被除數(shù)沒(méi)有特定的限制。

為達(dá)到以上目的，本發(fā)明采取的技術(shù)方案是：

一種計(jì)算整數(shù)的模數(shù)除法的余數(shù)的方法，其特征在于：其計(jì)算步驟如下：

(1)通過(guò)和計(jì)算裝置連接的輸入設(shè)備或通過(guò)和計(jì)算裝置連接的存儲(chǔ)設(shè)備獲取被除數(shù)M、除數(shù)D，判斷M和D的大小關(guān)系：如果M＜D，則余數(shù)R＝M，結(jié)束計(jì)算，否則轉(zhuǎn)(2)；

(2)將被除數(shù)M轉(zhuǎn)換成二進(jìn)制位M＝M₀×2⁰+M₁×2¹+…+M_n-1×2^n-1，獲取各個(gè)權(quán)值的系數(shù)M_i(i＝0□n-1)和二進(jìn)制的位數(shù)n；

(3)根據(jù)被除數(shù)M確定流水線處理第1級(jí)輸入?yún)?shù)的個(gè)數(shù)：如果2^j＜M≤2^2j，其中j為集合{1，2，4，……，2^m}中的一個(gè)值，m為自然數(shù)，那么流水線處理第1級(jí)輸入?yún)?shù)的個(gè)數(shù)N＝2j；

(4)根據(jù)各個(gè)權(quán)值的系數(shù)M_i的結(jié)果查存儲(chǔ)在計(jì)算裝置內(nèi)的余數(shù)表，得到r_i(i＝0，1…n-1)：當(dāng)M_i＝1(i＝0～n-1)時(shí)獲取余數(shù)表中除數(shù)D所在行和M_i對(duì)應(yīng)的權(quán)值2ⁱ所在列的值r_i，當(dāng)M_i＝0時(shí)，r_i＝0；

(5)確定流水線處理第1級(jí)的輸入?yún)?shù)：由(3)知流水線處理的第1級(jí)有N個(gè)輸入?yún)?shù)，由(2)知被除數(shù)被表示成二進(jìn)制時(shí)的位數(shù)n，那么這N個(gè)輸入?yún)?shù)R_1i(i＝0…N-1)中的n個(gè)參數(shù)R_1i(i＝0…n-1)即為(4)中所得到的r_i(i＝0，1…n-1)的值，剩下的N-n個(gè)輸入值均為0，即R_1i＝0(i＝n，…N-1)；

(6)確定流水線級(jí)數(shù)及每級(jí)子處理程序的數(shù)量：由(3)知第1級(jí)流水線處理輸入?yún)?shù)的個(gè)數(shù)N＝2j，則N＝2^q，即j＝2^q-1，那么流水線處理級(jí)數(shù)為q，第1級(jí)流水線處理有2^q-1個(gè)子處理流程，以此類推，第k級(jí)流水線處理有2^q-k+1個(gè)輸入?yún)?shù)，有2^q-k個(gè)子處理流程；

(7)確定子處理流程的輸入?yún)?shù)：每個(gè)子處理流程有兩個(gè)輸入?yún)?shù)，對(duì)于第k級(jí)流水線處理總共有2^q-k+1個(gè)輸入?yún)?shù)R_ki(i＝0，1，…，2^q-k+1-1)，將這2^q-k+1個(gè)輸入?yún)?shù)兩兩分組，作為2^q-k個(gè)子處理流程的輸入，即第i-1，i(i＝2，4，6，…2^q-k+1)個(gè)參數(shù)R_k(i-2)，R_k(i-1)作為第i/2個(gè)子處理流程的兩個(gè)輸入?yún)?shù)；