De Bruijn-Algorithmus Binärzahl zählen 64Bits C #
Ich benutze den "De Bruijn" -Algorithmus, um die Anzahl der Binärstellen zu ermitteln, die eine große Zahl (bis zu 64 Bit) hat.
Zum Beispiel:
- 1022 hat 10 Ziffern in binärer Form.
- 130 hat 8 Ziffern in binär.
Ich habe festgestellt, dass die Verwendung einer Tabellensuche basierend auf De Bruijn es mir ermöglicht, diese x100-mal schneller zu berechnen als herkömmliche Methoden (Kraft, Quadrat, ...).
Laut dieser Website hat 2 ^ 6 die Tabelle, um die 64-Bit-Zahlen zu berechnen. Dies wäre die in c #
freigelegte Tabelle %Vor%(Ich weiß nicht, ob ich die Tabelle richtig von dieser Website mitgebracht habe) Dann, basierend auf dem R. Kommentar hier . Ich sollte dies verwenden, um die Tabelle mit der Eingabe-Uint64-Nummer zu verwenden.
%Vor%Aber der c # -Compiler erlaubt mir nicht, 0x022fdd63cc95386dull zu verwenden, weil es 64bits überläuft. Und ich muss stattdessen " 0x022fdd63cc95386d " verwenden.
Diese Codes verwenden. Das Problem ist, dass ich nicht das richtige Ergebnis für die Eingabe bekomme.
Zum Beispiel 1.000.000 Berechnungen der Zahl: 17012389719861204799 (64 Bits verwendet) Dies ist das Ergebnis:
- Mit der pow2 Methode erhalte ich das Ergebnis 64 1 Million mal in 1380ms.
- Mit DeBruijn Methode erhalte ich das Ergebnis 40 1 Million mal in 32ms. (Ich weiß nicht, warum 40)
Ich versuche zu verstehen, wie "De Bruijn" funktioniert, und wie kann ich das beheben und einen endgültigen Code für c # erstellen, um Zahlen bis zu 64 Bit zu berechnen.
UDPATE und Benchmarks für verschiedene Lösungen
Ich war auf der Suche nach dem schnellsten Algorithmus, um die Anzahl der Binärstellen zu erhalten, die eine nicht vorzeichenbehaftete Anzahl von 64 Bits in c # hat (bekannt als ulong).
Zum Beispiel:
- 1024 hat 11 Binärstellen. (2 ^ 10 + 1) oder (log2 [1024] +1)
- 9223372036854775808 hat 64 Binärstellen. (2 ^ 63 + 1) oder (log2 [2 ^ 63] +1)
Die konventionelle Potenz von 2 und Square ist extrem langsam. und nur für 10000 Berechnungen benötigt es 1500ms, um die Antwort zu bekommen. (100M Berechnungen brauchen Stunden).
Hier, Niklas B. , Jim Mischel und Spender brachten verschiedene Methoden, um dies schneller zu machen. p>
- SIMD- und SWAR-Techniken // Zur Verfügung gestellt von Spender (Antwort hier )
- De_Bruijn Geteilte 32Bits // Zur Verfügung gestellt von Jim Mischel (Antwort hier )
- De_Bruijn 64bit Version // Zur Verfügung gestellt von Niklas B. (Antwort hier )
- De_Bruijn 128bit Version // Wird auch von Niklas B. zur Verfügung gestellt (Antwort hier )
Das Testen dieser Methoden mit einer CPU Q6600, die mit Windows 7 (64Bits) auf 3GHz übertaktet wird, ergibt die folgenden Ergebnisse.
Wie Sie sehen können, dauert es nur ein paar Sekunden, um 100.000.000 Anfragen korrekt zu finden, da De_Bruijn die Version mit 128 Bit am schnellsten ist.
Vielen Dank an euch alle, ihr helft mir sehr dabei. Ich hoffe, das hilft dir auch.
4 Antworten
Sie sollten R .. 's Antwort und seine Ressource erneut. Die Frage, auf die er antwortete, war, wie man log2 für Potenzen von zwei findet.
Die Bit-Twiddling-Website sagt, dass die einfache Multiplikation + Verschiebung nur funktioniert "Wenn Sie wissen, dass v eine Potenz von 2 ist". Andernfalls müssen Sie zuerst auf die nächste Potenz von zwei runden:
%Vor%Hier ist eine Version mit einer größeren Nachschlagetabelle, die die Verzweigung und eine Addition vermeidet. Ich habe die magische Zahl mit zufälliger Suche gefunden.
%Vor% Sie sollten auf jeden Fall andere Tricks zum Berechnen von log2 prüfen und überlegen, ob Sie MSR Assembly-Anweisung, wenn Sie auf x86 (_64) sind. Es gibt Ihnen den Index des höchstwertigen gesetzten Bits, das genau das ist, was Sie brauchen.
Nachdem verschiedene Bit-Twiddling Info, so würde ich es machen ... weiß nicht, wie sich das neben DeBruijn stapelt, sollte aber deutlich schneller sein als Mächte einzusetzen.
%Vor%Als ich das eine Weile für 32 Bits zurücksah, war die DeBruijn-Sequenzmethode bei weitem die schnellste. Siehe Ссылка
Was Sie für 64 Bits tun könnten, ist die Aufteilung der Zahl in zwei 32-Bit-Werte. Wenn die hohen 32 Bits nicht Null sind, dann führe die DeBruijn-Berechnung darauf aus und füge dann 32 hinzu. Wenn die hohen 32 Bits Null sind, führe die DeBruijn-Berechnung auf den niedrigen 32 Bits durch.
In etwa so:
%Vor%Bearbeiten: Diese Lösung wird nicht empfohlen, da sie eine Verzweigung für Null erfordert.
Nachdem ich Niklas B's Antwort gelesen hatte, verbrachte ich ein paar Stunden damit, dies zu erforschen, und erkannte, dass alle magischen Multiplikatoren in der letzten sein mussten n th, um für die Nachschlagetabelle mit 64 Elementen zu passen (ich habe nicht das notwendige Wissen, um warum zu erklären).
Also habe ich genau denselben Generator verwendet, der von dieser Antwort erwähnt wurde, um die letzte Sequenz , hier ist der C # -Code:
%Vor%Tags und Links algorithm c# performance count digit