Частичное или свернутое умножение - кто-нибудь может определить эту функцию?

Question

Я надеюсь на понимание того, что выглядит как частичное умножение.

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

Эта функция повторяется несколько раз, как показано ниже:

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

Есть ли какие-либо комбинации для расчета этого результата?
Как насчет случая, когда х == у?

Любые ссылки на дополнительную информацию помогут ..

Answer 1

Это ранняя форма генератора случайных чисел, часто используемая на миникомпьютерах и небольших мэйнфреймах. Вызов может выглядеть примерно так:

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

Произведите рандомизацию finetune, синхронизируя клавиатуру или подобный действительно случайный, но медленный метод, затем позвоните один раз так:

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

Впоследствии используйте его в качестве PRNG, называя его так:

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

Использовать seednew в качестве PRN.

Фон Нейман однажды выступал за такого рода вычисления для тестовых приложений "Монте-Карло", но позже передумал, когда узнал больше об анализе выходных данных PRNG.

-Аль.

Answer 2

Похоже на странный расчет хеша. Он берет младшие 32 бита из двух чисел, умножает их, берет старшие 32 бита (перемещая их в нижние позиции), умножает их и возвращает сумму.

Я не думаю, что вы можете сделать это проще, но, вероятно, быстрее. Вы можете прервать цикл while, если он снова вернет то же значение.

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

Я не знаю, есть ли высокий шанс закончить цикл раньше.

Answer 3

DoBusyWork (как предположил @RBerteig, имя - красный флаг) может быть способом заставить компилятор не оптимизировать занятый цикл.

Эти проклятые компиляторы становятся настолько умными, что иногда они решают: «О! Вам не нужен цикл! Я вижу, что вы пытаетесь вычислить!» несмотря на ваш реальный интерес как программиста.

Answer 4

LOW пытается взять только 32 младших бита. High перемещает следующие 32 бита вниз на 32 бита. Вся процедура NotMultiply пытается умножить 32 младших бита x и y и добавить их в верхние 32 бита. DoBusyWork делает это n раз.

Если x == y, вы получите HIGH (x) & sup2; + LOW (x) & sup2;.

Я понятия не имею, почему они хотели бы сделать это, хотя. Это своего рода смешивание верхней и нижней половин х и у.