Генерация синуса

[Barmaley_m]

Привет!
Реализовал синус многочленом.
...
Коэффициенты подобрал методоми "научного тыка" и "искусственного отбора".

Какого порядка многочлен? Было лень детально анализировать твой код, но кажется, что многочлен 3-го порядка?

Коэффициенты для таких многочленов надо подбирать не генетическими алгоритмами, а методом Ремеза. Минимакс-аппроксимация. Кстати, в этой теме я приводил коэффициенты минимакс-многочлена 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 ----------

Быстро, без таблиц

Это взаимоисключающие условия. Если без таблиц - значит с умножением, а умножение без таблиц быстрым не бывает.

[Reobne]

Какого порядка многочлен? Было лень детально анализировать твой код, но кажется, что многочлен 3-го порядка?

Смотрим алгоритм(я его для наглядности и написал): A - меняется линейно, DE - квадратично, BC - третья степень, HL - четвёртая. H идёт в таблицу, значит многочлен 4-й степени.

Коэффициенты для таких многочленов надо подбирать не генетическими алгоритмами, а методом Ремеза.

Эти методы ближе к непрерывным функциям, а у нас тут сплошная дискретика. И по аргументу и по значению. Эволюции-же дискретность только на руку: меньше вариантов мутаций и быстрее вычисления для отбора.
Вот если-бы в проце было аппаратное умножение с плавающей точкой, но не было синуса, тогда да. И без таблиц.

О да. У тебя там, смотрю, 16-битная арифметика реализована с применением jr c. Обычно от этих команд можно избавиться. Посмотри в мой синус, как там сделано. Например, условное увеличение или уменьшение на 1 можно реализовать командами вида ADC A,0 или ADC A,-1.

Да, спасибо, можно будет как-нибудь попробовать. Придётся перелапатить код(или переписать совсем), чтобы в нужный момент старший байт был в A. Может чего и оптимизируется.

[Barmaley_m]

Эти методы ближе к непрерывным функциям, а у нас тут сплошная дискретика. И по аргументу и по значению.

Дискретика? Ничего, что синус - непрерывная функция? Кроме того, алгоритм Ремеза - это обобщение на непрерывный случай менее известного r-алгоритма, который отыскивает наилучшее приближение функции по Чебышеву (минимум максимального отклонения) на дискретном наборе точек. Причем, в отличие от алгоритма Ремеза, который хоть и сходится быстро, но никогда 100% точно, r-алгоритм находит решение за конечное число операций. См. Демьянов, Малоземов "Введение в минимакс".

Другое дело, что в силу конечной точности представления аргумента и результата, иногда бОльшая точность достигается при таких коэффициентах аппроксимирующего многочлена, которые слегка отличаются от тех, которые оптимальны для случая бесконечной точности вычислений. Я читал недавно статью на эту тему. Не помню уже, какие методы там применялись, но по идее, можно пытаться "эволюционно" уточнять решение, которое было первоначально получено по Ремезу.

Придётся перелапатить код(или переписать совсем), чтобы в нужный момент старший байт был в A. Может чего и оптимизируется.

Не обязательно, чтобы старший байт был в A. Например, такая конструкция:
SBC A,A
ADD A,D
LD D,A
условно уменьшает регистр D на 1 за 12 тактов и 3 байта кода.

[Reobne]

Спасибо за подсказки, но что-то у меня не получается выручить хотя-бы байтик, а переписать всё с нуля не хватает мотивации.

[Barmaley_m]

Спасибо за подсказки, но что-то у меня не получается выручить хотя-бы байтик, а переписать всё с нуля не хватает мотивации.

Ну ладно. Может быть когда-нибудь я сам засяду за оптимизацию. Можно еще вопрос по поводу дискретики? Алгоритм уже весьма оптимизирован - ведь в нем нет умножений, которые обычно характерны для многочленов. Получается, что на коэффициенты многочлена накладываются серьезные ограничения? Чему равны эти коэффициенты в опубликованной тобой программе?

[Reobne]

Получается, что на коэффициенты многочлена накладываются серьезные ограничения? Чему равны эти коэффициенты в опубликованной тобой программе?

Многочлена в программе уже нет. Многочлен был прообразом.
То есть, образно говоря, ты хочешь узнать каким сортом овса я кормлю свой велосипед! Даже если конь идейно породил велосипед, всё равно велосипед уже не конь и овса не ест. Так и в моей программе многочлена уже давно нет, а есть сумматоры. Конечно можно было-бы восстановить и многочлен, для интереса, если-бы значения этих сумматоров не делилось-бы иногда на 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
Я глубоко убеждён, что это тебе никак не поможет! Поэтому посчитал на калькуляторе, без проверки о округлил на глазок.

Кстати, программировал когда нибудь движение точки с постоянным ускорением. Допустим прыжок персонажа? Если да, то вспомни этот момент, и тебе станет понятнее, при чём тут сумматоры и как обойтись без умножения.

[Advertiser]

[char]

Reobne, навскидку, - может в процедуре поменять местами запись байта и изменение констант (с корректировкой начальных величин, exx вынести вверх), пара байт лишнего jr loop уже и сэкономится, да и структура процедурки покрасивше станет

[Reobne]

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]

Буду чуть позже разбираться, почему оно уходит и нельзя ли это как-то исправить путем манипуляций с коэффициентами или еще как.

Разобрался, почему уходит решение. При переходе от дифференциальных к разностным уравнениям надо ввести в коэффициенты небольшие поправки. По моим прикидкам, даже 3й порядок - это излишне. Коэффициент при x^3 получается около 1e-7, что меньше 2^-16, да и точность порядка 1e-4 не нужна, достаточно и 2^-8. Попробую рассчитать минимакс-полином 2го порядка.

[char]

абракадабра

  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