03.03.2022 09:40
SemenovVV 21 1900 Источник

На сайте habr.com/ru уже были похожие публикации осенью 2021 года:

Как посчитать синус быстрее всех

Как посчитать синус быстро

Не на Habr Как сделать быструю функцию для вычисления синуса? топик начат в 2003 году последний отклик в 2020 году.

Целью данной публикации попытка предложить способ расчета синуса и косинуса достаточно быстро для тех платформ, где отсутствуют эти функции (микроконтроллеры) или там где скорость расчета важнее точности.

Мне кажется, что выпуклые функции синус и косинус можно аппроксимировать не только рядом Тейлора ( многочленом вида a*x + b*x^3 +c*x^5 ... ) , а обычной параболой поведенной через точки 1,2,3 как на рисунке.

Точки 1 и 2 базовые, размещаются с определенным задаваемым шагом. В скрипте Scilab это переменная step. Координаты точки 3 будем вычислять таким образом, чтобы в ней было максимальное отклонение синуса ( или косинуса ) от отрезка 1-2.

Ниже приведены скрипты на Scilab для расчета коэффициентов полинома второй степени на интервале [ 0 ... pi /2] и графики отклонений для от функций синуса и косинуса .

Расчет коэффициентов для синуса на Scilab

/// синус
function [a,b,c]=  koef_parabola(x1,y1,x2,y2,x3,y3)
   /// расчет коэффициентов параболы по 3 точкам 
    a1= y3 -  ( x3*(y2-y1)+ x2*y1 -x1*y2 )/( x2-x1)
    a2=   x3*( x3-x1-x2 ) + x1*x2  
    a= a1 /a2
    b =( y2-y1)/( x2-x1) - a*( x1+x2)
    c=( x2*y1 - x1*y2) / (x2-x1)   + a * x1*x2
endfunction

kol_int =12   /// количество интервалов на отрезке 0 ... %pi/ 2
kol_funct =kol_int+1
step =%pi/ ( 2*kol_int)  /// шаг
point0_x =0:step:%pi/ 2
point0_sin = cos(point0_x)
aa_sin =1:1:(kol_int)
bb_sin =1:1:(kol_int)
cc_sin =1:1:(kol_int)
    xx1=0
    yy1=1
for ii=1:1:kol_int
    xx2=xx1+step
    yy2=cos(xx2)
    wsp1 =(yy2-yy1)/(xx2-xx1)  /// наклон
    xx3=asin(-wsp1)   /// координаты центральной точки
    yy3= sqrt( 1- wsp1^2)  ///  cos(xx3)
     [aa,bb,cc]=koef_parabola( xx1,yy1,xx2,yy2,xx3,yy3)
     aa_sin(ii)=aa
     bb_sin(ii)=bb
     cc_sin(ii)=cc         
     xx1=xx2
     yy1=yy2
end
 ///вывод шага и коэффициентов
 disp( step,aa_sin,bb_sin,cc_sin) 
    xx1=0
   xx2=step 
for ii=1:1:kol_int
int01=[xx1:0.005:xx2]    
a1=aa_sin(ii)
b1=bb_sin(ii)
c1=cc_sin(ii)
 plot(int01, (cos(int01) -  a1*int01^2 -b1*int01-c1 ) )
   xx1=xx1+step
   xx2=xx2+step 
end

Пример отклонений для синуса

график отклонений полинома второй степени от синуса на интервале 0 ... Пи/ 2 при разбиении на 8 интервалов ( размер интервала =Пи/ 16 примерно = 0.196 )

Расчет коэффициентов для косинуса на Scilab

function [a, b, c]=koef_parabola(x1, y1, x2, y2, x3, y3)
   /// расчет коэффициентов параболы по 3 точкам 
    a1= y3 -  ( x3*(y2-y1)+ x2*y1 -x1*y2 )/( x2-x1)
    a2=   x3*( x3-x1-x2 ) + x1*x2  
    a= a1 /a2
    b =( y2-y1)/( x2-x1) - a*( x1+x2)
    c=( x2*y1 - x1*y2) / (x2-x1)   + a * x1*x2
endfunction
kol_int =12   /// количество интервалов на отрезке 0 ... %pi/ 2
kol_funct =kol_int+1
step =%pi/ ( 2kol_int)  /// шаг
point0_x =0:step:%pi/ 2
point0_sin = cos(point0_x)
aa_sin =1:1:(kol_int)
bb_sin =1:1:(kol_int)
cc_sin =1:1:(kol_int)
xx1=0
yy1=1
for ii=1:1:kol_int
xx2=xx1+step
yy2=cos(xx2)
wsp1 =(yy2-yy1)/(xx2-xx1)  /// наклон
xx3=asin(-wsp1)   /// координаты центральной точки
yy3= sqrt( 1- wsp1^2)  ///  cos(xx3)
[aa,bb,cc]=koef_parabola( xx1,yy1,xx2,yy2,xx3,yy3)
aa_sin(ii)=aa
bb_sin(ii)=bb
cc_sin(ii)=cc
xx1=xx2
yy1=yy2
end
///вывод шага и коэффициентов
disp( step,aa_sin,bb_sin,cc_sin)
xx1=0
xx2=step
for ii=1:1:kol_int
int01=[xx1:0.005:xx2]
a1=aa_sin(ii)
b1=bb_sin(ii)
c1=cc_sin(ii)
plot(int01, (cos(int01) -  a1*int01^2 -b1*int01-c1 ) )
xx1=xx1+step
xx2=xx2+step
end

Пример отклонений для косинуса

