快速模3或除法算法？

是否有快速算法，類似於2的冪，其可以與3一起使用，即n％3。也許有些事情，如果數字的總和可以被三整除，那麼這個數字也是可以被整除的。快速模3或除法算法？

這導致下一個問題。在數字中添加數字的快速方法是什麼？即37 - > 3 +7 - > 10 我要尋找的東西，沒有條件語句那些傾向於抑制量化

感謝

2009-11-08 Anycorn

在這種情況下添加數字將不起作用，因爲您必須先將數字轉換爲十進制數字，而不是僅僅分割多一點的時間。 – 2009-11-08 18:01:42

你究竟在做什麼？除非有一些理論上的好奇心，否則我懷疑這個具體的問題可能是真實世界應用的瓶頸...... – 2009-11-08 18:01:54

它既實用又理論。這個問題來自於嘗試在線程之間分配多個嵌套在笛卡爾中心上的循環（Cuda具體但並不重要）。我已經用另一種方式解決了這個問題，但仍然想知道是否有辦法。這是一個真正的瓶頸，因爲整數除法和模數比我試圖進行的實際浮點運算要昂貴得多。 – Anycorn 2009-11-08 18:18:36

4 % 3 == 1，所以(4^k * a + b) % 3 == (a + b) % 3。你可以利用這一點來評估X％3的32位x：

x = (x >> 16) + (x & 0xffff); 
x = (x >> 10) + (x & 0x3ff); 
x = (x >> 6) + (x & 0x3f); 
x = (x >> 4) + (x & 0xf); 
x = (x >> 2) + (x & 0x3); 
x = (x >> 2) + (x & 0x3); 
x = (x >> 2) + (x & 0x3); 
if (x == 3) x = 0;

（未經檢驗的 - 你可能需要一些更多的削減）這是速度比你的硬件可以做X％3？如果是這樣，它可能不是太多。

來源

2009-11-08 18:22:39

這真的比'x％3'快嗎？請參閱https://godbolt.org/g/aRbqrW – plasmacel 2017-07-27 20:06:06

不知道你的第一個問題，但對於你的第二個，你可以採取優勢%運營商和整數除法：

int num = 12345; 
int sum = 0; 
while (num) { 
    sum += num % 10; 
    num /= 10; 
}

這工作，因爲12345 % 10 = 5，12345/10 = 1234和繼續下去，直到num == 0

來源

2009-11-08 18:14:57

+1尼斯＃2。解。 – 2009-11-08 18:21:15

是的，這是顯而易見的解決方案。然而，在我的平臺上進行分區和模數的操作非常昂貴，大約有幾百個循環。我更感興趣的東西，不涉及那些。我不得不說這是一個純粹的好奇心問題。 – Anycorn 2009-11-08 18:28:49

comp.compilers item這具有用於計算模3.

的替代，特別是如果被除數的maximium大小是適度的具體建議，是3的倒數作爲固定點值相乘，以足夠的精確位來處理最大大小的分紅來計算商，然後從分紅中減去3 *商以得到餘數。所有這些乘法都可以用一個固定的移位和相加序列來實現。指令的數量將取決於倒數的位模式。當股息最小的時候，這種做法非常有效。

關於加數字的號碼...如果你想添加的小數位數，你會最終會做什麼相當於數轉換到十進制，這10分包括某處。如果你願意在base2中加入數字，你可以通過簡單的右移和添加循環來完成。可以使用各種聰明的技巧以N位數據塊的形式做到這一點，以加快速度。

來源

2009-11-08 18:55:35

快速模3或除法算法？

回答

相關問題