Partielle oder gewickelte Multiplikation - kann jemand diese Funktion identifizieren?

Question

Ich hoffe auf Einblicke in was wie eine partielle Multiplikation aussieht.

#define LOW(x) ((x)&0xffffffff) 
#define HIGH(x) ((x)>>32) 
unsigned long long NotMultiply(unsigned long long x, unsigned long long y) 
{ 
    return HIGH(x)*HIGH(y) + LOW(x)*LOW(y); 
} 

Diese Funktion wird mehrmals wiederholt, wie folgt:

unsigned long long DoBusyWork(unsigned long long x, unsigned long long y, int n) 
{ 
    while (n--) 
      x = NotMultiply(x,y); 
    return x; 
} 

Gibt es irgendwelche Verknüpfungen dieses Ergebnis für die Berechnung?
Was ist für den Fall, wo x == y?

Alle Links zu mehr Informationen würden .. helfen nur die unteren 32 Bits zu nehmen versucht

Answer 1

LOW. High verschiebt die nächsten 32 Bit um 32 Bit. Die ganze NotMultiply-Routine versucht, die unteren 32 Bits von x und y zusammen zu multiplizieren und sie zu den oberen 32 Bits hinzuzufügen. DoBusyWork macht es n mal.

Wenn x == y, erhalten Sie HIGH (x) ² + LOW (x) ².

Ich habe keine Ahnung, warum sie das tun wollen, obwohl. Es wird die obere und untere Hälfte von x und y zusammengemischt.

Answer 2

Sieht aus wie eine seltsame Hash-Berechnung. Es nimmt die unteren 32 Bits von zwei Zahlen, multipliziert sie, nimmt die höheren 32 Bits (verschiebt sie zu den niedrigeren Stellen) und multipliziert sie und gibt die Summe davon zurück.

Ich glaube nicht, dass Sie es einfacher machen können, aber wahrscheinlich schneller. Sie können die while-Schleife unterbrechen, wenn sie den gleichen Wert erneut zurückgibt.

unsigned long long DoBusyWork(unsigned long long x, unsigned long long y, int n) 
{ 
    long long previousX = x; 
    while (n--) 
    { 
      x = NotMultiply(x,y); 
      if (x == previousX) break; 
      previousX = x; 
    } 
    return x; 
} 

Ich weiß nicht, ob es eine hohe Chance gibt, die Schleife früh zu beenden.

Answer 3

DoBusyWork (wie @RBertig vorgeschlagen hat, der Name ist eine rote Flagge) kann eine Möglichkeit sein, den Compiler zu zwingen, eine Busy-Schleife nicht zu optimieren.

Diese verdammten Compiler werden so schlau, dass sie manchmal entscheiden: "Oh! Du brauchst dort keine Schleife! Ich sehe, was du zu berechnen versuchst!" trotz Ihres wirklichen Interesses als Programmierer.

Answer 4

Dies ist eine frühe Form des Zufallszahlengenerators, oft auf Minicomputern und kleinen Mainframes verwendet. Der Aufruf könnte wie folgt aussehen:

unsigned long long seedold = 0xA5A5A5A5A5A5A5A5; 
unsigned long long seednew = 0X5A5A5A5A5A5A5A5A; 
unsigned long long lltmp; 
int finetune; 

Randomize finetune durch die Tastatur oder eine ähnliche wirklich zufällig, aber langsame Methode Timing, dann einmal nennen wie folgt aus:

lltmp = DoBusyWork(seedold, seednew, finetune); 
seedold = seednew; 
seednew = lltmp; 

es anschließend als PRNG verwenden indem Sie es so nennen:

lltmp = DoBusyWork(seedold, seednew, 1); 
seedold = seednew; 
seednew = lltmp; 

Verwenden Sie seednew als die PRN.

Von Neumann hat sich einmal für diese Art von Berechnung für "Monte-Carlo" -Testanwendungen ausgesprochen, aber später änderte er seine Meinung, als er mehr über die Analyse der Ausgabe von PRNGs erfuhr.

-Al.