如何將殘差數字系統轉換爲混合基數系統？

我理解Residual Number System的概念和Mixed Radix system的概念，但我很難獲得任何轉換方法，我發現它們只適用於簡單的案例研究。如何將殘差數字系統轉換爲混合基數系統？

我開始了Knuth的計算機編程藝術，但是這個轉換理論有點太過分了，一旦歐拉被提及，我就迷了路。維基百科有一個nice section關於這個問題，我試圖here和here但我無法回到我開始的數字。

我找到了一篇很好的文章here (PDF)，我簡化了相關部分here，但我不明白乘法逆和它們的符號。具體來說，y_2 = |（3-19）|（1/31）| _7 | _7 = | 5 * 5 | _7特別是如何| 1/31 | _7 = 5

2013-04-11 eyepatch

我不能肯定，維基百科的文章是正確的。 – 2013-04-12 00:43:49

感謝您的編輯，我閱讀了剩餘數字系統頁面上的對話頁面，[this]（http://en.wikipedia.org/wiki/Chinese_remainder_theorem）值得一讀。 – eyepatch 2013-04-12 17:44:16

乘法逆函數尊重模數（這裏是7）。由於模數7是素數，所以每個數（模7）都有一個倒數。特別是，31_7 = 3_7（因爲31 = 4 * 7 +3 - 對不起，如果我太教學），其反比爲5，因爲3 * 5 = 15 = 1_7。因此，我們可以寫 | 1/31 | _7 = 5

現在

y_2 = |(3 - 19) |(1/31)|_7 |_7 
    = | (-16) * 5 |_7 
    = | 5 * 5 |_7   since -16 = (-3)*7 + 5 
    = 4

來源

2013-04-12 16:26:51 lmsteffan

我現在明白你是如何得到| -16 | _7 = 5的，這是我處理負模量的一種不尋常的方式，但我可以用它來處理。我仍然失去這個|（1/31）| _7 = 5的生意。我明白| 31 | _7 = | 3 | _7，但我沒有跟着你。 3 * 5 = 15，但| 15 | _7 = 0。 – eyepatch 2013-04-12 19:55:43

ahem ... 15 = 2 * 7 + 1，因此| 15 | _7 = 1。 – lmsteffan 2013-04-12 20:27:50

如何將殘差數字系統轉換爲混合基數系統？

回答

相關問題