Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
В принципе, в этой постановке задача решается в уме, поскольку синус малого угла равен углу.
31415/180 = 15707/9.
То есть в уме надо разделить 157075 на 9, что не вызывает сомнений, равно 174527 и совпадает с Вашим ответом до 7 знака.
31415/180 = 15707/9.
То есть в уме надо разделить 157075 на 9, что не вызывает сомнений, равно 174527 и совпадает с Вашим ответом до 7 знака.
Экскурс в античную тригонометрию. Текст до хабраката мне показался слишком скудным для такой интересной статьи.
За 355/113 спасибо, правда не знаю, что проще запомнить, учитывая то, что 3.14 точно уже у всех отскакивает от зубов.
Но вот 3,1415926 отскакивает далеко не у всех.
Это я знаю и помню прекрасно, пи многие знаки мне лишни напрасны = 3,14159265358
Помню класса с пятого
Помню класса с пятого
у меня до 6 знака (3.141592) отскакивает. У жены — почти до двадцатого :) Для тренировки она себе пи до какого-то там знака на пароль поставила :)
Чтобы нам не ошибиться,
Надо правильно прочесть:
Три, четырнадцать, пятнадцать,
Девяносто два и шесть
Вполне себе от зубов :)
Надо правильно прочесть:
Три, четырнадцать, пятнадцать,
Девяносто два и шесть
Вполне себе от зубов :)
Нас вот так учили запоминать эту дробь:
Есть мнение, что
а) иногда синус аппаратно считают через таблицы (аля Брадиса) с поправками до 3-ей степени. Для машинной точности типа double таблицы получаются не такие уж и большие по размеру, зато очень быстро — пара умножений и сложений;
б) иногда синус считают аппаратно разложением в ряд, в котором коэффициенты посчитаны заранее. Тоже остаётся только сложение и умножение.
а) иногда синус аппаратно считают через таблицы (аля Брадиса) с поправками до 3-ей степени. Для машинной точности типа double таблицы получаются не такие уж и большие по размеру, зато очень быстро — пара умножений и сложений;
б) иногда синус считают аппаратно разложением в ряд, в котором коэффициенты посчитаны заранее. Тоже остаётся только сложение и умножение.
a) Верно, именно так, например, считается синус в библиотеке C когда нет поддержки плавающей точки. Но на калькуляторах так делают редко. Умножение на калькуляторе — дорогая операция, а в CORDIC используются только сложение и сдвиги.
б) Я раньше тоже так думал, но на практике ни разу не встречал. Подозреваю, что это весьма редкое явление.
б) Я раньше тоже так думал, но на практике ни разу не встречал. Подозреваю, что это весьма редкое явление.
берём первые члены ряда Фурье для синуса, упрощаем/сокращаем и получаем простую формулу для синуса любого угла
По первой картинке я уж подумал, что вычисление синуса будет с использованием ряда Тейлора с помощью Arduino, который будет сам кнопочки нажимать…
Я в одной из библиотек видел такой алгоритм — сначала по формулам приведения сводим аргумент к отрезку [0,pi/4], потом применяем к нему синус или косинус (в зависимости от того, какая функция получилась), заданный в виде аппроксимирующего многочлена (8-й или 9-й степени, в зависимости от требуемой точности).
Хабр — торт. Простой математический пример в статье, и множество комментариев с методами, алгоритмами, и т.п.
> Отношение 355/113 — это единственное приближение числа π рациональной дробью, которое короче десятичного представления аналогичной точности.
Ну, не единственное. В десятичной системе счисления ничего уникального нет. Но «единственное такое, что одновременно короткое и с отличной точностью» — это да.
Ну, не единственное. В десятичной системе счисления ничего уникального нет. Но «единственное такое, что одновременно короткое и с отличной точностью» — это да.
Вот тут товарищ Jon McLoone специально искал и не нашёл ничего лучше: All Rational Approximations of Pi Are Useless.
Если брать относительный выигрыш — то может быть, других и нет. Странно, что в этом тексте нет упоминания о разложении в цепную (непрерывную) дробь. Казалось бы, чем больше член разложения, который мы отбрасываем, тем больше должен быть выигрыш в цифрах. Если 355/113 (отбросили 292) даёт 1 знак выигрыша, то приближение первыми 453293 членами разложения (отброшен член 12996958) должно дать 5, а то и 6 знаков.
Ещё странно сравнение sqrt(2) и «e». У sqrt(2) цепная дробь ограничена, поэтому выигрыша больше, чем в 1 цифру, мы не получим никогда, но у «e» её члены неограниченно растут (хотя и довольно медленно — линейно), и, грубо говоря, удлинение записи в 10 раз всегда будет давать лишнюю цифру выигрыша.
Ещё странно сравнение sqrt(2) и «e». У sqrt(2) цепная дробь ограничена, поэтому выигрыша больше, чем в 1 цифру, мы не получим никогда, но у «e» её члены неограниченно растут (хотя и довольно медленно — линейно), и, грубо говоря, удлинение записи в 10 раз всегда будет давать лишнюю цифру выигрыша.
В комментариях пишут то же самое, про convergents of continued fractions. Их можно посчитать через WolframAlpha, например, Last[Convergents[Pi, 6]] = 104348/33215. Но выигрыша нет — надо запоминать 11 цифр, чтобы получить π с точностью 10 цифр.
В любом случае много цифр запоминать смысла нет, так что это уже искусство для искусства.
В любом случае много цифр запоминать смысла нет, так что это уже искусство для искусства.
Спасибо за интересную статью!
Ждём продолжения — как посчитать это же на камушках и римскими цифрами 8)).
Интересно, почему в вычислении синуса «по цифрам» не делалось округления при сдвиге:
вместо
было бы лучше (при k>0, конечно),
Да и таблица арктангенсов в конце могла бы быть точнее. Выбросить 2/3 её, к сожалению, нельзя — поправочный коэффициент перестанет быть предсказуемым — но заменить вторую половину на обычное умножение (которое наверняка реализовано очень эффективно) было бы и быстрее, и точнее.
Впрочем, военным виднее. Они высоко летают.
вместо
int tx = c - (((s >> k) ^ d) - d);было бы лучше (при k>0, конечно),
int tx = c - (((((s >> (k - 1)) + 1) >> 1) ^ d) - d);Да и таблица арктангенсов в конце могла бы быть точнее. Выбросить 2/3 её, к сожалению, нельзя — поправочный коэффициент перестанет быть предсказуемым — но заменить вторую половину на обычное умножение (которое наверняка реализовано очень эффективно) было бы и быстрее, и точнее.
Впрочем, военным виднее. Они высоко летают.
почему в вычислении синуса «по цифрам» не делалось округления при сдвиге
Думаю, что для простоты. Попробовал предложенный вариант, получил тот же результат.
заменить вторую половину на обычное умножение
Умножение на калькуляторе — дорогая операция. В частности именно поэтому не используются приближения многочленами или рядами.
На физике нас учили, что
sin a ≈ a, если a -> 0
Пригодилось множество раз.
sin a ≈ a, если a -> 0
Пригодилось множество раз.
А аппроксимация полиномами Чебышева не подойдет?
Умножение на калькуляторе — дорогая операция, реализуется программно. А сложение и сдвиг — дешёвые, реализованы аппаратно. Поэтому и не используются приближения многочленами или рядами.
Умножение реализуется через сложение и сдвиги, так что ваше утверждение не очевидно. Функция умножения в любом калькуляторе уже реализована, скорость вычисления в пределах миллисекунд — удовлетворительно, т.к. операции всё равно вводятся вручную. Не вижу смысла отказываться от рядов, если алгоритм будет проще — аппаратная реализация будет в итоге проще и дешевле.
Посмотрите на картинку в начале статьи. Этот калькулятор питается от маленькой солнечной батареи, и даже солнца ему не надо — достаточно настольной лампы. Тактовая частота меряется не в гигагерцах и даже не в мегагерцах, а в килогерцах. Для него одно умножение занимает миллисекунды, а чтобы многочлен посчитать уже секунды уйдут, неприемлемо.
Разработчики калькуляторов это ещё в семидесятые годы прикинули и вышло, что CORDIC лучше. Разумеется, на более привычном процессоре помощнее всё может оказаться наоборот.
Разработчики калькуляторов это ещё в семидесятые годы прикинули и вышло, что CORDIC лучше. Разумеется, на более привычном процессоре помощнее всё может оказаться наоборот.
В бейсике «Спектрум» и во многих других бейсиках того времени для вычисления синусов использовалось именно разложение в ряд Чебышева. Думаю, дело в том, что в литературе по численным методам 80-х годов (всякие книги типа МакКракен и Дорн и т.д.) разложение в ряд Чебышева было самым продвинутым методом аппроксимации, которые рассматривались. Программисты подобного софта по большей части просто не знали, какие еще бывают методы.
CORDIC более перспективен для аппаратной реализации, т.к. не требуется умножение. На самом деле умножение — очень затратная операция по времени либо аппаратным ресурсам. Если разрабатывать микросхему, вычисляющую синус — то лучше отказаться от умножителя и реализовать CORDIC, чем использовать умножитель и аппроксимацию, основанную на умножении. То же касается ассемблерного кода для процессоров, не имеющих аппаратного умножителя.
Если есть умножитель, то несколько лучше, чем разложение в ряд Чебышева, применить аппроксимацию минимакс-полиномом. Коэффициенты такого полинома вычислить сложнее, чем Чебышева, но стоит только освоить алгоритм Ремеза — как трудности исчезнут. Аппроксимация же рядом Тейлора (Маклорена) — это очень неэффективный подход.
Если имеется много памяти — то лучше всего хранить в ней таблицу значений синуса и применять линейную интерполяцию для промежуточных углов. Линейная интерполяция по сути сводится к одному умножению.
При вычислении синусов еще важно то, в какой последовательности надо их вычислять. Скажем, если нужно вычислить синусы многих углов, равноотстоящих друг от друга — то есть рекуррентные соотношения. y[i] = -y[i-2] + 2*b*y[i-1], константа b задает шаг. Одно умножение и два сложения — и это при том, что данная формула дает точные ответы. Конечно, при ее использовании будет накапливаться ошибка округления, поэтому представление чисел должно иметь много бит, и самые младшие из них будут постепенно зашумляться. Есть и другие рекуррентные формулы, вычисляющие одновременно синус и косинус многих углов, где влияние ошибок округления уменьшено.
CORDIC более перспективен для аппаратной реализации, т.к. не требуется умножение. На самом деле умножение — очень затратная операция по времени либо аппаратным ресурсам. Если разрабатывать микросхему, вычисляющую синус — то лучше отказаться от умножителя и реализовать CORDIC, чем использовать умножитель и аппроксимацию, основанную на умножении. То же касается ассемблерного кода для процессоров, не имеющих аппаратного умножителя.
Если есть умножитель, то несколько лучше, чем разложение в ряд Чебышева, применить аппроксимацию минимакс-полиномом. Коэффициенты такого полинома вычислить сложнее, чем Чебышева, но стоит только освоить алгоритм Ремеза — как трудности исчезнут. Аппроксимация же рядом Тейлора (Маклорена) — это очень неэффективный подход.
Если имеется много памяти — то лучше всего хранить в ней таблицу значений синуса и применять линейную интерполяцию для промежуточных углов. Линейная интерполяция по сути сводится к одному умножению.
При вычислении синусов еще важно то, в какой последовательности надо их вычислять. Скажем, если нужно вычислить синусы многих углов, равноотстоящих друг от друга — то есть рекуррентные соотношения. y[i] = -y[i-2] + 2*b*y[i-1], константа b задает шаг. Одно умножение и два сложения — и это при том, что данная формула дает точные ответы. Конечно, при ее использовании будет накапливаться ошибка округления, поэтому представление чисел должно иметь много бит, и самые младшие из них будут постепенно зашумляться. Есть и другие рекуррентные формулы, вычисляющие одновременно синус и косинус многих углов, где влияние ошибок округления уменьшено.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
sin 1° на калькуляторе