Как рассчитать сумму последовательности степеней 2 в x86? - PullRequest
Новая
       56

Как рассчитать сумму последовательности степеней 2 в x86?

0 голосов
/ 08 июня 2019

Я хочу вычислить последовательность показателей степени основания 2. Например, если дано 3, программа рассчитает (2 ^ 3 + 2 ^ 2 + 2 ^ 1 + 2 ^ 0).Проблема в том, что я не могу вычислить показатель степени, чтобы быть с.

Я попытался shl, чтобы вычислить показатель, и я попытался цикл.Ни один из них не дает правильного результата, моя последняя попытка приведена ниже. 

.586
.MODEL FLAT
INCLUDE io.h                            
.STACK 4096

.DATA

        Exponent    DWORD   ?           
        Prompt  BYTE    "Enter an exponent", 0

        Base        DWORD  2

        string      BYTE    40 DUP (?)

        resultLbl   BYTE    "The solution is", 0
        Solution    DWORD   20 DUP (?), 0

.CODE
_MainProc PROC

    input   Prompt, string, 40      ; read ASCII characters (N)
        atod    string              ; ascii to double
        mov     exponent, eax       ; store in memory     


        push Exponent
        push Base

        call function
        add esp, 8

        dtoa   Solution, eax         ; convert to ASCII characters
        output  resultLbl, Solution   ; output label and sum



                mov     eax, 0      ; exit with return code 0
        ret

_MainProc ENDP


;@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
; Procedure takes base and exponent from main

Function PROC
    push ebp                      ; stores base pointer
    mov  ebp, esp                 ; set base pointer to current position

    mov ebx, [ebp + 12]   ; read base (2)
    mov ecx,  [ebp + 8]       ; read N



    MainLoop:           ; loop to calculate expoent
          mul ebx           ; multiply base by its self
          add eax, ebx           ; save answer in eax
          dec ecx                ; decrement the exponent
          cmp ecx, 0             ; check if exponent is 0 yet
          je exit                ; Exit if exponent is 0
          jg mainloop            ; stay in loop if exponent is above 0

    Exit: 

        pop ebp                   ; restore base pointer 
        ret

function ENDP



END

Я хочу, чтобы программа выдала правильный результат экспоненты, и если вы можете вычислить последовательность выше, например, если задано 3, программа рассчитает(2 ^ 3 + 2 ^ 2 + 2 ^ 1 + 2 ^ 0).

1 Ответ

4 голосов
/ 09 июня 2019

База 2 - это особый случай, потому что компьютеры используют двоичные целые числа.

2^n = 1 << n, т.е. 2 n = 1 смещение влево n раз.т.е. эта битовая позиция установлена.

Вы запрашиваете 2^0 + 2^1 + ... 2^n. Число со всеми битами, настроенными на включающий бит n.
Это на 1 меньше, чем 2^(n+1), поэтому требуемое число равно 2^(n+1) - 1.

