Partial, or wrapped multiplication - can anyone identify this function ?

Question

I am hoping for insight into what looks like a partial multiplication.

#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);
}

This function is iterated multiple times, as follows:

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

Are there any shortcuts for calculating this result ?
What about for the case where x == y?

Any links to more information would help..

Answer 1

Looks like a strange hash calculation. It takes the lower 32 bits of two numbers, multiplies them, takes the higher 32 bits (moving them to the lower places) and multiplies them, and returns the sum of it.

I don't think that you can make it simpler, but probably faster. You can break the while loop if it returns the same value again.

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;
}

I don't know if there is a high chance to finish the loop early.

Answer 2

DoBusyWork (as @RBerteig has suggested, the name is a red flag) may be a way to force the compiler to not optimize a busy-loop.

These darned compilers are getting so smart that sometimes they decide, "Oh! You don't need a loop there! I see what you're trying to calculate!" despite your real interest as a programmer.

Answer 3

This is an early form of random number generator, often used on minicomputers and small mainframes. The call might look something like this:

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

Randomize finetune by timing the keyboard or some similar truly random but slow method, then call once like this:

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

Subsequently use it as a PRNG by calling it like this:

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

Use seednew as the PRN.

Von Neumann once advocated this kind of calculation for "Monte-Carlo" testing applications but later changed his mind when he learned more about analyzing the output of PRNGs.

-Al.