график отклонений полинома второй степени от синуса на интервале 0 ... Пи/ 2 при разбиении на 12 интервалов

Синус таблица коэффициентов полинома степени 2 для 8 интервалов

( шаг Пи / 16 )

Я не привожу кода на каком либо языке или псевдокода, дабы не засорять публикацию, каждый желающий может подобрать себе коэффициенты полинома степени 2 для аппроксимации и написать свою функцию. По значению аргумента x вычисляем номер интервала, запоминаем коэффициенты и подставляем из в формулу полинома

Комментарии (21)


  1. iboltaev
    03.03.2022 10:03
    #24129861
    +6

    Мне кажется, что выпуклые функции синус и косинус можно аппроксимировать не только рядом Тейлора ( многочленом вида a*x + b*x^3 +c*x^5 ... ) , а обычной параболой поведенной через точки 1,2,3 как на рисунке

    Кажется - это плохо.

    Если нужно посчитать быстро и не очень точно, то лучше таблица + линейная интерполяция


    1. SemenovVV Автор
      03.03.2022 10:32
      #24129951

      так туже тоже самое, квадратичная интерполяция + можно подобрать требуемую точность размером интервала +вы пропустили слова не только ...


      1. iboltaev
        03.03.2022 11:12
        #24130089
        -1

        требуемую точность можно и размером таблицы подобрать


  1. Rsa97
    03.03.2022 10:16
    #24129893
    +7

    Если нужно быстро и не очень точно, то есть старая добрая формула Бхаскара, работающая на отрезке от 0 до 180°.
    image


    1. SemenovVV Автор
      03.03.2022 10:33
      #24129955

      а отрезка от 0 до 90° мало? + что проще считать? где больше делений и умножений?


      1. unsignedchar
        03.03.2022 10:46
        #24130005
        +2

        Это больше вопрос с индусу, который в 7 веке додумался до этой формулы;).

        ЗЫ: нужна ли программисту математика за пределами школьной?


        1. boris768
          03.03.2022 10:51
          #24130019

          В геймдеве - очень нужна, вообще всё завязано на алгебре и аналитической геометрии


          1. iboltaev
            03.03.2022 11:15
            #24130101

            это первый курс института, но ок


            1. boris768
              03.03.2022 11:44
              #24130259

              вопрос так и стоял, первый курс в моем понимании - за пределами школьной


      1. Rsa97
        03.03.2022 11:02
        #24130059

        Отрезка 0-90°, конечно, достаточно, но формула симметрична относительно 90°.
        А по вычислениям тут два вычитания, два умножения и деление.


    1. SemenovVV Автор
      03.03.2022 16:54
      #24131293

      если считать по предлагаемому мной способу, то всего на 6 интервалах точность вычисления синуса примерно в 10 раз выше чем по формуле Бхаскара. + по сложности (число делений и умножений ) как вычисление числителя. Снимаю шляпу перед Бхаскаром. Очень интересно, как он до своей формулы додумался?


      1. Rsa97
        03.03.2022 17:24
        #24131441
        +1

        У вас полином второй степени ax2+bx+c. Значит три умножения и два сложения.
        y = x*x, y = a*y, z = b*x, z = z+y, z = z+c.

        Столько же операций и в формуле Бхаскара, только там не надо искать интервал в таблице.
        y = 180-x, y = y*x, z = 40500-y, y = y*4, y = y/z.


        1. premierhr
          04.03.2022 13:46
          #24133497

          Операция деления совсем не равнозначна по машинным циклам умножению.


  1. AVI-crak
    03.03.2022 10:24
    #24129929

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

    https://github.com/AVI-crak/Rtos_cortex/blob/master/math_s.c#L356


  1. Ktator
    03.03.2022 10:57
    #24130035
    +3

    Целью данной публикации попытка предложить способ расчета синуса и косинуса достаточно быстро

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

    Мне кажется, что выпуклые функции синус и косинус можно аппроксимировать ...

    Математика – это точная наука, здесь не может ничего казаться. Как только вы определите критерии, сразу появится возможность будет вычислить, можно или нельзя.

    Я не привожу кода на каком либо языке или псевдокода, дабы не засорять публикацию

    У вас публикация и так короткая, можно было бы и добавить (ну или хотя бы выложить на github). Не то, что это сложно или лично мне интересно, но просто глаз резануло от такого заявления.


    1. SemenovVV Автор
      03.03.2022 11:26
      #24130187

      согласен, что математика точная наука. но фактически все наши вычисления с вещественными числами приближенные. код не привел т.к. он существенно зависит от требуемой точности вычислений и размера интервала (шага). А так достаточно просто, определили в какой интервал попадает аргумент, вытащили коэффициенты ( могут храниться в массиве ), вычислили полином степени 2.


      1. Ktator
        03.03.2022 11:46
        #24130265

        но фактически все наши вычисления с вещественными числами приближенные.

        Не понял, к чему это. Я же не писал, что мы вычисляем что-то идеально точно.


  1. Daemonis
    03.03.2022 12:20
    #24130365
    +5

    Мне кажется, линейной функцией будет еще быстрее :)

    ПС: а можно и константой 0.5 :) Так будет практически мгновенно и довольно точно :)


    1. Tiriet
      03.03.2022 19:57
      #24131783
      +2

      А на интервале (0..2Pi) лучше аппроксимировать нулем!


      1. Dlougach
        04.03.2022 10:49
        #24132975

        В последнюю неделю — уже не нулём, а π.


    1. premierhr
      04.03.2022 14:06
      #24133561

      тогда константа - 2/pi