introspec, там 9битный синус
у него 9 бит это 8 бит L
так что все правильно
introspec, там 9битный синус
у него 9 бит это 8 бит L
так что все правильно
С уважением,
Jerri / Red Triangle.
Ага, и специальный код, который учитывает дополнение для отрицательных чисел?Сообщение от jerri
у него 9 бит это 8 бит L
так что все правильно
Предлагаю считать это решение жульническим!
---------- Post added at 22:58 ---------- Previous post was at 21:44 ----------
72 байта, "честный" 8-битный синус восстанавливается из таблицы дельт сжатых RLE:Код:SinTable: ld de, SinData ld hl, 49152 ld (hl), l QuarterGen: ld a, (de) and 7 ld c, a ld a, (de) sub c rrca rrca rrca ld b, a inc de RollOut: ld a, (hl) add c inc l ld (hl), a djnz RollOut bit 6, l jr z, QuarterGen ld e, l ld d, h Reflect: inc e dec l ld a, (hl) ld (de), a jr nz, Reflect Invert: xor a sub (hl) ld (de), a inc l inc e jr nz, Invert ret SinData: db 35,12,91,10,35,10,19,10,11,10,11,18,11 db 74,9,18,17,10,25,10,17,8,25,8,9,16,9,24
Последний раз редактировалось introspec; 06.10.2013 в 01:56. Причина: 73 байта -> 72 байта
"introspec" читается как "интроспек". некоторые читают как "интроспец", но я никакой не спец. я спек.
Есть интересный способ генерации синуса, основанный на рекуррентном соотношении. Если рассмотреть значения sin(x), sin(x-T), sin(x-2*T), где T - период дискретизации (константа) - то получится следующее:
sin(x-T) = sin(x)*cos(T) - cos(x)*sin(T)
sin(x-2*T) = sin(x)*cos(2*T) - cos(x)*sin(2*T)
Разрешим первое уравнение относительно cos(x):
cos(x) = sin(x)*cos(T)/sin(T) - sin(x-T)/sin(T)
Во втором уравнении применим формулы двойного угла:
sin(x-2*T) = sin(x)*(cos(T)^2 - sin(T)^2) - 2*cos(x)*sin(T)*cos(T)
Подставим cos(x), выраженное через первое уравнение, во второе:
sin(x-2*T) = sin(x)(cos(T)^2 - sin(T)^2) - 2*(sin(x)*cos(T)/sin(T) - sin(x-T)/sin(T))*sin(T)*cos(T)
Упростим выражение, раскрыв скобки. Многое сократится:
sin(x-2*T) = sin(x)*cos(T)^2 - sin(x)*sin(T)^2 - 2*sin(x)*cos(T)^2 + 2*sin(x-T)*cos(T)
Вынесем sin(x) за скобки. При этом cos(T)^2+sin(T)^2 = 1, и получим:
sin(x-2*T) = -sin(x) + 2*cos(T)*sin(x-T)
Разрешим это уравнение относительно sin(x) и получим:
sin(x) = 2*cos(T)*sin(x-T) - sin(x-2*T)
Это и есть рекуррентное соотношение, позволяющее вычислять значение синуса на регулярных интервалах (T). При известных значениях sin(x-T) и sin(x-2*T) можно вычислить sin(x), и на основе него вычислить следующее и т.д. до бесконечности. Окончательная формула для алгоритма (заменив sin(x) на y[i]):
y[i] = k*y[i-1] - y[i-2]
где k - константа, k=2*cos(T)
---
Данный алгоритм требует только одно умножение. Если подобрать такое k, которое является степенью двойки (в том числе отрицательной) - то умножение переходит в сложение + сдвиг. Разумеется, при этом можно получить далеко не произвольное значение T.
Если точность вычислений недостаточно высока, данный алгоритм может проявлять нестабильность. Так что надо проверять.
Жаль, поиск на форуме не работает. Ведь это все писалось один в один)
Ребята, а вы код такой писать пробовали? Формула для проца с умножением и плавающей точкой прекрасная, но для таблицы в 256 значений вы не сможете подобрать такое "к", как вам нравится. Вместо этого вам придётся иметь дело с к=(2-(2*пи/256)^2), причём округлять до 2 - нельзя.
"introspec" читается как "интроспек". некоторые читают как "интроспец", но я никакой не спец. я спек.
Прошу прощения, что боян.
Ну ладно. Есть еще одна идея. Детально не копал, но может быть, есть смысл зайти с этой стороны. Длина таблицы в 256 - это отличная длина для БПФ. Создаем массив длиной 256 чисел, заполняем его нулями, устанавливаем второе и последнее числа в 1. Делаем обратное БПФ - получаем косинус. На данном этапе пока что экономии в вычислениях никакой. Однако можно попытаться заглянуть в формулы для БПФ и заметить, где у нас при известных входных данных происходит умножение на нуль или сложение с нулем при заведомо известных входных данных. Умножение на 1 также тривиальная операция. В конечном счете должен получиться какой-то упрощенный алгоритм БПФ, результатом которого будет таблица значений косинуса. Если окажется, что такой алгоритм экономный с вычислительной точки зрения - то можно попытаться применить его.
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Мне подсказали, что самые компактные реализации обычно используют не дельты, а дельты дельт. Я попробую написать ещё и такую версию и отчитаюсь, что у меня из этого выйдет.
БПФ - прикольная математика, но вот так "в лоб" я не очень верю, что может выйти компактнее. Хотя, буду рад оказаться неправ!
---------- Post added at 20:25 ---------- Previous post was at 19:14 ----------
Генератор таблицы 8-битных синусов (256 байт на один период, значения от -127 до 127). 63 байта, работа с несжатыми дельтами дельт. Таблицу можно положить куда угодно (49152 не принципиально), но она должна быть выровнена на 256 байт.Дополнение: g0blinish разбирал Mathricks в 7-ом номере Acid Paper; в ней реализован алгоритм с простыми дельтами, которые удалось упаковать в 16 байт ограничив вариацию синуса 7-ю битами. Длина кода Mathricks - 65 байт (g0blinish насчитал 66 байт, но он забыл выкинуть два байта для покраски бордера в чёрный цвет; кроме того, у процедуры в Mathricks нет в конце команды ret). Похоже тут у нас родился новый рекордКод:SinTable: ld de, SinData-1 ld hl, 49152 ld (hl), l ld c, 3 QuarterGen: ld b, 4 inc de SkipReload: ld a, (de) rlca rlca ld (de), a and 3 dec a add c add c sub (hl) inc l ld (hl), c ld c, a djnz SkipReload bit 6, l jr z, QuarterGen ld e, l ld d, h Reflect: inc e dec l ld a, (hl) ld (de), a jr nz, Reflect Invert: xor a sub (hl) ld (de), a inc l inc e jr nz, Invert ret SinData: db 86,21,85,84,149,36,136,97,85,84,145,133,132,148,134,21
Последний раз редактировалось introspec; 06.10.2013 в 01:37. Причина: 70 байт -> 63 байта
"introspec" читается как "интроспек". некоторые читают как "интроспец", но я никакой не спец. я спек.
Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт. На кодах калькулятора может получиться ещё меньше.
Это фактически тот же подход, что предложили Barmaley_m и Titus.
Только приложенный код выдаёт не синус, а косинус!
---------- Post added at 18:57 ---------- Previous post was at 18:49 ----------
Я правильно понимаю, что EXD = EX DE, HL? А то у меня что-то длина кода не сходится...
"introspec" читается как "интроспек". некоторые читают как "интроспец", но я никакой не спец. я спек.
Ну, зависит от начального значения hl и de... влом было подгонять. С косинусом тожно можно жить )
А, там 47 байт )
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)
Ваши права
Ответить с цитированием
