Просмотр полной версии : Генерация синуса
Hacker VBI
14.05.2013, 15:40
Нашёл интересную реализацию генератора синуса (http://www.coranac.com/2009/07/sines/) для арм/С.
пытаюсь разобраться, но интересно АРМ устроен, некоторые вещи не ясны.
Вопроса два:
1. есть ли смысл в таком подходе?
2. возможна ли достойная реализация под z80?
вот сам код:
С:
s32 isin_S3(s32 x)
{
// S(x) = x * ( (3<<p) - (x*x>>r) ) >> s
// n : Q-pos for quarter circle 13
// A : Q-pos for output 12
// p : Q-pos for parentheses intermediate 15
// r = 2n-p 11
// s = A-1-p-n 17
static const int qN = 13, qA= 12, qP= 15, qR= 2*qN-qP, qS= qN+qP+1-qA;
x= x<<(30-qN); // shift to full s32 range (Q13->Q30)
if( (x^(x<<1)) < 0) // test for quadrant 1 or 2
x= (1<<31) - x;
x= x>>(30-qN);
return x * ( (3<<qP) - (x*x>>qR) ) >> qS;
}
And, of course, there's an assembly version as well. It's only ten instructions, which I think is actually shorter than a LUT+lerp implementation.
@ ARM assembly version, using n=13, p=15, A=12
@ Input: gamma in Q13
.arm
.align
.global isin_S3a
isin_S3a:
mov r0, r0, lsl #(30-13)
teq r0, r0, lsl #1
rsbmi r0, r0, #1<<31
mov r0, r0, asr #(30-13)
mul r1, r0, r0
mov r1, r1, asr #11
rsb r1, r1, #3<<15
mul r0, r1, r0
mov r0, r0, asr #17
bx lr
дома есть немного раскоментированный код арм-а , могу вечером выложить что обнаружил.
Давай сразу на Z80 пример.
Hacker VBI
14.05.2013, 16:54
drbars, легко сказать.
пока разбираю асм арма
introspec
14.05.2013, 17:43
Смотря для чего использовать. Умножение - дорогая операция, а тут - два умножения (хотя два умножения можно заменить одним кубом). Относительная погрешность в худшем случае - 4% (посчитал на ходу, мог ошибиться, конечно). Для генерации таблицы могло бы быть и поточнее, для работы на лету - слишком медленно для процессора без "дешёвого" умножения.
Цель какая?
---------- Post added at 14:43 ---------- Previous post was at 14:32 ----------
Тут мысль такая: они минимизировали абсолютные погрешности там, где синус большой, а то, что итоговые относительные значения аргумента врут там где синус маленьких их, типа, не волнует.
В любом случае, в 3D движок я бы это не поставил, а в эффект где достаточно знать абсолютную величину синуса - можно.
Hacker VBI
14.05.2013, 18:13
introspec, спасибо. да, думаю что именно для демосцены применимо.
даже не обязательно риалтайм, хотя посмотрим.
тут сдвигов куча, да плюс два умножения...
introspec
14.05.2013, 18:22
Только не вздумай делать "в лоб" - тут всё подогнано для 32-битного процессора. Нет смысла делать так на 8-битном процессоре. Нужно делать 16-ти или даже 8-битную версию. Я прикину множители и напишу.
А для чего такой изврат-то?
Вот пример генератора синуса в 75 байт http://zxpress.ru/article.php?id=1289
Вышеприведенный пример врядли будет короче, даже без учета процедуры умножения.
Vitamin, там ошибка в табличке
Hacker VBI
15.05.2013, 10:41
После консультации с introspec и рекомендации Vitamin освоение арм-а и римейк данного генератора прекращён
introspec
05.10.2013, 00:28
Vitamin, там ошибка в табличке
jerri, там по-моему не в табличке ошибка, а во втором полупериоде - они его сделали ldir, а что знак менять нужно, очевидно, забыли.
introspec, там 9битный синус
у него 9 бит это 8 бит L
так что все правильно :)
introspec
05.10.2013, 01:58
у него 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
Barmaley_m
05.10.2013, 14:26
Есть интересный способ генерации синуса, основанный на рекуррентном соотношении. Если рассмотреть значения 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.
Если точность вычислений недостаточно высока, данный алгоритм может проявлять нестабильность. Так что надо проверять.
y[i] = k*y[i-1] - y[i-2]
где k - константа, k=2*cos(T)
---
Данный алгоритм требует только одно умножение. Если подобрать такое k, которое является степенью двойки (в том числе отрицательной) - то умножение переходит в сложение + сдвиг. Разумеется, при этом можно получить далеко не произвольное значение T.
Если точность вычислений недостаточно высока, данный алгоритм может проявлять нестабильность. Так что надо проверять.
Жаль, поиск на форуме не работает. Ведь это все писалось один в один)
introspec
05.10.2013, 14:50
Ребята, а вы код такой писать пробовали? Формула для проца с умножением и плавающей точкой прекрасная, но для таблицы в 256 значений вы не сможете подобрать такое "к", как вам нравится. Вместо этого вам придётся иметь дело с к=(2-(2*пи/256)^2), причём округлять до 2 - нельзя.
Barmaley_m
05.10.2013, 22:01
Прошу прощения, что боян.
Ну ладно. Есть еще одна идея. Детально не копал, но может быть, есть смысл зайти с этой стороны. Длина таблицы в 256 - это отличная длина для БПФ. Создаем массив длиной 256 чисел, заполняем его нулями, устанавливаем второе и последнее числа в 1. Делаем обратное БПФ - получаем косинус. На данном этапе пока что экономии в вычислениях никакой. Однако можно попытаться заглянуть в формулы для БПФ и заметить, где у нас при известных входных данных происходит умножение на нуль или сложение с нулем при заведомо известных входных данных. Умножение на 1 также тривиальная операция. В конечном счете должен получиться какой-то упрощенный алгоритм БПФ, результатом которого будет таблица значений косинуса. Если окажется, что такой алгоритм экономный с вычислительной точки зрения - то можно попытаться применить его.
introspec
05.10.2013, 23:25
Мне подсказали, что самые компактные реализации обычно используют не дельты, а дельты дельт. Я попробую написать ещё и такую версию и отчитаюсь, что у меня из этого выйдет.
БПФ - прикольная математика, но вот так "в лоб" я не очень верю, что может выйти компактнее. Хотя, буду рад оказаться неправ! :)
---------- Post added at 20:25 ---------- Previous post was at 19:14 ----------
Генератор таблицы 8-битных синусов (256 байт на один период, значения от -127 до 127). 63 байта, работа с несжатыми дельтами дельт. Таблицу можно положить куда угодно (49152 не принципиально), но она должна быть выровнена на 256 байт.
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,13 4,21
Дополнение: g0blinish разбирал Mathricks в 7-ом номере Acid Paper; в ней реализован алгоритм с простыми дельтами, которые удалось упаковать в 16 байт ограничив вариацию синуса 7-ю битами. Длина кода Mathricks - 65 байт (g0blinish насчитал 66 байт, но он забыл выкинуть два байта для покраски бордера в чёрный цвет; кроме того, у процедуры в Mathricks нет в конце команды ret). Похоже тут у нас родился новый рекорд :)
Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт. На кодах калькулятора может получиться ещё меньше.
introspec
06.10.2013, 21:57
Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт. На кодах калькулятора может получиться ещё меньше.
Это фактически тот же подход, что предложили Barmaley_m и Titus.
Только приложенный код выдаёт не синус, а косинус! :)))))))))
---------- Post added at 18:57 ---------- Previous post was at 18:49 ----------
Я правильно понимаю, что EXD = EX DE, HL? А то у меня что-то длина кода не сходится...
Только приложенный код выдаёт не синус, а косинус!
Ну, зависит от начального значения hl и de... влом было подгонять. С косинусом тожно можно жить )
Я правильно понимаю, что EXD = EX DE, HL? А то у меня что-то длина кода не сходится...
А, там 47 байт )
Barmaley_m
07.10.2013, 01:21
Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт.
(зануда моде он) Я бы не называл это отрицательной обратной связью. Тут скорее можно говорить о рекурсивном фильтре второго порядка. В общем виде такой фильтр описывается формулой:
a0*y[i] = b0*x[i] + b1*x[i-1] + b2*x[i-2] - a1*y[i-1] - a2*y[i-2]
При отсутствии входного сигнала (все x[i]=0) выходной сигнал такого фильтра может быть одним из следующих:
1) Постоянный уровень (напр. при a0=1, a1=-1, a2=0)
2) Затухающая экспонента (напр. при a0=1, a1=-0.9, a2=0)
3) Нарастающая экспонента (напр. при a0=1, a1=-1.1, a2=0)
4) Постоянная по уровню синусоида (напр. при a0=1, a1=-2..2, a2=1]
5) Затухающая по экспоненте синусоида
6) Нарастающая по экспоненте синусоида
Фильтр называют стабильным, если его выходной сигнал затухает при отсутствии входного сигнала. Если выходной сигнал нарастает при отсутствии входного - фильтр нестабилен. Наконец, при сохранении уровня выходного сигнала при отсутствии входного фильтр называется условно-стабильным.
Для целей фильтрации сигналов обычно применяются только стабильные фильтры (т.е. затухающие). Для генерации синусоид - условно-стабильные. Определить, к какому классу принадлежит фильтр, можно, вычислив корни квадратного трехчлена:
a0*z^2 + a1*z + a2 = 0
Если оба корня (z1, z2) действительные - выходной сигнал будет постоянным либо экспонентой. Если корни комплексные - то будет синусоида (затухающая, нарастающая или постоянная). При этом, если корни находятся внутри круга abs(z)<1 - то фильтр является стабильным. Если лежат на круге abs(z)=1 - то условно-стабильным. Если за пределами круга - то нестабильным.
В предложенной выше формуле для генерации синуса:
y[i] = k*y[i-1] - y[i-2]
у нас коэффициенты равны соответственно a0=1, a1=k, a2=1. Если k лежит в пределах -2..2 - то получается два комплексных корня на единичной окружности, т.е. как раз то, что и требуется.
(зануда моде офф)
На кодах калькулятора может получиться ещё меньше.
На кодах калькулятора можно сразу вызвать процедуру sin из ПЗУ, кстати!
(зануда моде он) Я бы не называл это отрицательной обратной связью. Тут скорее можно говорить о рекурсивном фильтре второго порядка. В общем виде такой фильтр описывается формулой:
a0*y[i] = b0*x[i] + b1*x[i-1] + b2*x[i-2] - a1*y[i-1] - a2*y[i-2]
Надо заметить, что по этому принципу построен фильтр Герцеля, который считается самой быстрой реализацией ДПФ для небольшого числа полос.
Barmaley_m
07.10.2013, 01:35
Да, Герцель - это хорошая вещь. Я с помощью этого метода делал на микроконтроллере детектор сигналов ДТМФ.
Да, Герцель - это хорошая вещь. Я с помощью этого метода делал на микроконтроллере детектор сигналов ДТМФ.
Какое совпадение) Я делал тоже самое)
Что самое интересное, реально самый быстрый ДПФ. Где-то 5-6 тактов на итерацию, на сколько я помню на Cortex-M0.
introspec
09.10.2013, 00:23
Достаточно сделать отрицательную обратную связь, и возникают гармонические колебания. 49 байт. На кодах калькулятора может получиться ещё меньше.
Я потестировал код немного и у меня что-то выходит, что косинус вычислен не вполне точно. Для эффектов сойдёт, наверное, но в 3д это вставлять нельзя. Из-за того, что нужная константа довольно близка к 2, я что-то засомневался, а можно ли вообще получить целиком период правильно округлённых значений косинса с таким подходом? При случае попробую переписать код по-своему чтобы лучше понять границы применимости метода.
---------- Post added at 21:23 ---------- Previous post was at 21:19 ----------
Кстати, вот ещё для коллекции ссылка от Serzhsoft:
http://cpu.untergrund.net/adv/tutor/sin_9.html
Он описывает уже немного устарелый морально генератор на дельтах (119 байт), а так же генератор на основе калькулятора (39 байт, 15 секунд работы).
Barmaley_m
09.10.2013, 00:49
Генератор синуса на рекуррентной формуле имеет 2 источника погрешности:
1) погрешность в коэффициенте k. Получив округленное значение k, следует вычислить реальный период синуса и прикинуть, достаточна ли точность
2) погрешность при округлении во время текущих вычислений. При определенных условиях она может привести к затуханию сигнала или же наоборот, нестабильности (процесс пойдет вразнос). Нужно испытывать. Чем больше разрядов используется для представления y[i] - тем лучше.
При использовании кодов калькулятора не для вычисления синусов, а для реализации рекуррентной формулы есть шанс повысить ее точность за счет обоих приведенных выше факторов. Может оказаться быстрее, чем вызывать sin.
introspec
09.10.2013, 00:51
Да, я хорошо понимаю, как это работает. Про реализацию рекуррентной формулы на калькуляторе я уже тоже думал, но пока хотел бы всё же избежать. Хочеться "чистое" решение всё же :)
Barmaley_m
09.10.2013, 01:05
Только что поигрался с Матлабом. Без округления рекуррентная формула работает безупречно. С округлением искажается амплитуда сигнала и его период (даже несмотря на точное значение k). И это при 16 битах разрешения!
Кстати, идея. Хоть нам нужно вычислить один период синуса, это ставит генератор в не очень хорошее положение. Если настроить генератор так, чтобы за проход таблицы он сгенерировал не один, а несколько периодов синуса - то с точки зрения ошибок округления ситуация, по-моему, должна улучшиться. После этого останется только перетасовать значения в таблице, чтобы из нескольких периодов сделать один.
introspec
09.10.2013, 01:09
Без округления рекуррентная формула не может не работать! :)
Всё же, раз это 8-и битный синус, довольно важно с моей точки зрения сохранить как можно больше точности (поэтому я и шёл всё же от табличных данных).
В вариант с генерацией нескольких периодов я пока не очень верю, скорее всего по этим данным придётся интерполировать, что означает сравнительно сложный код и дополнительный источник ошибок.
Barmaley_m
09.10.2013, 01:12
Да, это помогает!
Только количество периодов не должно делиться на 2. Иначе будут генерироваться повторения. Точность возросла значительно! Я сгенерировал только что 13 периодов косинуса при разрешении данных 8 бит. Вышло очень даже неплохо.
introspec
09.10.2013, 01:14
У меня сейчас идея поэкстравагантнее крутится. Я пишу генерацию синуса алгоритмом Брезенхэма :)
Barmaley_m
09.10.2013, 01:14
Не надо ничего интерполировать. Если количество периодов и длина массива данных не имеют общих делителей - то данные периодов будут дополнять друг друга. Они не будут повторяться от периода к периоду в пределах длины массива. Для окончательной обработки их придется всего лишь перетасовать.
introspec
09.10.2013, 01:16
всего лишь перетасовать
Я реально не назло, но неужели можно всерьёз рассчитывать впихнуть всё это в 50-60 байт? :) т.е. я понимаю академический интерес, но хочется всё же что-то реальное получить в конце, не?
У меня сейчас идея поэкстравагантнее крутится. Я пишу генерацию синуса алгоритмом Брезенхэма :)
Типа как рисование окружностей?)
introspec
09.10.2013, 01:19
Типа как рисование окружностей?)
Точно так же! :)
Точно так же! :)
Вроде бы по такому же принципу генерится синус в игре Rick Dangerous 2.
Когда в меню человечек туда-сюда шатается.
Barmaley_m
09.10.2013, 01:46
На 29 периодах у меня отличная точность получилась после перетасовки.
Алгоритм перетасовки следующий
j = 0;
for(i=0; i<256; i++)
{
y[j] = x[i];
j = (j+29) % 256;
}
Barmaley_m
09.10.2013, 03:51
Реализовал алгоритм, работающий на рекуррентном соотношении с 55 периодами и последующей перетасовкой. Число периодов и амплитуду синуса пришлось подбирать вручную: неоптимальные значения приводят к большим погрешностям. Соответственно был вычислен и жестко запрограммирован множитель k.
Вычисляется таблица синуса длиной 256 байт, 8-битные значения. Погрешность - +-8. На картинке красная линия - точные значения, синяя - вычисленные данной прогой.
58 байт.
Barmaley_m
09.10.2013, 04:12
А вот вариант на 73 периодах. Получилось даже еще лучше. Максимальная погрешность - +-5.
Для эффектов сойдёт, наверное, но в 3д это вставлять нельзя.
Можно. У X-Trade вместо синуса где-то использовалась аж парабола.
introspec
09.10.2013, 12:47
Можно. У X-Trade вместо синуса где-то использовалась аж парабола.
OK, согласен, перефразирую: "Можно, но не нужно потом пенять, что из-за 8-битной математики точки трясутся!" :v2_dizzy_roll:
У X-Trade вместо синуса где-то использовалась аж парабола.
я тоже использовал параболу в i512 и grass вроде. отлично работает.
---------- Post added at 15:19 ---------- Previous post was at 15:18 ----------
"Можно, но не нужно потом пенять, что из-за 8-битной математики точки трясутся!"
а они будут трястись? имхо, картинка просто будет слегка искажаться, чего я на глаз не замечал.
introspec
09.10.2013, 13:21
а они будут трястись? имхо, картинка просто будет слегка искажаться, чего я на глаз не замечал.
Смотря что делать, конечно. Смотря какого рода ошибки опять же. Ну, короче, я не критикую, я просто хочу чтоб человек выбирал процедуру осознанно и понимал, что байты не всегда бесплатно достаются.
Barmaley_m
09.10.2013, 14:07
Можно. У X-Trade вместо синуса где-то использовалась аж парабола.
Кстати о параболах. Я как раз недавно натыкался на одну статью. Там приводились коэффициенты многочлена 3-го порядка (кубической параболы) для приближения косинуса на интервале от 0 до pi/2. Так вот, многочлена третьего порядка оказалось достаточно, чтобы погрешность была менее 0.001! Для наших же целей 8-битной точности может оказаться достаточно и многочлена 2-го порядка, т.е. параболы. Ее коэффициенты должны быть вычислены методом минимакс-аппроксимации. Ну а получив четверть периода, можно, используя симметрию, получить и полный период.
---------- Post added at 13:07 ---------- Previous post was at 13:04 ----------
Вот коэффициенты минимакс-полинома третьего порядка для косинуса на интервале 0..pi/2:
y = 0.9998864206+0.00469*x-0.530309*x^2+0.063046*x^3;
introspec
09.10.2013, 14:08
Кстати о параболах. Я как раз недавно натыкался на одну статью. Там приводились коэффициенты многочлена 3-го порядка (кубической параболы) для приближения косинуса на интервале от 0 до pi/2. Так вот, многочлена третьего порядка оказалось достаточно, чтобы погрешность была менее 0.001! Для наших же целей 8-битной точности может оказаться достаточно и многочлена 2-го порядка, т.е. параболы. Ее коэффициенты должны быть вычислены методом минимакс-аппроксимации. Ну а получив четверть периода, можно, используя симметрию, получить и полный период.
Ну я же писал уже, ошибка будет 3-4%. Для меня сейчас - многовато, но где-то, конечно, хватит.
Barmaley_m
09.10.2013, 14:08
Максимальная абсолютная погрешность для приведенной выше формулы - 0.000114
introspec
09.10.2013, 14:09
Максимальная абсолютная погрешность для приведенной выше формулы - 0.000114
Это не парабола, правда? :)
ОК, я смотрел на параболу примерно в прошлом веке уже, могу и ошибаться сейчас.
Но с учётом кол-ва умножений и констант при таком подходе, меня просто что-то не прёт от такого подхода.
Вот коэффициенты минимакс-полинома третьего порядка для косинуса на интервале 0..pi/2:
y = 0.9998864206+0.00469*x-0.530309*x^2+0.063046*x^3;
А ничего, что эти вычисления сложнее, чем алгоритм рекурсивного генератора синуса (типа Герцеля)?
Barmaley_m
09.10.2013, 14:16
Кубический полином вычислять - сложнее. А квадратичный - может и ненамного сложнее. Константы при умножении закодировать жестко, как я это сделал для своей реализации рекурсивного алгоритма. А там видно будет. Значение x^2 можно вычислять так же, как это делается в алгоритме Брезенхама - по рекуррентному соотношению y[i] = y[i-1] + 2*x*dx
Побочный результат такого алгоритма - парабола. Ее можно использовать для быстрого умножения, подобно тому, как это сделано в Elite.
А что, Брезенхейм не прокатил?
для классической параболы вообще нет коэффициентов, т.е. просто x^2. вычисляется проще некуда.
Побочный результат такого алгоритма - парабола. Ее можно использовать для быстрого умножения, подобно тому, как это сделано в Elite.
Ну-ка, расскажи, как умножают в элите, интересно)
Barmaley_m
09.10.2013, 14:30
Умножают путем возведения в квадрат по таблице значений параболы. Допустим, нужно умножить a на b. Имеем:
(a+b)^2 = a^2 + 2*a*b + b^2
2*a*b = (a+b)^2 - a^2 - b^2
a*b = ((a+b)^2 - a^2 - b^2)/2
Квадраты a, b и a+b вычисляются по таблице. Остальные операции дешевые.
Умножают путем возведения в квадрат по таблице значений параболы. Допустим, нужно умножить a на b. Имеем:
(a+b)^2 = a^2 + 2*a*b + b^2
2*a*b = (a+b)^2 - a^2 - b^2
a*b = ((a+b)^2 - a^2 - b^2)/2
Квадраты a, b и a+b вычисляются по таблице. Остальные операции дешевые.
Хитро) Первый раз вижу такой подход)
Сколько байтная таблица? Сколько битное умножение?
Интересно, нет ли такого же хитрого деления?
Barmaley_m
09.10.2013, 14:35
Можно сделать умножение 7*7 бит. Таблица содержит 16-битные числа. Результат сложения a+b - 8-битное число, таким образом длина таблицы - 512 байт. Результат умножения, соответственно, 14-битный.
Сколько байтная таблица? Сколько битное умножение?
Интересно, нет ли такого же хитрого деления?
Здесь есть умножение и деление: http://zxpress.ru/article.php?id=11746
introspec
09.10.2013, 14:48
А что, Брезенхейм не прокатил?
Ну точки-то легко сделать, а вот потом преобразовать номер точки в угол пока не очень хорошо выходит. Буду думать ещё.
Здесь есть умножение и деление: http://zxpress.ru/article.php?id=11746
Хороший, подобный вышеописанноми из элиты алгоритм деления:
Lоg A/В= Lоg A-Lоg В
Однако, плохо применим для чисел с разрядностью больше 8, из-за больших таблиц.
---------- Post added at 15:16 ---------- Previous post was at 14:49 ----------
Хорошо бы какой-то алгоритм деления не поразрядный, но и не требующих таблиц сопоставимых с разрядностью исходных чисел.
Можно сделать умножение 7*7 бит. Таблица содержит 16-битные числа.
В Wolf 48K умножение беззнаковых 8*8 бит, таблица содержит 8-битные числа. В интро к невышедшему Body #40 умножение 15*15 бит беззнаковых, таблица содержит 16-битные числа (32 килобайта). Но интро, тем не менее, работает на 48К.
Хорошо бы какой-то алгоритм деления не поразрядный, но и не требующих таблиц сопоставимых с разрядностью исходных чисел.
Лучше использовать деление как можно реже. В моём 3d-движке его вообще нет (если не считать деления +-6/6 бит по таблице).
Лучше использовать деление как можно реже. В моём 3d-движке его вообще нет (если не считать деления +-6/6 бит по таблице).
А как ты делаешь перспективу? Только не говори, что заменяешь деление умножением. А обратное число берешь из таблицы в несколько килобайт.
По такой же таблице.
Размер и разрядность таблицы какова?
Страничка. Разрядность вроде как 6/+-7.
Страничка. Разрядность вроде как 6/+-7.
Страничка - это 16кб или 256 байт?
Что такое 6/+-7?
6 бит на входе, 7 со знаком на выходе?
Страничка - это 16 КБ.
6 бит делимое, 7 бит со знаком делитель.
Результат 7 бит со знаком.
Страничка - это 16 КБ.
Страничка - это, конечно, многовато, особенно для 48Кб.
Barmaley_m
06.11.2013, 14:18
Оптимизировал свою программу вычисления периода косинуса. Удалось выиграть несколько байт кода. Теперь длина равна 54 байтам. Погрешность - такая же, как и у предыдущего варианта.
Привет!
Реализовал синус многочленом.
Вычисляется он на промежутке (0..PI/2), в остальные четверти копируется.
Коэффициенты подобрал методоми "научного тыка" и "искусственного отбора". :)
Получился такой алгоритм:
HL=32737
BC=19
DE=5461
A=-20
FOR X=64 TO 0 STEP -1
SINTAB[X]=H
A=A-2
DE=DE+A
BC=BC-D
HL=HL+BC
NEXT X
Тоесть, строго говоря, я считаю косинус, но в итоге получается синус.
Отклонение abs(SINTAB[X]-sin(X*PI/128)*127.5) не превышает 0.503. Это очень близко к идеальному 0.5
И итоговый код:
sintabgen
ld hl,sintab+#40
ld d,h
ld e,l
exx
ld hl,32737
ld bc,19
ld de,5461
ld a,-20
EX AF,AF'
loop
ld a,h
exx
ld (hl),a
ld (de),a
inc e
dec l
jr z,cont
exx
ld a,c
EX AF,AF'
add a,-2
ld c,a
add e
jr c,$+3
dec d
ld e,a
ld a,c
EX AF,AF'
sub d
jr nc,$+3
dec b
ld c,a
add hl,bc
jr loop
cont
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
Это 55 байт кода.
Понимаю, что не рекорд, но это другой вариант, а значит у него другой потенциал оптимизации.
Писал в эмуляторе EmuZWin. "Генетический алгоритм" на дельфе7.
Если кто захочет другую амплитуду или период - пишите, попробую подобрать коэффициенты. Прогу на дельфе не привожу, не из жадности а от стыда. :)
А будет процедура расчета точки синуса из периода? Быстро, без таблиц :)
Вх. A=X [0..255]
Вых. А=Y (значение синуса)
Амплитуда и период должны меняться на входе в процедуру. Например задаются в HL.
Barmaley_m
26.11.2013, 14:59
Привет!
Реализовал синус многочленом.
...
Коэффициенты подобрал методоми "научного тыка" и "искусственного отбора". :)
Какого порядка многочлен? Было лень детально анализировать твой код, но кажется, что многочлен 3-го порядка?
Коэффициенты для таких многочленов надо подбирать не генетическими алгоритмами, а методом Ремеза (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_% D0%A0%D0%B5%D0%BC%D0%B5%D0%B7%D0%B0). Минимакс-аппроксимация. Кстати, в этой теме я приводил коэффициенты минимакс-многочлена 3й степени для приближения синуса (или косинуса).
Отклонение abs(SINTAB[X]-sin(X*PI/128)*127.5) не превышает 0.503. Это очень близко к идеальному 0.5
Вот это круто. Один лишний байт кода - зато существенно выше точность. Спасибо!
а значит у него другой потенциал оптимизации.
О да. У тебя там, смотрю, 16-битная арифметика реализована с применением jr c. Обычно от этих команд можно избавиться. Посмотри в мой синус, как там сделано. Например, условное увеличение или уменьшение на 1 можно реализовать командами вида ADC A,0 или ADC A,-1.
---------- Post added at 12:59 ---------- Previous post was at 12:55 ----------
Быстро, без таблиц :)
Это взаимоисключающие условия. Если без таблиц - значит с умножением, а умножение без таблиц быстрым не бывает.
Какого порядка многочлен? Было лень детально анализировать твой код, но кажется, что многочлен 3-го порядка?
Смотрим алгоритм(я его для наглядности и написал): A - меняется линейно, DE - квадратично, BC - третья степень, HL - четвёртая. H идёт в таблицу, значит многочлен 4-й степени.
Коэффициенты для таких многочленов надо подбирать не генетическими алгоритмами, а методом Ремеза (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_% D0%A0%D0%B5%D0%BC%D0%B5%D0%B7%D0%B0).
Эти методы ближе к непрерывным функциям, а у нас тут сплошная дискретика. И по аргументу и по значению. Эволюции-же дискретность только на руку: меньше вариантов мутаций и быстрее вычисления для отбора.
Вот если-бы в проце было аппаратное умножение с плавающей точкой, но не было синуса, тогда да. И без таблиц.
О да. У тебя там, смотрю, 16-битная арифметика реализована с применением jr c. Обычно от этих команд можно избавиться. Посмотри в мой синус, как там сделано. Например, условное увеличение или уменьшение на 1 можно реализовать командами вида ADC A,0 или ADC A,-1.
Да, спасибо, можно будет как-нибудь попробовать. Придётся перелапатить код(или переписать совсем), чтобы в нужный момент старший байт был в A. Может чего и оптимизируется. :)
Barmaley_m
27.11.2013, 19:01
Эти методы ближе к непрерывным функциям, а у нас тут сплошная дискретика. И по аргументу и по значению.
Дискретика? Ничего, что синус - непрерывная функция? Кроме того, алгоритм Ремеза - это обобщение на непрерывный случай менее известного r-алгоритма, который отыскивает наилучшее приближение функции по Чебышеву (минимум максимального отклонения) на дискретном наборе точек. Причем, в отличие от алгоритма Ремеза, который хоть и сходится быстро, но никогда 100% точно, r-алгоритм находит решение за конечное число операций. См. Демьянов, Малоземов "Введение в минимакс".
Другое дело, что в силу конечной точности представления аргумента и результата, иногда бОльшая точность достигается при таких коэффициентах аппроксимирующего многочлена, которые слегка отличаются от тех, которые оптимальны для случая бесконечной точности вычислений. Я читал недавно статью на эту тему. Не помню уже, какие методы там применялись, но по идее, можно пытаться "эволюционно" уточнять решение, которое было первоначально получено по Ремезу.
Придётся перелапатить код(или переписать совсем), чтобы в нужный момент старший байт был в A. Может чего и оптимизируется. :)
Не обязательно, чтобы старший байт был в A. Например, такая конструкция:
SBC A,A
ADD A,D
LD D,A
условно уменьшает регистр D на 1 за 12 тактов и 3 байта кода.
Спасибо за подсказки, но что-то у меня не получается выручить хотя-бы байтик, а переписать всё с нуля не хватает мотивации. :(
Barmaley_m
28.11.2013, 17:24
Спасибо за подсказки, но что-то у меня не получается выручить хотя-бы байтик, а переписать всё с нуля не хватает мотивации. :(
Ну ладно. Может быть когда-нибудь я сам засяду за оптимизацию. Можно еще вопрос по поводу дискретики? Алгоритм уже весьма оптимизирован - ведь в нем нет умножений, которые обычно характерны для многочленов. Получается, что на коэффициенты многочлена накладываются серьезные ограничения? Чему равны эти коэффициенты в опубликованной тобой программе?
Получается, что на коэффициенты многочлена накладываются серьезные ограничения? Чему равны эти коэффициенты в опубликованной тобой программе?
Многочлена в программе уже нет. Многочлен был прообразом.
То есть, образно говоря, ты хочешь узнать каким сортом овса я кормлю свой велосипед! :) Даже если конь идейно породил велосипед, всё равно велосипед уже не конь и овса не ест. Так и в моей программе многочлена уже давно нет, а есть сумматоры. Конечно можно было-бы восстановить и многочлен, для интереса, если-бы значения этих сумматоров не делилось-бы иногда на 256 с отбросом дробной части. А так даже восстановить нереально. :)
В качестве начального приближения к косинусу я брал F(t)=1-t^2+t^4.
Перевёл его в цифру и забыл о нём. А потом улучшал цифру.
Вот просто для любопытства, если-бы дробные части не отбрасывались, то восстановленный многочлен был-бы:
1.00297+0.01498*t-1.08493*t^2+0.16189*t^3+0.6596*t^4
Я глубоко убеждён, что это тебе никак не поможет! :) Поэтому посчитал на калькуляторе, без проверки о округлил на глазок.
Кстати, программировал когда нибудь движение точки с постоянным ускорением. Допустим прыжок персонажа? Если да, то вспомни этот момент, и тебе станет понятнее, при чём тут сумматоры и как обойтись без умножения.
Reobne, навскидку, - может в процедуре поменять местами запись байта и изменение констант (с корректировкой начальных величин, exx вынести вверх), пара байт лишнего jr loop уже и сэкономится, да и структура процедурки покрасивше станет ;)
Reobne, навскидку, - может в процедуре поменять местами запись байта и изменение констант (с корректировкой начальных величин, exx вынести вверх), пара байт лишнего jr loop уже и сэкономится, да и структура процедурки покрасивше станет ;)
Спасибо! Без одного JR-а размер стал 53 байта!
sintabgen
ld hl,32737-19
ld bc,19+5461/256
ld de,5461+20
exx
ld hl,sintab+#40
ld d,h
ld e,l
ld a,-20+2
EX AF,AF'
loop
exx
ld a,c
EX AF,AF'
add a,-2
ld c,a
add e
jr c,$+3
dec d
ld e,a
ld a,c
EX AF,AF'
sub d
jr nc,$+3
dec b
ld c,a
add hl,bc
ld a,h
exx
ld (hl),a
ld (de),a
inc e
dec l
jr nz,loop
;cont
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
Barmaley_m
29.11.2013, 02:05
Буду чуть позже разбираться, почему оно уходит и нельзя ли это как-то исправить путем манипуляций с коэффициентами или еще как.
Разобрался, почему уходит решение. При переходе от дифференциальных к разностным уравнениям надо ввести в коэффициенты небольшие поправки. По моим прикидкам, даже 3й порядок - это излишне. Коэффициент при x^3 получается около 1e-7, что меньше 2^-16, да и точность порядка 1e-4 не нужна, достаточно и 2^-8. Попробую рассчитать минимакс-полином 2го порядка.
абракадабра :)
ld c,-20+2
loop
dec c
dec c
ld a,c
exx
add e
jr c,$+3
dec d
ld e,a
;
ld a,c
sub d
jr nc,$+3
dec b
ld c,a
;
add hl,bc
ЗдОрово! Теперь 49 байт!
Провереный код:
sintabgen
ld hl,32737-19
ld bc,19+5461/256
ld de,5461+20
exx
ld hl,sintab+#40
ld d,h
ld e,l
ld c,-20+2
loop
dec c
dec c
ld a,c
exx
add e
jr c,$+3
dec d
ld e,a
ld a,c
sub d
jr nc,$+3
dec b
ld c,a
add hl,bc
ld a,h
exx
ld (hl),a
ld (de),a
inc e
dec l
jr nz,loop
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
отлично! :)
осталось добавить несколько наборов коэффициентов для разных максимальных "ширин синуса" (63, 31, 15...)
;)
по сути программы, получился типичный бризенхем / постройка окружности через похожесть графиков квадрата чисел и синусоиды, только с некоторой добавочной корректировкой приращений.
упрощая вычисления / делая короче, можно вернуться к графику квадрата чисел...
Прикинул, что можно выкинуть четвёртый порядок. Погрешность возрастёт примерно до 0.8, что незначительно. Если сейчас получится, то будет альтернативный, чуть менее точный, но более короткий вариант.
Вот что получилось:
sintabgen2 ;; 45 байт
ld SP,-64 ;!!!
ld de,32731-11
ld bc,11+5639/256
ld hl,5639+64
exx
ld hl,sintab+#40
ld d,h
ld e,l
loop
exx
add hl,sp
ld a,c
sub h
jr nc,$+3
dec b
ld c,a
ex de,hl
add hl,bc
ex de,hl
ld a,d
exx
ld (hl),a
ld (de),a
inc e
dec l
jr nz,loop
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
Не так уж сильно и сократилось. Чую есть ещё потенциал упрощения.
Barmaley_m
29.11.2013, 18:39
Рассчитал минимакс-полином второго порядка для косинуса на интервале от 0 до pi/2. Для удобства преобразовал диапазон аргумента из [0..pi/2] в [0..64], чтобы соответствовать таблице длиной в 256 байт. Также вычислял приближение на дискретном множестве точек (целые значения аргумента). Получившаяся формула:
y = 1.0130681110126272 - 3.1409834002847181e-3*x - 2.0249761634779685e-4*x^2
Диапазон аргумента - от 0 до 63 (при этом 64 соответствует pi/2). Диапазон значений функции - обычный для косинуса (от 0 до 1). Можно умножить все коэффициенты на 127, чтобы получить значения в диапазоне 8-битного целого со знаком.
Максимальная абсолютная погрешность данной формулы - 0.0131. Это хуже, чем достижимая для 8-битного целого (0.0039), поэтому лучше будет использовать многочлен 3-го порядка, хоть его точность приближения и избыточна.
Выручил указатель стека и ещё немного ужал.
За счёт замены прибавления 64 на сдвиг #44. И то и другое дают перенос раз в четыре цикла. :)
Максимальные отклонения значений в таблице от теории = 0.89.
sintabgen2 ;; 43 байта
ld de,32731-11
ld hl,11+5639/256
ld bc,65536-(5639+64)/256
exx
ld hl,sintab+#40
ld d,h
ld e,l
ld c,#44
loop
rlc c
exx
jr nc,$+3
inc c
add hl,bc
ex de,hl
add hl,de
ex de,hl
ld a,d
exx
ld (hl),a
ld (de),a
inc e
dec l
jr nz,loop
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
Barmaley_m
29.11.2013, 19:43
Да, об такой код недолго голову сломать :)
наоборот, все просто :)
а то использовать/портить SP - только заради одного стабильного изменения старшего байта на каждые 4 отбавки по 64 - это совсем было не дело :)
Красиво.
от jr можно избавиться так:
оригинал:
rlc c
exx
jr nc,$+3
inc c
очень просится ADC HL,BC... но тут всё хитрО :v2_dizzy_botan:
замена:
xor a
rlc c
exx
adc a,c
ld c,a
Сделал с примером отображения.
Теперь дело за малым: Сделать расчет разных амплитуд :v2_dizzy_coder:
вертится на уме, что надо бы попробовать использовать изменения L и E, чтобы не ротировать зазря C=#44
...
что-то вроде:
ld b,.....
....
ld a,e
sub l
exx
rrca
rra
add a, SOME_NUMBER
ld c,a
?
Спасибо, но не получается так.
Вот тоже, лёг спать, и мысль пришла заменить ld c,#44 и rlc c (4 байта) на ld a,l ... and 3 (3 байта) и условие соответственно изменить на NZ, но не получается. По фазе изменений не совпадает. Надо чтобы один раз в C было #EA, потом 4 раза #EB, 4 раза #EC и так далее. Вот это первое одиночное #EA весь ритм и сбивает.
---------- Post added at 04:21 ---------- Previous post was at 03:59 ----------
Спасибо за пример. :)
Сделать расчет разных амплитуд :v2_dizzy_coder:
Как-то лениво делать варианты для кучи амплитуд, большинство из которых и не понадобятся. Это уже не творчество а ремесло какое-то.
Вот Char предлагал следующую амплитуду взять 63. А почему не 64? Байт позволяет.
Если кому-нибудь для конкретной программы понадобится конкретный вариант(и по амплитуде и по фазе), то это уже мотивация.
А пока что это этюд на рекорд. Кто будет планировать свою 128 байтную дему, тому будет ориентировка, сколько примерно займёт генератор таблицы синуса. :)
ld a,e
exx
add hl,bc
and #03
jr nz,$+3
inc c
ex de,hl
?
ld a,e
exx
add hl,bc
and #03
jr nz,$+3
inc c
ex de,hl
?
Работает! Ещё байтик сэкономили! Теперь 42 байта.
пора глянуть весь листинг процедурки с окончательно посчитанными константами, в шестнадцатеричном виде, - что там получается...
sintabgen2 ;; 42 байта (#2a байта :) )
ld de,#7fd0
ld hl,#0021
ld bc,#ffea
exx
ld hl,sintab+#40
ld d,h
ld e,l
loop
ld a,e
exx
add hl,bc
and #03
jr nz,$+3
inc c
ex de,hl
add hl,de
ex de,hl
ld a,d
exx
ld (hl),a
ld (de),a
inc e
dec l
jr nz,loop
ld (hl),l
loop2
xor a
sbc a,(hl)
ld (de),a
inc l
inc e
jr nz,loop2
---------- Post added at 05:10 ---------- Previous post was at 05:02 ----------
Вариант в 41 байт:
sintab EQU #7b00 ; или #7d00
....
ld e,l
ld hl,sintab+#40
loop
exx
....
jr nz,loop-1 :smile:
Для разнообразия вот еще вам такой синус:
org $8000
LD B,201 ; Длина таблицы синуса
LD HL,$8100 ; Адрес начала таблицы синуса
EXX ;
XOR A ;
LD H,A ;
LD L,A ;
PUSH HL ;
LD IXL,$FE ;
JR LoopIn ;
;-------------------------------
MLoop:
EXX ;
SBC HL,BC ;
SBC A,IXL ;
LD IXL,D ;
;-------------------------------
LoopIn:
LD D,A ;
ADD A,A ;
SBC A,A ;
LD IXH,A ;
LD A,D ;
LD E,H ;
LD B,3 ;
RLoop: SRA D ;
RR E ;
DJNZ RLoop ;
POP BC ;
PUSH HL ;
SBC HL,DE ;
LD D,A ;
SBC A,IXH ;
ADD HL,HL ;
ADC A,A ;
EXX ;
LD (HL),A ;
INC L ;
DJNZ MLoop ;
POP AF ;
RET ;
Не самый короткий алгоритм - 53 байта.
Да и есть некие ограничения. Длина получаемой таблицы... 201 байт)
Однако, есть и плюсы - высокая точность (теоретически, т.к. это не аппроксимация а чистый синус). В таблице можно сохранять не 8 бит, а все 16 (а то и 24, т.к. в алгоритме 24-битная арифметика).
Так же возможна любая амплитуда.
Можно было бы сделать таблицу 256 байт, но это усложнило бы алгоритм, и он бы стал громоздким.
Изначально думалось, что алгоритм будет компактнее, т.к. я уже привык к 32-битным ARM-ам, где подобный алгоритм получился бы не более, чем за 10 команд.
Кто первый догадается, что за алгоритм - тому конфетка)
Из бейсика вывел полученную таблицу, поделив результат на 2. Вроде все норм.
http://s020.radikal.ru/i721/1311/9a/68acfd7b9c7c.png
Попробую угадать :)
complex Z=0+i*1
for i=0 to 200
Z=Z*(e^(i*PI/100))
SinTab[i]=Real(Z)
next
Попробую угадать :)
complex Z=0+i*1
for i=0 to 200
Z=Z*(e^(i*PI/100))
SinTab[i]=Real(Z)
next
Ой, а я в z плоскостях не ориентируюсь, поэтому ничего не могу сказать)
Это я теорию функций комплексного переменного вспомнил.
Если без неё, то примерно так:
Real x=0,y=1
for i=0 to 200
x, y = x*cos(d)+y*sin(d), -x*sin(d)+y*cos(d)
SinTab[i]=x
next
---------- Post added at 08:27 ---------- Previous post was at 08:26 ----------
d=PI/100
Это я теорию функций комплексного переменного вспомнил.
Если без неё, то примерно так
Это слишком общий случай, описывающий подобные генераторы вообще)
А я спрашивал именно про частный случай моего алгоритма.
Titus, как амплитуду/период менять?
Titus, как амплитуду/период менять?
Эм... я должен прервать конкурс 'угадай алгоритм'? )
Я уже нашел как. думаю никто не собирается тут что-то угадывать :)
Работает хорошо, но период/ампилитуды не любые конечно, немного меняется.
Мне вот требуется менять амплитуду увеличивая на 1... ?
Интересно как у тебя получилось менять период, если сказано:
Да и есть некие ограничения. Длина получаемой таблицы... 201 байт)
?
Интересно как у тебя получилось менять период, если сказано:
?
Вот и я удивился, как) Поделитесь опытом)
---------- Post added at 14:38 ---------- Previous post was at 14:37 ----------
Работает хорошо, но период/ампилитуды не любые конечно, немного меняется.
Мне вот требуется менять амплитуду увеличивая на 1... ?
А вот амплитуды можно абсолютно любые.
А вот амплитуды можно абсолютно любые.
В пределах разрядности :)
Сейчас пытаюсь придумать прогу, на базе "чересчур общего" алгоритма. 16-ти битные вычисления хочу сделать, и на все 256 байт период растянуть.
В пределах разрядности :)
Сейчас пытаюсь придумать прогу, на базе "чересчур общего" алгоритма. 16-ти битные вычисления хочу сделать, и на все 256 байт период растянуть.
Разрядность 24-битная, так что амплитуду можно настроить весьма тонко.
Чересчур общий - это какой?
Этот (http://zx-pk.ru/showpost.php?p=647816&postcount=101), который ты отбраковал. :)
Ладно, раз всем лениво, раскрою алгоритм, который весьма прост)
В данном случае используется алгоритм генерации синуса посредством рекурсивного цифрового генератора (о чем упоминалось даже в этой теме неоднократно). Многим он больше знаком по алгоритму Герцеля:
D0 = a1 * D1 - D2 + x,
D2 = D1,
D1 = D0,
который является модификацией данного генератора с добавленным возбуждением коэффициентом x. А сам генератор в чистом виде - это:
D0 = a1 * D1 - D2,
D2 = D1,
D1 = D0,
где a1 = 2 * cos (2 * pi * частота / частота_отсчетов),
или же a1 = 2 * cos (2 * pi * k);
Ввиду того, что алгоритм рекурсивный, требуется большая точность (разрядность) чисел. Приемлимой точности даже 16 битами (не говоря уже о 8) на отрезке в пару сот итераций не добиться. Поэтому выбрана разрядность 24 бита.
Далее о коэффициенте a1. Понятно, что ни о каком умножении речи быть не может. Единственный вариант - представить a1 в виде достаточно простого полинома вида 2 * (2^0 + 2^(...) + 2^(...) + ...) и т.д.
Самым простым полиномом, удовлетворяющим периоду близкому к 256, и при этом имеющим близкий к целому числу корень 1/k - это полином 2 * (2^0 - 2^(-11)), что легко представлятся в виде сдвига вправо на 8 + 3 бит, и одного вычетания. Что я и изобразил в своем алгоритме.
Посчитаем 1/k (число отсчетов) для данного полинома.
a1 = 2 * (1 - 2^(-11)) = 1,9990234375
1 / k = 1 / (arccos(a1 / 2) / (2 * pi) = 201.0536,
что является достаточно точным, близким к целочисленному периодом.
Если кого интересует полином для периода 256, то я тоже прикидывал его, у меня получился 2 * (2^0 - 2^(-12) - 2^(-14) + 2^(-18)), что потребует уже целых 3 сдвига и 3 сложения, усложняя код, ведь это все надо в 24-х битной арифметике сдвигать и складывать (ну, младшие части полинома можно и в 16, и даже в 12-битной).
Посчитаем 1/k (число отсчетов) для данного полинома:
a1 = 2 * (1 - 2^(-12) - 2^(-14) + 2^(-18)) = 1,99939727783203125
1 / k = 1 / (arccos(a1 / 2) / (2 * pi) = 255.92,
что уже менее точно, но все же достаточно приемлимо.
Вот вышеприведенный уже код, но с комментариями:
org $8000
LD B,201 ; Длина таблицы синуса 201 байт
LD HL,$8100 ; Адрес таблицы синуса
EXX ;
XOR A ; D0/D1 = $00.00.00
LD H,A ;
LD L,A ;
PUSH HL ; D2 = -$02.00.00
LD IXL,-2 ;
JR LoopIn ; --> LoopIn
;------------------------------- Главный цикл
MLoop:
EXX ;
SBC HL,BC ; A.H.L = A.H.L - LX.B.C
SBC A,IXL ; (D0 = a1*D1 - D2)
LD IXL,D ; Сохранить LX для D2 будущей итерации
;-------------------------------
LoopIn:
; D0/D1 = A.H.L
LD D,A ; D = A (и заодно сохранить A)
ADD A,A ;
SBC A,A ;
LD IXH,A ; A = $00/$FF, в зависимости от знака
LD A,D ; Восстановить A
LD E,H ;
LD B,3 ; DE = (A.H.L >> 8) >> 3 = A.H.L >> 11
RLoop: SRA D ;
RR E ;
DJNZ RLoop ;
POP BC ; Восстановить D2 = LX.B.C
PUSH HL ; Сохранить D1 = (A).H.L
SBC HL,DE ; A.H.L = A.H.L - HX.D.E
LD D,A ;
SBC A,IXH ;
ADD HL,HL ; A.H.L = A.H.L << 1
ADC A,A ; (D0 = a1 * D1)
EXX ; Сохранить A в (HL)+
LD (HL),A ; и цикл
INC L ;
DJNZ MLoop ;
POP AF ; Восстановить стек
RET ; Выход
---------- Post added at 15:21 ---------- Previous post was at 15:19 ----------
Да, начальная амплитуда задается через коэффициент в D2 со знаком минус.
Если хотите, программа на бейсике, чтобы побаловаться с коэффициентом a1 и периодом. Специально сделан 10-кратный прогон, чтобы было видно, как периоды ложаться друг на друга, т.е. чтобы сразу была видна погрешность.
Кстати, можно написать программу поиска близких к целочисленным корней 1/k для коротких полиномов (ну, скажем до 4-й степени), которая простым перебором найдет решения. Если они есть)
Вот что получилось.
Алгоритм, немного переделал, но смысл тот-же:
Real x=0,y=1
const d=2*PI/N/M, si=sin(d), co=cos(d)
for i=0 to N-1
for j=1 to M
x = x*co+y*si
y = -x*si+y*co
next M
SinTab[i]=x
next N
Разрядность вычислений принял 16.
N я принял за 256, а M подбирал, чтобы si и co получились удобные для умножения. В итоге принял М за 5.
При этом константу "co" можно вообще выкинуть, она, для 16 бит неотличима от единицы.
si=#0.014
То есть сдвинуть на 8 разрядов, сумма, потом ещё 2 разряда, и ещё сумма.
В итоге получилась такой фрагмент кода:
sintabgen5
ld de,289
ld hl,32769
xor a
exx
ld hl,sintab+#80
ld d,h
ld e,l
stb_loop1
neg
ld (de),a
ld b,10
stb_loop2
ld a,b
rra
sbc a,a
exx
ex de,hl
xor d
ld c,a
rla
sbc a,a
ld b,a
add hl,bc
sra c
sra c
add hl,bc
ld a,d
exx
djnz stb_loop2
inc e
dec l
ld (hl),a
jr nz,stb_loop1
Занимает она 43 байта. Погрешность около 2.
Работает, конечно, медленнее, есть внутренний цикл, но это меня совершенно не тревожит. :)
XOR там, чтобы знак менялся. По формуле надо то плюс, то минус. Заметили, что EX DE,HL только одно? :) Поэтому внутренний цикл до 10-ти.
Знаю, что инверсия и отрицание отличаются. Тут это большой роли не сыграло. Основная погрешность, всё-таки, из-за небольшого фазового расхождения.
Я конечно старался кодить покороче, до рекорда немного не дотянул. Интересно, совсем другой подход, а размер получился похожий. Прям закон информатики! :)
Но потенциал оптимизации, как всегда, неизвестен! А может даже точность повысить получится. Неизвестно.
Все эти рекорды ни к чему, если процедура не универсальна. Кто напишет универсальный код, чтобы на входе были параметры периода и амплитуды — тот и герой :) Коротко, быстро и точно.
А тот, кто демо в 256 байт пишет синус из калькулятора возьмёт. Точно и сердито :)
Это я теорию функций комплексного переменного вспомнил.
Если без неё, то примерно так:
Real x=0,y=1
for i=0 to 200
x, y = x*cos(d)+y*sin(d), -x*sin(d)+y*cos(d)
SinTab[i]=x
next
d=PI/100
Ты уверен в этой формуле? Написал на бейсике, дает затухающие колебания, каждый следующий период меньше предыдущего)
---------- Post added at 23:08 ---------- Previous post was at 23:06 ----------
Сделал вместо cos(d) единицу, затухать перестало)
Может быть не хватает разрядности бейсика?)
В формуле уверен. Это поворот вектора на угол.
Шлю свой бейсик-пример, сравни.
Исправь там 200 на 2000. Увидишь, что 10 кругов пиксель в пиксель легли. :)
Исправь там 200 на 2000. Увидишь, что 10 кругов пиксель в пиксель легли. :)
Понятно почему)
Я это:
x = x*co+y*si
y = -x*si+y*co
В лоб считал, а надо сперва t = x*co + y*si, потом уже x=t;
Ну не пользуюсь я в повседневной жизни, никаких своих программах, а так же при походе на вершину Джомолунгмы - комплексными числами)
Чем меньше шаг угла, тем меньше погрешности от такого упрощения. Поэтому я его и применил, у меня угол-то не ПИ/100, а ПИ/(128*5)=ПИ/640.
Надо было сразу об этом нюансе написать, не подумал.
Кто напишет универсальный код, чтобы на входе были параметры периода и амплитуды
Просто универсальных вещей не бывает, всегда есть ограничения.
Очень универсальный код, с 256-разрядной арифметикой никому не нужен.
Напиши поконкретнее, какую программу ждёшь? Скольки разрядная амплитуда? Какой возможный интервал изменения периода? Период произвольный или степени двойки? Какие ограничения на размер кода и на время выполнения? На точность есть-ли ограничения?
Вариант универсального алгоритма можно сказать вот он: это мозг. Вот мне, например, надо: наиболее короткий алгоритм, за две секунды чтобы сработал, сделал таблицу в 256 байтовых значений синуса, с периодом от 0 до 2*PI, 8 разрядных значений со знаком. Ввожу это себе в мозг, вырабатываю ряд вариантов. На форуме люди ещё помогают. Выберу потом наилучший вариант. Вот тебе и результат. :) Не плохой вариант! Плюс я надеюсь, что умнее стану. Тренировка и прокачка мозгов, понимаешь ли. :)
ИМХО это ближе по духу к спектруму, а более универсальный код ближе по духу к более мощным компьютерам.
В общем, виноват, но мне не понятно, что ты хочешь. Догадываюсь, что что-то хочешь, не просто-же "Баба Яга против". А что конкретно - непонятно. :(
Reobne, ты это, демы то когда писать начнешь?
И вы тут все за размер (зачем то) бьетесь, а мне интересно, сколько тактов занимает построение таблицы?
Построение таблицы один раз выполняется, поэтому тут размер первоочерёден, а такты практически не важны.
Демы, когда созрею. Пока-что идей много, но слишком абстрактны. Пускай выкристализовываются потихоньку, не буду же я себя насиловать. :)
Построение таблицы один раз выполняется
Не факт... представь что эффект разбит на сцены с разными значениями синуса...
Можно конечно кучу табличек нарендерить... а если памяти нету?
Да и куча... сколько она будет рендерится?
---------- Post added at 07:25 ---------- Previous post was at 07:24 ----------
кстати, не ты ли на хабре писал пару статей про демосцену?
Нет, статей не писал.
Ты меня убедил, что случаи бывают разные, немного посчитал тактов:
Вот этот код (http://zx-pk.ru/showpost.php?p=647579&postcount=81), например, который считает многочленом 4-го порядка(49 байт), работает за 12 128 тактов.
А вот этот (http://zx-pk.ru/showpost.php?p=647805&postcount=97), (многочлен 3-го порядка, 42 байта), за 11 233 такта.
Получается, и кадром моргнуть не успеешь, и ещё кучу дел сделаешь. Так что, один раз на сцену - никто не заметит. :)
Уверен, что через бейсик-калькулятор будет куда медленнее.
Но, возможно методом распаковки сжатых данных быстрее.
А ещё быстрее просто 32 готовых байта отзеркалить и инвертировать.
В теме столько толковых кодеров, которым грех писать только один синус. Ньюарт правильно говорит - сотворите классные демы и эффекты, это будет гораздо интереснее)
Barmaley_m
07.12.2013, 00:44
Ньюарт правильно говорит - сотворите классные демы и эффекты, это будет гораздо интереснее)
Видишь ли, интерес бывает разного плана. Синус - это нечто фундаментальное. Те, кто сделал в это вклад в данной теме, получили не просто синус, но и бесценный опыт и знания. Скажем, выяснили для себя пределы применимости рекуррентной формулы y[n] = c*y[n-1] - y[n-2] для вычислений с конечной точностью. Ну или расширили горизонты своих знаний в области быстрого вычисления полиномов, минимакс-аппроксимации и т.д.
Дема - это, по большому счету, домик из готовых кирпичиков. Нужно просто взять готовые кирпичики и сложить их вместе. Ну и опыт применим только в деле создания подобных домиков. История показывает, что великие демомейкеры далеко не всегда создавали другие интересные проекты или даже вообще не работают по специальности программистами или железячниками. Для зрителей - конечно, это интереснее. А вот для самих кодеров - не всегда.
Дема - это, по большому счету, домик из готовых кирпичиков. Нужно просто взять готовые кирпичики и сложить их вместе. Ну и опыт применим только в деле создания подобных домиков. История показывает, что великие демомейкеры далеко не всегда создавали другие интересные проекты или даже вообще не работают по специальности программистами или железячниками. Для зрителей - конечно, это интереснее. А вот для самих кодеров - не всегда.
Ну, не скажи. Смотря какая дема.
Когда пишешь какой-то эдакий доселе невиданный на Спеке эффект, необходимо несколько раз перековыркнуться через голову, что почище всякого синуса будет. Из кирпичиков складываются уже обьезженные эффекты, а что-то новаторское надо так же вылизывать, придумывать и оптимизировать, как этот наш синус.
А уж чем заниматься великим демомейкерам - это их дело) Rst7, кстати, до сих пор делает всякие интересные штуки, и порой оптимизацией железа/софта добивается такого соотношения цена/качество, чего другие сделать не могут.
Дема - это, по большому счету, домик из готовых кирпичиков.
Настоящее демо это оригинальный взгляд на привычные вещи, дизайн, музыку, код.
Что-то вроде эпловского "think different".
Настоящее демо это оригинальный взгляд на привычные вещи, дизайн, музыку, код.
Что-то вроде эпловского "think different".
Лично для меня (как уже обсуждалось в холиваре), главным является новаторство в коде. Музыка, дизайн и графика, конечно, должны быть соответствующие, но обязательно должен быть прогресс в коде относительно дем предыдущих поколений.
А на счет идей - есть тысячи амиговских дем с кучей разнообразных эффектов - вот тебе и идеи. Почему амиговские, потому что идеи на современных платформах сплошь 3D и все такое прочее. А Амига - это и колыбель демомейкинга (уж очень много на ней зачетных дем), и, в некотором роде, родственная по ресурсам платформа. Пусть мощнее, но все же родственная.
Лично для меня (как уже обсуждалось в холиваре), главным является новаторство в коде. Музыка, дизайн и графика, конечно, должны быть соответствующие, но обязательно должен быть прогресс в коде относительно дем предыдущих поколений.
А на счет идей - есть тысячи амиговских дем с кучей разнообразных эффектов - вот тебе и идеи. Почему амиговские, потому что идеи на современных платформах сплошь 3D и все такое прочее. А Амига - это и колыбель демомейкинга (уж очень много на ней зачетных дем), и, в некотором роде, родственная по ресурсам платформа. Пусть мощнее, но все же родственная.
колыбель скорее c64 чем амига, просот он у нас не популяерн ;)
вон для амиги best of OCS (http://www.pouet.net/prodlist.php?order=views&platform[]=Amiga+OCS%2FECS&page=1) до сих пор "State of the Art (http://www.pouet.net/prod.php?which=99)"
хотя сколько было крику что там "нет кода, и вообще одна анимация"
что не мешает деме с красивой реализацией и прекрсной музыкой уже много лет быть любимой.
(хотя мое имхо, там кроме кода демы, еще надо бы учитывать код которым создавалось это "видео")
хотя сколько было крику что там "нет кода, и вообще одна анимация"
что не мешает деме с красивой реализацией и прекрсной музыкой уже много лет быть любимой.
Ну, тут, опять же дело вкуса)
У меня любимые - это Binary, Extension, Hardwired, Technological Death, Arte, Love и т.д. Их много) А State of the Art я даже никогда не пересматриваю, хотя на заре амижества так же ее уважал. А сейчас возникнет вопрос - а где же эффекты?)
У меня вопрос - почему нельзя таблицу синуса сразу запилить в дату и не генерить ее программно?
Tronix, какой размер таблицы вашего синуса в дате?
Tronix, какой размер таблицы вашего синуса в дате?
А какая разница? Ну пусть будет 1024 байт. Я ее генерю и записываю в DB. Ну, и скажем код, который строит красивую неведомую хрень по этой таблице - 1024 байта. Итого - 2048 байт размер проги в памяти и на кассете.
Теперь берем процедуру генерации таблицы, саму табличку заполняем перед стартом. Значит у нас таблица - 1024, код крутящейся хрени - 1024 и еще сюда же код, строящий эту таблицу. Итого: в памяти оно занимает больше места, на кассете меньше.
introspec
08.12.2013, 17:18
Tronix, спасибо, конечно, за призыв к капитану Очевидность. Поработаю и я таким капитаном. Тут в теме нет ни одного человека, кто бы не умел сделать табличку синусов. Интерес именно в генерации такой таблички, максимально компактным кодом.
Если вы не понимаете контекст, в котором такие вещи бывают нужны, было бы куда грамотнее не разводить флейм в техническом треде, а помолчать, м.б. почитать и задуматься, зачем такие вещи бывают нужны.
Итого: в памяти оно занимает больше места, на кассете меньше.
В памяти генератор занимает место, пока не сгенерит табличку. После этого используй память под другие нужды.
Осталось только "на кассете меньше". :)
Alex Rider
08.12.2013, 18:57
Такие синусы нужны в программистском писькомерстве типа 256-байт демо или недоигра. С трудом себе представляю случай, когда в деме даже под 48 Кб не будет места под 64 байта таблицы синуса.
P.S. Не имею негативного отношения к мелкоконкурсам, просто не вижу их полезность.
Alex Rider, пиши игры под 48к
там нехватка 10 байт - обычное дело
просто не вижу их полезность.
это спорт. какая полезность в спорте?
Если вы не понимаете контекст, в котором такие вещи бывают нужны, было бы куда грамотнее не разводить флейм в техническом треде, а помолчать, м.б. почитать и задуматься, зачем такие вещи бывают нужны.
А я вот например прекрасно понял что он (Tronix) имел в виду.
Зря ты (introspec) ругнулся на него...
Знаю, ты ругаться любишь, но в этот раз у тебя шляпа вышла, уж без обид :)
А по поводу синуса - вот интересная статья: http://zxpress.ru/article.php?id=5525
И блин я так не угадал как-же можно
Цитирую:
P.S. А ведь можно обойтись и без
таблички данных SIN_DAT! Кто догадается -
как? : -)
Действительно, как?
introspec
09.12.2013, 18:21
А я вот например прекрасно понял что он (Tronix) имел в виду. Зря ты (introspec) ругнулся на него... Знаю, ты ругаться любишь, но в этот раз у тебя шляпа вышла, уж без обид :)
Ничто человеческое мне, конечно, не чуждо, запросто могу быть и неправ. Но моя претензия была не в том, что он написал что-то непонятное, а в том, что он написал что-то тривиальное.
А по поводу синуса - вот интересная статья: http://zxpress.ru/article.php?id=5525
Открываем мою ссылку прямо в этом треде и читаем: http://zx-pk.ru/showpost.php?p=633334&postcount=25
И блин я так не угадал как-же можно
Цитирую: "P.S. А ведь можно обойтись и без таблички данных SIN_DAT! Кто догадается - как? : -)" Действительно, как?
Destr, колись, ты вообще этот тред читал или так, мимо проходил? Тут 90% программ без табличек сделано.
Могу развернуть мою позицию. Сейчас на этом форуме практически полностью вымерли нормальные обсуждения серьёзных технических моментов. За всю осень я не могу вспомнить ни одной темы вызвавшей серьёзное обсуждение программистов. Кроме синуса. Поэтому, да, хотя я и осознаю, что эта тема узкоспециализированная и далеко не всем нужная, на данный момент это единственное место на форуме, где можно посмотреть как разные люди работают над оптимизацией стандартной задачи, используя разные подходы, разные стили программирования. Поэтому я нахожу эту тему чуть ли не самой полезной темой на форуме, за довольно долгое время. Поэтому я и пытаюсь защищать эту тему от засорения флудом.
Destr, колись, ты вообще этот тред читал или так, мимо проходил?
Колюсь: ниасилил весь, потому и ссылу пропустил (ну лажает у нас в деревне инет, бывает по полчаса страничку открываем, есть такое).
А по поводу синуса - что то я не понял. Ты дал ссыль на зеркало (ну эта самая статья) а вот как без таблички да честный синус - до сих пор тайна (для меня, по крайней мере. Ну делаю я скидку что лапоть деревенский, но блин в голове не могу умять чтоб процедура да генерации, да честный синус, да чтоб в 39 байт...)
P.S. Конечно речь не о калькуляторе ПЗУшном, уж там можно и полёт на Луну рассчитать.
Годиков эдак за 2-3...
Ага...
---------- Post added at 18:18 ---------- Previous post was at 18:13 ----------
В своей деме новогодней (которая за 2011 год кажись) я этот синус тупым инкрементом заделывал, он конечно получился нифига не синус, но похож, собака! :)
---------- Post added at 18:31 ---------- Previous post was at 18:18 ----------
Реализовал синус многочленом.
Вычисляется он на промежутке (0..PI/2), в остальные четверти копируется.
Коэффициенты подобрал методоми "научного тыка" и "искусственного отбора".
Получился такой алгоритм:
Код:
HL=32737
BC=19
DE=5461
A=-20
FOR X=64 TO 0 STEP -1
SINTAB[X]=H
A=A-2
DE=DE+A
BC=BC-D
HL=HL+BC
NEXT X
Да, именно так и делал.
Только не знал что это называется многочлен :)
P.S.S. На асме это всё конечно гораздо быстрей работает, но и гораздо страшней выглядит...
А по сабжу-заголовку - синус есть Святой Грааль.
Ищем его, ищем, а ничерта не находим, хотя и кричим периодически что вот мол "Есть он, уже нашли!!!"
Типа теоремы Ферма (которую уже как-бы доказали, но сцуко никакой математической базы так и не подвели. обошлись тупым перебором.)
Вот и мучаемся с синусом так-же как и древние с делением окружности на диаметр (да-да, то самое PI)
Ищем его, ищем, а ничерта не находим, хотя и кричим периодически что вот мол "Есть он, уже нашли!!!"
Вообще-то давно уже нашли) Вопрос в степени точности)
Вообще-то давно уже нашли) Вопрос в степени точности)
Да, браза!
Об чём и звук!
А что насчет Cordic? Лет 15 назад наковыривал эту тему, одни только сложнения и вычитания.
http://www.andreadrian.de/oldcpu/Z80_number_cruncher.html#mozTocId558053
Насколько я знаю в FPGA используются именно эти алгоритмы.
А что насчет Cordic? Лет 15 назад наковыривал эту тему, одни только сложнения и вычитания.
http://www.andreadrian.de/oldcpu/Z80...mozTocId558053
Жаль что на английском, статья-то похоже полезная :(
Жаль что на английском, статья-то похоже полезная :(
Не вникал, но мне кажется, что что-то типа рекурсивного цифрового генератора, на основе которого в этой теме приводились примеры. Хотя, может и другой алгоритм, надо разбираться.
В одной из ссылок по этому алгоритму лежит диссертация нашего товарища. http://baykov.de/CORDIC1972.htm
Т.е. по-русски, значит алгоритм CORDIC называется как Цифра-за-цифрой.
denpopov
12.02.2014, 08:11
Здрассте, дяденьки кодеры!
Что, ряд Тейлора никто не вспомнил?
способ, предложенный introspec'ом мне нравится, но в двух примерах генерации синуса он не понятен как принцип, зато апроксимация парабол иногда использовалась в демах.
и чем она удобна, это имхо то, что можно изменять амплитуду синусоиды. я написал код, но вышла фигня:
device zxspectrum128
ORG #6000
begin
ld bc,#8000
ld hl,0
ld de,0
sinlp1: add hl,de
ld a,h,(bc),a
ld a,e:add a,8:ld e,a
jr nc,noincd
inc d
noincd:
inc c
bit 6,c
;ld a,c:cp #41
jr z,sinlp1
;--------------------1st
ld e,#40;ld e,c
ld d,b;de=$807F,bc,=$8040
sinlp2:
ld a,(bc)
ld l,a
ld a,64*2-1:sub l
ld (de),a
inc e
dec c
jr nz,sinlp2
;jr $;c=$7F
ld c,a;bc=$807F,de=$8080
sinlp3:
ld a,(bc)
; neg
ld (de),a
dec c
inc e:jr nz,sinlp3
ld hl,#8000
drwlp:
ld a,(hl)
ld c,l
push hl
call 022B0h
;A=y
;c=X
call 022B0h
inc a
ld b,a
xor a:scf
bwlp:rra:djnz bwlp
or (hl):ld (hl),a
pop hl
inc l:jr nz,drwlp
jr $
end
display /d,end-begin
savesna "!test.sna",begin
и не могу понять в чем дело.
Что, ряд Тейлора никто не вспомнил?
По сути ряд Тейлора это многочлен. Мы тут еже много алгоритмов написали основаных на многочлене. Вопрос в том, насколько правильно, по обеспечения точности, находятся коэффициенты многочлена.
Ряд Тейлора грубее чем минимакс-полином, так как не учитывает значения функции на нужном диапазоне, а только в одной точке. А генетический подбор ещё точнее, так как учитывает ещё и дискретность.
Так что, может кто и вспомнил о ряде Тейлора, но смысла о нём писать не увидел, после того как уже написано о более точных методах.
Код дочитал до этого места:
;--------------------1st
ld e,#40;ld e,c
ld d,b;de=$807F,bc,=$8040
sinlp2:
ld a,(bc)
В коментах написано de=$807F а фактически de=$8040
В А загружается содержимое $8040, но мы ещё ничего туда не записали.
Идет копирование из первой четверти во вторую со сменой знака, но синус не меняет знак во второй четверти.
denpopov
12.02.2014, 09:26
В коментах написано de=$807F а фактически de=$8040
ну проверьте сами на отладчике пожалуйста.
Проверил, работает. Это не синус, а косинус, так что своё третье замечание я забираю назад, плюс ещё ошибка - двойной call 022B0h.
denpopov
12.02.2014, 10:04
Это не синус, а косинус, так что своё третье замечание я забираю назад
ну так принцип одинаковый же, наверное?
плюс ещё ошибка - двойной call 022B0h.
моя ошибка - убирал комментарии из глючного и неработающего исходника.
denpopov
27.05.2014, 16:30
а вот и CORDIC (http://www.andreadrian.de/oldcpu/sincos.z80)
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot