Was ist auf x64 CPUs der schnellste weg um 128 Bit große Integerzahlen zu dividieren?

Die MMX Einheit erlaubt leider nur 64 Bit große Ganzzahlen.

Gibt es etwas schnelleres ohne auf Gleitkommazahlen auszuweichen?

Mir geht es nur darum große Ganzzahlen zu berechnen.
Oder ist es heutzutage sogar schon schneller Gleitkommezahlen zu berechnen,
weil die SSE Einheiten vielleicht mehr Gleitkommazahlen gleichzeitig berechnen können?

Die SSE-Operationen sind nicht dafür ausgelegt die Register als 128Bit-Register zu benutzen, sondern zu unterteilen um mehrer Operationen auf verschiedenen Zahlen durchzuführen.

Mehr wie 80Bit bekommst du auf der FPU nicht.

Wenn du es schnell haben willst, dann implementier dir doch eine effiziente Division für die 128Bit Integer und vergleich das mit der Performance die die FPU schafft. Wenn du es geschickt machst kannst du die Performance dadurch wieder rausholen, dass du SSE nutzt und somit mehrer Divisionen die langsamer sind gleichzeitig durchführen kannst. Dann wärst du unterm Strich ja wieder schneller.

Noch etwas:

Momentan muß ich vom Modulo Operator gebrauch machen.

Was ich nämlich erreichen will, ist eine 128 Bit große natürliche gerade Zahl
durch die natürlichen Zahlen von 2-255 zu teilen um dann herauszubekommen,
welche der Zahlen zwischen 2-255 bei der Division wieder ein ganzzahliges Ergebnis liefern.

Mein C Code sieht momentan im Prinzip also in etwa so aus,
verwendet hier aber auf 32 Bit Maschinen maximal 32 Bit große Zahlen da ich nicht weiß, wie man von C Code aus die MMX Einheiten ansprechen kann:

#include <stdio.h>

int main()
{
   unsigned int original = 238914674;
   unsigned int divisor = 0;
   unsigned int modulo;

   for (divisor = 2; divisor <= 255; divisor++)
   {
     /* Das gleiche, aber ohne Modulo und If Abfrage
        printf("%d / %d = %f\n", original, divisor, ((double) original/divisor)); */
     modulo = (original%divisor);
     if (modulo == 0)
     {
       printf("%d / %d = %d\n", original, divisor, original/divisor);
     }
   }
   return 0;
}

Dazu habe ich nun 2 Fragen.

1. Frage:
Ist der Modulo Operator überhaupt schnell oder wäre das ganze mit Gleitkommazahlen schneller?

2. Frage:
Wie nutze ich von C Code aus die MMX und SSE Einheiten?
Bzw. wie kann ich 128 Bit große Integertypen bei C verwenden?

Mir geht es hier um pures Numbercrunching, daher sollte der Code so schnell wie möglich sein aber noch von einer Hochsprache wie C gebrauch machen (also kein Assembler oder so).

Tippgeber schrieb:

Die SSE-Operationen sind nicht dafür ausgelegt die Register als 128Bit-Register zu benutzen, sondern zu unterteilen um mehrer Operationen auf verschiedenen Zahlen durchzuführen.

Mehr wie 80Bit bekommst du auf der FPU nicht.

Ach so, das wußte ich nicht.
Ich schätze mal, daß das auch für SSE4 gilt, oder?

Wenn du es schnell haben willst, dann implementier dir doch eine effiziente Division für die 128Bit Integer

Hm, ok, aber wie mache ich das?
Eine 64 Bit CPU kann ja maximal nur 64 Bit große Integerzahlen effizent berechnen.

und vergleich das mit der Performance die die FPU schafft. Wenn du es geschickt machst kannst du die Performance dadurch wieder rausholen, dass du SSE nutzt und somit mehrer Divisionen die langsamer sind gleichzeitig durchführen kannst. Dann wärst du unterm Strich ja wieder schneller.

Wie greife ich von C aus auf die SSE Einheiten zu ohne Assemblercode zu benutzen?

rüdiger

Der GCC bietet ein __uint128_t/__int128_t. Das dürfte ziemlich schnell implementiert sein.

rüdiger schrieb:

Der GCC bietet ein __uint128_t/__int128_t. Das dürfte ziemlich schnell implementiert sein.

THX

sothis_

falls es dich interessiert, ggf. auch den assembleroutput von gcc anschauen, wie er mit __uint128_t und __int128_t bei arithmetischen operationen umgeht

... wenn es Dir darum geht, auf Teilbarkeit durch irgendeine Zahl von 2 bis 255 zu prüfen:

Du musst nur die Primzahlen in diesem Bereich als Teiler testen!
Beispiel: 2^127-1 ist nicht durch 2 teilbar und damit auch nicht durch 4,6,8,...

Die Liste der Primzahlen kannst Du sehr leicht vorberechnen (z.B. http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes).

Wenn Du wiederholt große Zahlen teilen musst, dann kannst Du auf diesem Weg eventuell Arbeit vermeiden und damit Geschwindigkeit gewinnen.

rapso

Integerfrage schrieb:

Die MMX Einheit erlaubt leider nur 64 Bit große Ganzzahlen.

normale division erlaubt das zu nem gewissen grad

mov RAX, [Variable1_128bit_Ptr]
mov RDX, [Variable1_128bit_Ptr+8]
mov RBX, [Variable2_64bit_ptr]
div RBX

jetzt steht in RAX das resultat der division (64bit) und der rest in RDX.

Gibt es etwas schnelleres ohne auf Gleitkommazahlen auszuweichen?

je nachdem wie kritisch dir das ist und welche zahlen du dividieren musst (z.b. ist dividieren durch immer den selben wert eventuell sehr schnell zu machen)

Mir geht es nur darum große Ganzzahlen zu berechnen.
Oder ist es heutzutage sogar schon schneller Gleitkommezahlen zu berechnen,
weil die SSE Einheiten vielleicht mehr Gleitkommazahlen gleichzeitig berechnen können?

division von float ist normalerweise schneller als mit int, selbst ohne sse, aber natuerlich viel ungenauer.

was genau hast du vor?