So berechnen Sie magische Konstanten für die Division durch Multiplikation für eine konstante Modulo-Operation ⇐ C++

[Anonymous]

Ich versuche, die in Clang (und wahrscheinlich auch anderen Compilern) durchgeführte Optimierung „Dividieren durch Multiplizieren“ zu reproduzieren, wenn ich die folgende Operation ausführe (zur Verwendung in meinem eigenen Compiler):

Code: Select all

bool modulo(uint64_t value)
{
constexpr auto CONSTANT = 5;
return value % CONSTANT == 0;
}

Für meinen Zweck kann davon ausgegangen werden, dass „KONSTANTE“ eine Primzahl (also eine ungerade Zahl) innerhalb der ersten 2048 Primzahlen ist.

Dies führt somit zu der folgenden Anordnung für alle Konstanten (wobei nur die magischen Zahlen geändert werden):

Code: Select all

modulo(unsigned long): // example here for "CONSTANT==5"
movabs rax, -3689348814741910323
imul rax, rdi
movabs rcx, 3689348814741910324
cmp rax, rcx
setb al
ret

Meine Frage ist: Wie berechnet man diese Zahlen zuverlässig? Da ich mich nicht besonders mit Mathematik auskenne, würde ich mich über Beispielcode in C++ (oder einer ähnlichen Sprache, damit ich ihn übersetzen kann) freuen und nicht nur über eine theoretische Erklärung.
Ich habe bereits eine Möglichkeit gefunden, die zweite Konstante für den Vergleich zu berechnen, grob basierend auf der Quelle von Hackers Delight und libdivde:

Code: Select all

struct DivMagic64 {
int64_t magic;
uint64_t cmpConst;
};

constexpr DivMagic64 computeDivMagic(uint64_t d) {
assert(d >= 1 && (d & 1)); // only works for odd divisors

const uint64_t cmpConstant = ~uint64_t(0) / d + 1;

int64_t magic = ???;

return { magic, cmpConstant };
}

Das Hauptproblem liegt in der ersten magischen Konstante. Für bestimmte Teiler wie „5“ kann er als „1 – cmpConstant“ berechnet werden, ich habe jedoch keine Ahnung, wie Clang zu dem Wert für einen Teiler wie 2573 kommt:

Code: Select all

movabs rax, -5570586920043653947 // ???
imul rax, rdi
movabs rcx, 7169352535448719 // correctly calculated in computeDivMagic
cmp rax, rcx

Ich habe auch versucht, den oben genannten Quellcode direkt für Berechnungen zu verwenden, allerdings erfordern sie anscheinend die Durchführung zusätzlicher Operationen an der Dividende, was clang bei seinen Berechnungen offenbar zu vermeiden scheint.