電腦如何找到模數？

是否有一些比特明智的操作很酷的算法？電腦如何找到模數？

2011-03-28 Nate

是，你注意到組裝這聽起來像你想在一個非常低的水平，知道這一點，而不是「從X，直到結果小於y反覆。減去Y」正確的東西像'X MOD y'？提醒我在彙編課程中編寫mul/div例程，並驚訝他們需要多長時間才能成功 – 2011-03-28 04:09:51

正確，我想知道是否有一些聰明的低級別方式，它比O（n）時間要好。 – Nate 2011-03-28 04:13:33

我不確定硬件的功能，但是在大多數指令集中，「模數」和「分頻」都是使用相同的指令完成的。分頻指令被實現爲使得商將被輸出到一個寄存器並且其餘的被同時輸出到第二寄存器。 – aroth 2011-03-28 04:14:41

通常，在處理器上的模數和除法操作是相同的東西。例如，請參閱http://jsimlo.sk/docs/cpu/index.php/div.html。這是在英特爾處理器上執行除法指令。

2011-03-28 04:11:26 Reinderien

在大多數情況下，彈性模量是剛通過將兩個數字進行計算。商被存儲在一個寄存器中，其餘的被存儲在另一個寄存器中。你會追趕剩下的。

2011-03-28 04:14:30

在x mod Y = X - Y *（X/Y）

其中（x/y）爲一個整數除法。

2011-03-28 04:18:09 Vagrant

除了明顯的方法，使用DIV和IDIV如上所述（用於x86）中，由二的冪modulo'd任意數量的結果可以通過採取按位來計算和：x mod y其中Y是POW2是與x AND (y - 1)相同。大多數編譯器執行該時可能的，因爲除法遠遠超過按位OPS

2011-03-28 04:38:19 Necrolis

如果除數是事先已知的（例如，對於由C編譯器產生的代碼，這是在編譯時已知的常數），則整數除法（昂貴從中可以容易地獲得模量）有時可以通過乘法和移位來實現。有關詳細信息，請參閱this article（警告：這不是光讀數）。

在許多處理器，整數乘法是遠遠大於整數除法快;某些處理器甚至沒有一個整數除法操作碼（乘法上Ñ比特值可以被優化成深度的電路O（log n）的，而沒有已知的方法來優化的深度以下除法電路O（n））。

2011-03-28 12:42:09

回答