алгоритм idiv

Тема в разделе "WASM.A&O", создана пользователем Mikl___, 23 ноя 2021.

  1. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
    Потребовалось в двоичной системе разделить +117/-13. Если бы делилось 117 на 13, то тут всё просто, использовались бы вычитания и сдвиги
    02.jpg
    а вот как разделить 01110101 на 11110011 чтобы в результате получилось 11110111 при этом используя элементарные операции (сдвиги, сложение. вычитание)?
     
  2. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.159
    Делить абсолютные значения и результату поменять знак соответственно (sign1 xor sign2).
     
    Mikl___ нравится это.
  3. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
    rmn,
    это первое, что приходит в голову, но как-то "некузяво". Я понимаю, что нужно искать литературу по intel8080 или микроконтроллерам и смотреть там, но пока ничего под руками нет
     
  4. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.787
    Mikl___,

    p.184

    Довольно тяжело воспринимается(два регистровых набора) впрочем это матан иначе не может быть. Мантиссы и тп твоя тема.
     

    Вложения:

    Последнее редактирование: 23 ноя 2021
    Artem_N и Mikl___ нравится это.
  5. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    251
    Никогда не видел чтобы деление обобщали на знаковые числа без анализа знаков делимого и делителей с переводом в беззнаковые и коррекцией результата. Собственно это то же самое, что мы делаем в столбик.

    Да это ж оверкилл с вещественными числами.
    Если уж нужен кусок кода на Z80 (с беззнаковыми!), то вот:
    Код (Text):
    1.  
    2. ; H_div_L - деление h / l
    3. ; in:   h - делимое
    4. ;       l - делитель
    5. ; out:  h <- h / l (результат)
    6. ;       a <- h % l (остаток)
    7. H_div_L         push bc
    8.                 ld b, 8
    9.                 xor a
    10. .loop           sla h
    11.                 rla
    12.                 cp l
    13.                 jr c, .skip
    14.                 inc h
    15.                 sub l
    16. .skip           djnz .loop
    17.                 pop bc
    18.                 ret
    19.  
    Это всё то же самое деление в столбик, но с небольшими оптимизациями - результат сразу же замещает делимое в регистре h по ходу процесса.
    Но при делении на константы возможны дополнительные трюки.
    На x86 стал излюбленным трюк когда переводят в вещественные, умножают на константу и одним сдвигом выбивают возможную ошибку из нижних разрядов.
     
    Artem_N и Mikl___ нравится это.
  6. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
  7. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    52
    Практического смысла гораздо больше в варианте rmn, но ради "кузявости":
    Ваше 117/13 = 117 - 13 * 8 - 13 * 1
    отнять положительное, это тоже самое, что прибавить отрицательное:
    117/(-13) = 117 + (-13 * 8) + (-13 * 1) = 117 + (11110011b * 8) + (11110011b * 1) = 01110101b + 10011ooob + 11110011b
    Чтоб совсем просто: деление столбиком - это один интеллектуальный шажочек от совсем тупого варианта: Отняли делитель,
    инкрементировали счётчик(он же, будущее частное) и так в цикле, пока >= 0.
    Просто отнимают не делитель * 1, А делитель * 2, или/и делитель * 4, или/и делитель * 8, и т. д. И соотв-но, +2 к результату, или +4 или +8 ....
     
    Mikl___ нравится это.
  8. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
    почему для правильного результата +117/-13=-9 мне нужно сдвинуть +117 влево на 9 разрядов и добавить +117? Магия?
    -13=243 -9=247 243*247=60021=117*513 ?
    02.jpg
    YGdIdQmqyK4.jpg
     
    Последнее редактирование: 5 дек 2021
  9. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    251
    Совпадение.
    Если взять за делимое 104 которое прекрасно на 13 делится, то этот же "трюк" не приводит ни к чему хорошему.
    104*512+104=53352/243=219,55555...

    Вообще даже само количество и качество доп-действий тут уже заметно сложнее классического анализа знаков.
     
  10. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
    +104/-13=-8
    (256-13)x(256-8)=2562+(-13-8)x256+(-13)x(-8)=(-21)x256+104=11101011|01101000
     
  11. f13nd

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.734
    Код (Text):
    1.  
    2. _117 3
    3.  09 39
    4.  _27
    5.   27
    6.    0
    7.  
    Деление столбиком это деление числа по частям, используя то свойство основания системы счисления, что позиция разряда есть его множитель: 117=1x102+1x101+7x100, 39=30x101+9x100.
    Таким образом из 117 отнимают 3*30=90, 27 в остатке дает 9. Операция negate и кодирование знака в MSB эксплуатирует свойство переноса разряда в плюс бесконечность (когда имеешь дело не с числом, а с полем фиксированной длины, на это плевать):
    Код (Text):
    1. 11110011
    2. +
    3. 00001101
    4. =0
    И ИМХО ни малейшего арифметического смысла у этой формы записи числа, продленного единицами в плюс бесконечность, нет. Даже школьники, деля числа в десятичной системе, знак отбрасывают.
     
  12. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    52
    Термин "отрицательное число", имхо неудачен. Лучше мыслить и оперировать понятием "дополнение до числа 2N", где N - число разрядов в выбранной разрядной сетке. Каждый множитель - "отрицательное число", приводить к "дополнению до числа 2N", и результат будет корректен только в битах, находящихся в пределах выбранной разрядной сетки. Если смотреть на вопрос под этим, правильным углом, то вся "магия" рассосётся.
     
  13. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    251
    Интересно, что механические калькуляторы разных типов лажают при попытке поделить на ноль зацикливаясь в процессе:

    Но если взять целочисленный алгоритм деления приведённый выше - "битовый столбик":
    Код (Text):
    1.  
    2. ; H_div_L - деление h / l
    3. ; in:   h - делимое
    4. ;       l - делитель
    5. ; out:  h <- h / l (результат)
    6. ;       a <- h % l (остаток)
    7. H_div_L         push bc
    8.                 ld b, 8
    9.                 xor a
    10. .loop           sla h
    11.                 rla
    12.                 cp l
    13.                 jr c, .skip
    14.                 inc h
    15.                 sub l
    16. .skip           djnz .loop
    17.                 pop bc
    18.                 ret
    19.  
    то нетрудно заметить (владея ассемблером Z80 конечно же), что количество циклов алгоритма лимитировано битностью результата и он точно выдаст некий результат.
    Какой же, если поделить некое X на 0?
    Ответ забавен: результат получится целиком забит единицами, т.е. максимальное целочисленное число влазящее в данную разрядную сетку, а в качестве остатка вернётся само число X.
    X/0=11111111 остаток X
    Это забавно потому что если мы теперь "проверим" результат деления обратным действитем, то получим 11111111*0+X=X... Оппа, единицы уничтожились при умножении на ноль и поэтому остаток равный делимому согласует равенство! :) Т.е. алгоритм с одной стороны "попытался" в результате получить максимально большое числое (максимально близкое к бесконечности), а с другой стороны манипулируя остатком "прикрыл" себе жопу для проверки результата. :) В чём то даже гениально.
     
    Mikl___ нравится это.
  14. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    52
    После того как впервые обратил внимание на этот прикол, ещё подумал: "Встретится ли мне когда-нибудь подобное???"
    Блин!!! Оно в функции memset!!!:lol:
    .....
    .....
    movzx edx, dl
    mov r9, 101010101010101h
    imul rdx, r9
    .....
    ....