Просмотр полной версии : 32 бит деление
Приветствую. Может кто-нибудь поделиться процедурой 32х битного деления? 32 бита делить на 16 бит, результат 16 бит и плюс остаток. чем быстрее процедура, тем лучше. пока нашёл 3 процедуры где то в старых загашниках, ни одна не работает. Точнее работают, но на каких то либо ровных значениях либо на малых. Когда на вход подаю делимое больше 16 бит, начинаются проблемы.
Спасибо!
Этот вариант (https://zx-pk.ru/threads/25783-vychislenie-chisla-pi-na-assemblere.html?p=840386&viewfull=1#post840386) подойдёт? (прошу прощения за мой i8080)
b2m, было бы хорошо под z80.
тут (https://zx-pk.ru/threads/1061-fast-48x48-mul-div.html?p=18445&viewfull=1#post18445) выкладывали, может подойдёт
Ну блин.
DIV32: ld a,b ; DE = HLDE/BC, HL = HLDE%BC
cpl
ld b,a
ld a,c
cpl
ld c,a
inc bc
xor a
DIV321: add hl,hl
rra
ex de,hl
add hl,hl
ex de,hl
jr nc, DIV320
inc hl
DIV320: push hl
add hl,bc
jr nc, DIV322
rla
DIV323: inc de
inc sp
inc sp
add a, 10h
jr nc, DIV321
ret
DIV322: rla
jr c, DIV323
pop hl
add a, 10h
jr nc, DIV321
ret
Ну блин.
DIV32: ld a,b ; DE = HLDE/BC, HL = HLDE%BC
cpl
ld b,a
ld a,c
cpl
ld c,a
inc bc
xor a
DIV321: add hl,hl
rra
ex de,hl
add hl,hl
ex de,hl
jr nc, DIV320
inc hl
DIV320: push hl
add hl,bc
jr nc, DIV322
rla
DIV323: inc de
inc sp
inc sp
add a, 10h
jr nc, DIV321
ret
DIV322: rla
jr c, DIV323
pop hl
add a, 10h
jr nc, DIV321
ret
О! Крутяк! Спасибо! Чьё авторство?
Вообще-то можно с использованием Z80 инструкций подсократить, например при 32-битном сдвиге использовать adc hl,hl, а вместо инверсии делителя использовать sbc hl,bc
- - - Добавлено - - -
Чьё авторство?
Из книги Гуртовцева,Гудыменко
Зачётная книжка. "Как выполнить умножение 2*2 разными 33-я способами"
Зачётная книжка. "Как выполнить умножение 2*2 разными 33-я способами"
Чёта не гуглится...
Чёта не гуглится...
Гуртовцев А. Л., Гудыменко С. В.. Программы для микропроцессоров: Справ, пособие. (https://scicenter.online/kniga-mikroelektronika-scicenter/programmyi-dlya-mikroprotsessorov-sprav.html) стр.90-91 (лучше скачать djvu, на сайте картинки со смещением в тексте)
- - - Добавлено - - -
О! Крутяк! Спасибо! Чьё авторство?
Я доработал процедуру, теперь точно "крутяк". И авторство моё :)
DIV32: ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321: ex de,hl
add hl,hl
ex de,hl
adс hl,hl
jr c DIV322
push hl
sbс hl,bc
jr nc, DIV323
pop hl
jr DIV325
DIV322: ccf
sbс hl,bc
jr DIV324
DIV323: inc sp
inc sp
DIV324: inc de
DIV325: dec a
jr nz, DIV321
ret
Если пошел уклон в сторону оптимизации по размеру, то можно немного сократить и ускорить
DIV32:
ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:
ex de,hl
add hl,hl
ex de,hl
adc hl,hl
jr c, DIV322
sbc hl,bc
jr nc, DIV323
add hl,bc
jr DIV324
DIV322:
ccf
sbc hl,bc
DIV323:
inc de
DIV324:
dec a
jr nz, DIV321
ret
Ну, ivagor как обычно в своём репертуаре... :)
- - - Добавлено - - -
Если пошел уклон в сторону оптимизации по скорости, то можно выиграть ещё 48 тактов
DIV32:
ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:
sla e
rl d
adc hl,hl
jr c, DIV322
sbc hl,bc
jr nc, DIV323
add hl,bc
jr DIV324
DIV322:
ccf
sbc hl,bc
DIV323:
inc de
DIV324:
dec a
jr nz, DIV321
ret
Раз пошло увеличение размера, то за +2 байта можно еще ускорить. Надо определиться, все же оптимизация по размеру или по скорости. И если по скорости, то можно ли разворачивать цикл (и если да, то явно можно нагуглить быстрые процедуры).
DIV32:
ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:
sla e
rl d
adc hl,hl
jr c, DIV322
sbc hl,bc
jr nc, DIV323
add hl,bc
dec a
jr nz, DIV321
ret
DIV322:
ccf
sbc hl,bc
DIV323:
inc de
dec a
jr nz, DIV321
ret
Надо определиться, все же оптимизация по размеру или по скорости.
Блин, при 27 байтах на процедуру, какой смысл в оптимизации по размеру, если не разворачивать цикл?
И если по скорости, то можно ли разворачивать цикл
Мой вариант удобнее разворачивать :)
- - - Добавлено - - -
А если ограничить делитель и частное 15-ю битами, то ветку DIV322 можно выкинуть, и тогда уже развернуть. Вряд-ли найдутся более быстрые процедуры.
- - - Добавлено - - -
А потом ещё сэкономить заменив jr DIV324 на dec de
- - - Добавлено - - -
DIV32: ; DE = HLDE/BC, HL = HLDE%BC, HLDE<2^31, BC<2^15
rept 16
sla e
rl d
adc hl,hl
sbc hl,bc
jr nc, $+4
add hl,bc
dec e
inc e
endm
ret
- - - Добавлено - - -
1162 тактов максимум
- - - Добавлено - - -
209 байт
- - - Добавлено - - -
А если ограничить делитель и частное 15-ю битами, то ветку DIV322 можно выкинуть
Хотя, не очевидно это, хорошо бы доказать...
- - - Добавлено - - -
Ооо... как можно было забыть, что inc e на 2 такта быстрее inc de!!!
если ограничить делитель и частное 15-ю битами
такая процедура не нужна. делитель 16 бит нужен.
1162 тактов максимум
оригинальная процедура (на z80, до ваших оптимизаций), на моих тестах/примерах отжрала 1055 тактов. так что у вас уже не оптимизация, а что-то обратное.
математические процедуры для z80, особенно 32х битные, это бич Спектрума и не только. чем быстрее, тем лучше, но самое оптимальное - это некая середина, при которой и размер процедуры и скорость в балансе. а если процедура будет занимать, образно говоря, пол килобайта. то т акая процедура тоже мало кому пригодится.
Без четких критериев оптимальности и ограничений не получится сделать оптимальную процедуру. Если говорить о развернутых вариантах, то для 8080 быстрейшим является реализация алгоритма blackmirrora, которую можно найти в ветке про пи. Насчет ее оптимальности по скорости для z80 (с соответствующей оптимизацией) я уверен не на 100%, но по крайней мере она где-то среди быстрейших.
Если вернуться к сравнительно компактным процедурам, то изменив распределение регистров, можно еще оптимизировать
DIV32:
ld a,b
ld b,16 ; BC = HLBC/DE, HL = HLBC%DE
DIV321:
sla c
rla
adc hl,hl
jr c, DIV322
sbc hl,de
jr nc, DIV323
add hl,de
djnz DIV321
ld b,a
ret
DIV322:
ccf
sbc hl,de
DIV323:
inc c
djnz DIV321
ld b,a
ret
И важно знать предполагаемые диапазоны наиболее вероятных значений делимого и делителя. Самую короткую процедуру можно оптимизировать без увеличения размера для (как мне представляется) наиболее востребованных соотношений делимого и делителя, для четкой проверки нужен конкретный test bench.
ivagor, в моём представлении математическая процедура должна выполнять математику, не взирая на 15 бит или ещё там что то. если процедура называется 32:16, то она во всём диапазоне должна работать. Если же процедура работает только в каких-то конкретных диапазонах, то увы, 32:16 её уже называть нельзя. и хорошо бы в комментариях к процедуре такое указывать. я топик то создал - работая с утилитой, которая должна работать с данными на винте, математика предполагает наличие всего диапазона (во всяком случае до 28 бит для ЛБА). столкнулся как раз с тем, что именованные процедуры, вроде div32_16 и тому подобные на проверку не могут даже 18 бит разделить на 16, выдавая вместо результата мусор. Увы, но в написании таких процедур я не силён. Но, изначальная для z80 процедура от b2m, переписка с 8080, оказалась самой быстрой и при этом весьма короткой (находил в разы больше и при этом медленнее).
сами понимаете, z80 математически обделённый, а потому нужна какая то быстрая процедура, но не превращённая в 16килобайтного монстра ради экономии 50 тактов.
если процедура называется 32:16, то она во всём диапазоне должна работать
Это не подвергается сомнению. Просто надо учитывать, что от соотношений делимого и делителя зависят вероятности прохождения тех или иных веток процедуры, и это можно учесть.
Но, изначальная для z80 процедура от b2m, переписка с 8080, оказалась самой быстрой и при этом весьма короткой
Это я не понимаю, с тех пор здесь выложены и более короткие и более быстрые варианты.
хммм. был не прав. опечатался при расчётах чтоли?
эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1104929&viewfull=1#post1104929) процедура 2055 тактов.
эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1104986&viewfull=1#post1104986) процедура 1756 тактов.
эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1104995&viewfull=1#post1104995) процедура 1586 тактов.
эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1104997&viewfull=1#post1104997) процедура 1538 тактов.
эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1105007&viewfull=1#post1105007) процедура 1406 тактов.
считал полуавтоматом через эмулятор ZxMak2, у него есть счётчик тактов, им и пользовался. но при изначальном подсчёте где то ошибся (опечатался) и на 1000 тактов пролетел по изначальной процедуре. пересчитал сейчас и заодно остальные процедуры тоже пересчитал. последнюю. где про 15бит, считать не стал, зачем мне 15бит?!
как считал:
ld hl,0x001f ;реальное значение
ld de,0xf7df ;размера диска в секторах
ld bc,0xffef ;максимум кластеров FAT16
push hl
push de
push bc
call DIV32
pop bc
pop de
pop hl
push hl
push de
push bc
call DIV32_2
pop bc
pop de
pop hl
push hl
push de
push bc
call DIV32_3
pop bc
pop de
pop hl
push hl
push de
push bc
call DIV32_4
pop bc
pop de
pop hl
push hl
push de
push bc
call DIV32_5
на каждом call остановка, замер тактов в счётчике, выполнение call, снова подсчёт и вычитание первого значения. в расчёте сама call тоже участвует (входит в потраченные такты).
от куда брал для замера значения (делимое, делитель): на этих значениях споткнулась процедура деления, которую я втыкал в утилиту изначально. потом начал пихать другие, они тоже ошибались. Потом нашёл рабочий вариант, но на 4000 тактов. печально. Потом уже вот тут b2m подкинул первую процедуру. значения реальные, взятые с моего винта. поскольку на них произошёл спотык (а я знаю верное значение на выходе, т.к. параллельно на калькуляторе считал для контроля), то их и использовал далее для тестов. может не совсем верное решение, но "я так вижу")))
Вариант с восстановлением остатка довели до кондиции, теперь вариант без восстановления остатка (не надо верить всему, что писали Гуртовцев и Гудыменко). Раскладка регистров измененная, как в последнем restoring варианте.
; BC = HLBC/DE, HL = HLBC%DE
; Non-restoring division
DIVNR32:
ld a,b
ld b,16
DIVNR321:
db 0CBh
db 031h ;sll c
rla
adc hl,hl
jr c,DIVNR323
sbc hl,de
jr c,DIVNR322_
DIVNR321_:
djnz DIVNR321
DIVNR325:
db 0CBh
db 031h ;sll c
rla
ld b,a
ret
DIVNR323:
ccf
sbc hl,de
jr nc,DIVNR322_
djnz DIVNR321
jr DIVNR325
DIVNR322:
sla c
rla
adc hl,hl
jr nc,DIVNR324
add hl,de
jr c,DIVNR321_
DIVNR322_:
djnz DIVNR322
DIVNR326:
sla c
rla
ld b,a
add hl,de
ret
DIVNR324:
add hl,de
jr nc,DIVNR321_
djnz DIVNR322
jr DIVNR326
- - - Добавлено - - -
Вероятно финальный вариант без восстановления остатка, по крайней мере у меня идеи вроде иссякли. +5 байт, зато:
1. В большинстве случаев немного быстрее
2. Без недокументированных команд
3. Узкоспециальное достоинство - от этого варианта ближе до версии для 8080
; BC = HLBC/DE, HL = HLBC%DE
; Non-restoring division
DIVNR32:
ld a,b
call DIVNR32_8
ex af,af'
ld a,c
call DIVNR32_8
ld c,a
ex af,af'
ld b,a
ret
DIVNR32_8:
ld b,8
DIVNR321:
scf
rla
adc hl,hl
jr c,DIVNR323
sbc hl,de
jr c,DIVNR322_
DIVNR321_:
djnz DIVNR321
scf
rla
ret
DIVNR323:
ccf
sbc hl,de
jr nc,DIVNR322_
DIVNR321_2:
djnz DIVNR321+1
rla
ret
DIVNR322:
add a,a
adc hl,hl
jr nc,DIVNR324
add hl,de
jr c,DIVNR321_2
DIVNR322_:
djnz DIVNR322
add a,a
add hl,de
ret
DIVNR324:
add hl,de
jr nc,DIVNR321_
djnz DIVNR322
add a,a
add hl,de
ret
По аналогии со второй версией без восстановления остатка, сделал подобную версию и с восстановлением
; BC = HLBC/DE, HL = HLBC%DE
; Restoring division
DIV32:
ld a,b
call DIV32_8
push af
ld a,c
call DIV32_8
pop bc
ld c,a
ret
; A = HLA/DE, HL = HLA%DE
DIV32_8:
ld b,8
DIV321:
add a,a
adc hl,hl
jr c, DIV322
sbc hl,de
jr nc, DIV323
add hl,de
djnz DIV321
ret
DIV322:
ccf
sbc hl,de
DIV323:
inc a
djnz DIV321
ret
+7 байт, но она быстрее и 2в1 - тут не только 32/16=16, но и 24/8=8 (кстати без восстановления остатка тоже во второй версии эта фишка есть, забыл там написать).
В итоге у каждого метода (restoring и non-restoring) по два варианта: компактный и побыстрее. Если сравнивать методы, то очевидно restoring компактнее, non-restoring быстрее. Можно еще немного ускорить за счет некоторого увеличения размера, но не сильно, тут уже каждый сам может при желании доработать.
снова возник вопрос:
вот эти процедуры деления, там написано в комментариях: DE = HLDE/BC, HL = HLDE%BC
я не сильно спец в таких вещах, но модуль числа то там зачем? или это остаток? или как?
А разве остаток от деления и "модуль числа" не одно и то-же?
(на самом деле, модуль числа это совсем другое, но я понял, что ты имел ввиду деление по модулю)
Избавиться в приведенных процедурах деления от вычисления остатка и сохранить вычисление правильного частного не получится. Хотя если быть очень занудным, то можно так: полностью развернуть и тогда можно будет убрать одну операцию ближе к завершению деления. Экономия мизерная, но если остаток совсем не нужен, размер не важен, зато важен каждый такт, то почему бы и нет (сам так делал). Можно наоборот - вычислять только остаток без частного, вот тут процедуру можно упростить, ускорить и сократить.
хотелось бы вернуться к банным борашкам. Возникла потребность в делении 32:32, наверное даже с остатком. Можете помочь, товарищи знатоки?!
Возникла потребность в делении 32:32, наверное даже с остатком
С уклоном в скорость или компактность?
С уклоном в скорость или компактность?
ну скорость бы хотелось.... наверное.
;BCBC'=BCBC'/DEDE'
;HLHL'=BCBC'%DEDE'
DIV323232:
ld hl,0
exx
ld hl,0
ld a,b
exx
push bc
call DIV328
exx
ld b,a
ld a,c
exx
call DIV328
exx
ld c,a
exx
pop bc
ld a,b
call DIV328
push af
ld a,c
call DIV328
pop bc
ld c,a
ret
DIV328:
ld b,8
DIV328loop:
add a,a
adc hl,hl
exx
adc hl,hl
exx
sbc hl,de
exx
sbc hl,de
exx
jr nc,DIV328_
add hl,de
exx
adc hl,de
exx
djnz DIV328loop
ret
DIV328_:
inc a
djnz DIV328loop
ret
спустя вот это всё время выясняется, что вот эта (https://zx-pk.ru/threads/32913-32-bit-delenie.html?p=1105007&viewfull=1#post1105007)процедура работает не корректно.
если заставлять её делить 32бита просто на 2 (или подобные значения), то выдаёт мусор.
если заставлять её делить 32бита просто на 2 (или подобные значения), то выдаёт мусор.
Если заставлять делить 32 бита на 2 или 3 или на много что еще с получением результата не помещающегося в 16 бит, то нужно использовать другую процедуру. А в той процедуре написано: BC = HLBC/DE, HL = HLBC%DE и она работоспособна в данных пределах.
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot