32 бит деление

Если пошел уклон в сторону оптимизации по размеру, то можно немного сократить и ускорить

Код:

---

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

---

[свернуть]

Цитата:

---

Сообщение от ivagor

Надо определиться, все же оптимизация по размеру или по скорости.

---

Блин, при 27 байтах на процедуру, какой смысл в оптимизации по размеру, если не разворачивать цикл?

Цитата:

---

Сообщение от ivagor

И если по скорости, то можно ли разворачивать цикл

---

Мой вариант удобнее разворачивать :)

- - - Добавлено - - -

А если ограничить делитель и частное 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 байт

- - - Добавлено - - -

Цитата:

---

Сообщение от b2m

А если ограничить делитель и частное 15-ю битами, то ветку DIV322 можно выкинуть

---

Хотя, не очевидно это, хорошо бы доказать...

- - - Добавлено - - -

Ооо... как можно было забыть, что inc e на 2 такта быстрее inc de!!!

Цитата:

---

Сообщение от b2m

если ограничить делитель и частное 15-ю битами

---

такая процедура не нужна. делитель 16 бит нужен.

Цитата:

---

Сообщение от b2m

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 тактов.

Цитата:

---

Сообщение от Sayman

если процедура называется 32:16, то она во всём диапазоне должна работать

---

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

Цитата:

---

Сообщение от Sayman

Но, изначальная для z80 процедура от b2m, переписка с 8080, оказалась самой быстрой и при этом весьма короткой

---

Это я не понимаю, с тех пор здесь выложены и более короткие и более быстрые варианты.

хммм. был не прав. опечатался при расчётах чтоли?
эта процедура 2055 тактов.
эта процедура 1756 тактов.
эта процедура 1586 тактов.
эта процедура 1538 тактов.
эта процедура 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

---

[свернуть]