x86 имеет инструкцию для установки бита в заданной позиции в регистре: bts reg, reg = Проверка и установка битов . В процессорах Intel, reg-reg форма декодирует в один моп, с задержкой в ​​1 цикл.(https://agner.org/optimize/) Он также помещает старое значение бита в CF, но обычно мы не заботимся об этом, когда используем его для этого. Обычно мы просто обнуляем регистр назначения и используем BTS для установки одного бита.

На Райзене bts reg,reg - это 2 мопа, а сдвиги с переменным счетом - одиночные, так что mov edx, 1 / shl edx, cl тоже хорошо, но это хуже для размера кода и больше мопов наПроцессоры Intel.

На процессорах семейства Intel Sandybridge shl reg, cl декодируется до 3 моп. BMI2 shlx reg, reg, reg равен 1 моп, но поддержка BMI2 все еще далекаиз того, что вы можете предположить, к сожалению.

(BTS-получатель памяти с источником регистров работает очень медленно, обрабатывая источник как индексацию в виде битовой строки произвольной длины, а не просто адресуемого слова, как обычноизбегайте его из-за производительности.)

Расчет 2^(n+1) - 1 без переполнения

( C версия этого ответа на другой вопрос , с выводом компилятора.)

Если мы просто добавили 1 к номеру ввода перед feediЧто касается BTS, он может обернуться и не работать для 31 (который должен установить все биты, но вместо этого установить бит 32%32 = 0)

Поскольку нам нужна одна дополнительная инструкция после чтения ввода в любом случаемы можем использовать инструкцию x86 shift-and-add (LEA), чтобы сделать еще один сдвиг , так как мы вычитаем 1. Так что с n=31 мы начинаем с установленного старшего бита и сдвигаем его, чтобы получить ноль,Вычитание 1 затем устанавливает все биты, как нужно 

xor    edx,edx                 ; edx = 0
bts    edx, eax                ; edx |=  1<<eax
lea    edx, [edx + edx - 1]    ; edx = (edx<<1) - 1

Логика для этого выглядит следующим образом 

n      BTS result (2^n)    *2 - 1
0    ->       1         ->   1        = 2 - 1
1    ->       2         ->   3        = 4 - 1
2    ->       4         ->   7        = 8 - 1
3    ->       8         ->  15        = 16 - 1
...
30   ->  0x40000000     ->  0x7FFFFFFF  = 0x80000000 - 1
31   ->  0x80000000     ->  0xFFFFFFFF  = 0 - 1

Это не совпадение, что последний столбец является промежуточной суммой 2-гоcolumn.

LEA с 3 "компонентами" для режима адресации имеет дополнительную задержку по сравнению с более простыми LEA, например, задержка 3 цикла в семействе Sandybridge по сравнению с 1 циклом.Но это все еще один моп, поэтому это отличный выбор для пропускной способности.

Если мы действительно хотим оптимизировать, и нам не нужно беспокоиться о переполнении кейса n=31 1072 *, мыd вручную написать цикл ASCII -> int, но начать с 1 вместо 0, чтобы сложить n+1 и найти n.Тогда bts даст нам 2^(n+1), и мы можем просто dec это.

Нет необходимости хранить exponent в памяти и перезагружать его снова;у вас уже есть это в реестре, где вы хотите.

Ваш комментарий в строке atod неправильный, и ваш код не будет иметь смысла, если он будет правильным.От ASCII до double (например, функция C strtod) вернется в x87 st0 или SSE2 xmm0, а не в EAX.atod фактически означает ASCII (десятичное число) в целое число.Возможно, d означает DWORD. 

    input   Prompt, string, 40      ; read ASCII characters (N)
    atod    string                 ; ascii (decimal) to integer in EAX

    xor    edx,edx                 ; edx = 0
    bts    edx, eax                ; edx |=  1<<eax
    lea    edx, [edx + edx - 1]    ; edx = (edx<<1) - 1

    dtoa    Solution, edx

Требуется 2 инструкции для реализации 1<<n, поэтому глупо использовать его в своей собственной функции.Простая передача аргументов + вызов функции потребует столько же усилий, сколько простое использование bts. 

0 -> 1 -> 1
1 -> 2 -> 3
2 -> 4 -> 7

Компиляторы обычно используют mov edx,1 + mov ecx, eax + shl edx, cl.Но это пропущенная оптимизация, особенно на процессорах Intel.

BMI2 shlx edx, edx, ecx поможет (избегая mov), но имеет меньший размер кода, чем xor -zero + bts.И BMI2 не всегда доступен.

Если вы не можете заставить свой компилятор использовать BTS (или у вас BMI2 для SHLX), другой хорошей реализацией является (2ULL << n) - 1, поэтому вы запекаете дополнительный сдвиг в числоты начинаешь сдвигатьсяТаким образом, счетчик 31 может сдвинуть бит и выдать 0.

...