32-битное умножение через 16-битное смещение

Question

Я пишу вызов функции мягкого умножения с использованием сдвига и добавления. Существующий вызов функции выглядит следующим образом:

unsigned long __mulsi3 (unsigned long a, unsigned long b) { 

    unsigned long answer = 0; 

    while(b) 
    { 
     if(b & 1) { 
      answer += a; 
     }; 

     a <<= 1; 
     b >>= 1; 
    } 
    return answer; 
} 

Хотя мое оборудование не имеет множитель, у меня есть жесткий рычаг переключения. Переключатель способен сдвигать до 16 бит за один раз.

Если я хочу в полной мере использовать свой 16-разрядный сдвиг. Любые предложения о том, как я могу адаптировать код выше, чтобы отразить возможности моего оборудования? Данный код сдвигает только 1 бит на итерацию.

16-разрядный сдвигатель может сдвигать 32-разрядные беззнаковые длинные значения до 16 мест за раз. SizeOf (без знака в длину) == 32 бита

Answer 1

Основной подход (предполагается, что сдвиг на 1): -

• Сдвиг верхние 16 бит
• Установите нижний бит из верхних 16 битов старшего бита нижних 16 бит
• Сдвинуть нижние 16 бит

ЗАВИСИТ немного на вашем оборудовании ...

но вы можете попробовать: -

• предполагая, без знака длиной 32 бита
• предполагающего Big Endian

затем: -

union Data32 
     { 
      unsigned long l; 
      unsigned short s[2]; 
     }; 

unsigned long shiftleft32(unsigned long valueToShift, unsigned short bitsToShift) 
{ 
    union Data32 u; 
    u.l = valueToShift 
    u.s[0] <<= bitsToShift; 
    u.s[0] |= (u.s[1] >> (16 - bitsToShift); 
    u.s[1] <<= bitsToShift 

    return u.l; 
} 

затем сделать то же самое в обратном направлении для смещения вправо

Answer 2

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

EX:

0101 
    * 0111 
    ------- 
    0101 
    0101. 
    0101.. 
-------- 
    100011 

, конечно, вы не можете подходите к нему так, если у вас нет ни оператора множителя, ни 1-битного переключателя! , хотя, вы можете сделать это другими способами, например, цикл:

unsigned long _mult(unsigned long a, unsigned long b) 
{ 
    unsigned long res =0; 

    while (a > 0) 
    { 
     res += b; 
     a--; 
    } 

    return res; 
} 

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

Answer 3

Имея 16-битовые сдвиги могут помочь вам сделать небольшое увеличение скорости, используя следующий подход:

 
(U1 * P + U0) * (V1 * P + V0) = 
= U1 * V1 * P * P + U1 * V0 * P + U0 * V1 * P + U0 * V0 = 
= U1 * V1 * (P*P+P) + (U1-U0) * (V0-V1) * P + U0 * V0 * (1-P) 

при условии P является удобной мощностью из 2 (например, 2 ** 16, 2 ** 32), поэтому умножение на него является быстрым сдвигом. Это уменьшает от 4 до 3 умножений меньших чисел и, рекурсивно, O (N ** (3/2)) вместо O (N ** 2) для очень больших чисел.

Этот метод описан, по меньшей мере, в TAoCP от Knuth. Там описаны более сложные версии.

Для небольших количествах (например, 8 на 8 бит), следующий метод быстро, если у вас есть достаточно быстрый диск:

 
a * b = square(a+b)/4 - square(a-b)/4 

если пластинчатый int(square(x)/4), вам потребуется 1022 байт для знака умножения и 510 байт для подписанного.

Answer 4

Возможность сдвига нескольких битов не поможет много, если у вас нет аппаратного умножения, например 8 бит x 8 бит, или вы можете позволить некоторым RAM/ROM сделать (скажем) 4-битный по 4-бит умножить на поиск.

Простой сдвиг и добавление (как вы это делаете) могут помочь в замене аргументов, чтобы множитель был меньше.

Если ваша машина быстрее выполняет 16-битные вещи в целом, а затем обрабатывает 32-битные «a» как «a1: a0» по 16 бит за раз, а также «b», вы просто можете такие же некоторые циклы. Ваш результат составляет всего 32 бита, поэтому вам не нужно делать «a1 * b1» - хотя один или оба из них могут быть равны нулю, поэтому выигрыш может быть невелик! Кроме того, вам нужны только 16 бит 16 бит «a0 * b1», так что это можно сделать полностью 16 бит, но если b1 (если b < = a), как правило, это тоже не является большой победой. Для «a * b0» вам нужно 32-битное «a» и 32-битное добавление в «ответ», но ваш множитель имеет только 16 бит ..., который может или не поможет.

Пропуск прогона множительных нулей может помочь - в зависимости от процессора и любых свойств множителя.

FWIW: Выполнение магии 'a1 * b1', '(a1-a0) * (b0-b1)', 'a0 * b0' и объединение результата с помощью сдвигов, добавлений и вычитаний в моем небольшом опыте , абсолютный кошмар ... признаки «(a1-a0)», «(b0-b1)» и их продукт должны быть соблюдены, что делает немного беспорядок того, что выглядит как симпатичный трюк. К тому времени, когда вы закончите с этим и добавляет и вычитает, вы должны иметь мощное медленное умножение, чтобы все это стоило! При умножении очень, очень длинных целых чисел это может помочь ... но там проблемы с памятью могут доминировать ... когда я это пробовал, это было чем-то вроде разочарования.