Приближённое вычисление математических функций для калькулей

[Lavr]

Я тут не просто поехидствовал из вредности, как может показаться...

Просто алгоритм для арифмометра Однера (aka ФеликсЪ) - это тоже математически какой-то ряд,
но в инструкции к арифмометру об этом не писали, а просто привели алгоритм.

Так что сколько раз "покрутить ручку", это как я полагаю, за сколько итераций ряд сходится.
И вряд ли для железки с ручкой предлагали алгоритм с плохой сходимостью, хотя, как я понимаю,
специфика этого "железного калькулятора" также предъявляла к алгоритму свои требования...

[Lavr]

Просто алгоритм для арифмометра Однера (aka ФеликсЪ) - это тоже математически какой-то ряд, ...

Что-то мне даже самому интересно стало... вот тут некто математику этой затеи расписывает:
Математика для всех. Квадрат числа: интересное свойство

[Andnor]

Ну да, но не все ряды одинаково полезны. Ну тут же очевидно что для получения n² по этой формуле нужно сложить n чисел. Если приближенно вычислять, то для двух цифр понадобится от 10 до 99 сложений. Поэтому я и говорю, что метод фигня. По формуле квадрата суммы сходится гораздо быстрее, и эта формула тоже из курса школьной математики где-то за 7-й класс.

Вот ещё пример покажу. Предположим, нужен корень 19619
1. Для получения первой цифры убираем по две цифры справа пока не останется одна или две: 1, убрано 4 цифры. Значит первое приближение: 100
2. По формуле квадрата суммы получаем следующее приближение: (19619 - 100²)/(2*100)+100 = 148.095. Цифры после запятой отбросим, так как я в уме считаю, да и благодаря формуле ошибка постепенно исправится.
3. 148²=21904, теперь можно по формуле квадрата разности: 148-(148²-19619)/(2*148)≈140.280, думаю можно опять отбросить то что после запятой.
4. 140²=19600, уже очень близко. Опять формула квадрата суммы: (19619 - 140^2)/(2*140)+140 ≈ 140.067857. Как видим, до целых ответ получен, можно попробовать ещё уточнить.
5. 140.067857² = 19619.004564572449, уже и так неплохо, но ладно: 140.067857-(140.067857^2-19619)/2/140.067857 ≈ 140.067840705853.

Ну тут уже точности за глаза. И это всего пять итераций. В целом это всё линейная интерполяция по производной функции y=x²: y'=2x.

На арифмометре для того чтобы получить 140², тебе бы пришлось сделать 140 сложений.

Code: Select all

$ bc -lq
s=0; for (i=1;i<280;i+=2) s+=i; s
19600

На арифмометре ты задолбаешься. Проще напрямую 140 умножить на 140, понадобится всего пять оборотов ручки.

[Lavr]

На арифмометре ты задолбаешься. Проще напрямую 140 умножить на 140, понадобится всего пять оборотов ручки.

Во-перых, не "тыч" мне, я не давал тебе для этого поводов... и слова выбирай культурней - тебя здесь читает много посетителей...
Во-вторых, как человек, у которого мозг начисто отформатирован Паскалем, вы всё время путаете тёплое
с мягким. Во времена арифмометра Однера (aka ФеликсЪ) других аппаратных средств для производства
вычислений не было.
И я не думаю, что инструкцию к нему писали люди, изучавшие Паскаль.
Если метод был удобен в то время для арифмометра, его и предложили использовать.

[Andnor]

Ну во-первых, я хотя бы видел этот арифмометр вживую и даже что-то считал на нём - я представляю, как это делается.

Во-вторых, для арифмометра можно использовать те же алгоритмы вычисления корня, что и вручную, просто считать при необходимости на арифмометре, а не столбиком.

Вот и попробуйте оба метода на бумаге ручкой. Посчитайте корень квадратный от какого-нибудь числа хотя бы до четырёх-пяти знаков после запятой. Увидите сами, как проще и быстрее и вопросы отпадут.
Моя формула вот: r_next:=r-(r^2-t)/2/r; r — текущая итерация корня, t — число, от которого берётся корень.

P.S. Вообще, как оказалось, она эквивалентна методу Герона. Вот ещё два варианта той же формулы:
r_next=r/2+t/2/r
r_next=(r²+t)/2/r

В общем же метод Герона - это каждый раз брать среднее арифметическое между r и t/r.

[Lavr]

Ну во-первых, я хотя бы видел этот арифмометр вживую и даже что-то считал на нём - я представляю, как это делается.

Я его не то что видел "вживую и даже что-то считал на нём", я его просто каждый день вижу,
поскольку он есть у меня на работе в качестве раритета, и работают со мной коллеги, которые
во времена своей молодости только на нём и на логарифмической линейке считали...
Поэтому я тоже не считаю зазорным уметь и то и другое. Во времена моего 1 курса в ВУЗе
линейка была еще весьма актуальна.

Во-вторых, для арифмометра можно использовать те же алгоритмы вычисления корня, что и вручную, просто считать при необходимости на арифмометре, а не столбиком.

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

Вот и попробуйте оба метода на бумаге ручкой. Посчитайте корень квадратный от какого-нибудь числа...

Я просто не представляю, зачем мне это?
Я в тематическом топике Приближённое вычисление математических функций для калькулей рассказал
об интересном методе вычисления квадратного корня, о котором, я более чем уверен, не знал никто,
в том числе и вы.
А то, что вы настырно излагаете, известно (или должно быть известно) большинству людей с техническим
высшим образованием. Никакую "терра инкогнита" вы никому не открыли...

[Andnor]

Ну хорошо, есть способ — складывать нечётные числа. Но его сложность экспоненциально растёт от количества цифр в корне. Например для нахождения одной значащей цифры нужно сложить от одного до девяти чисел, а для нахождения двух уже от 10 до 99 чисел и так далее. В то же время, алгоритм Герона очень быстро сходится. Более быстрые алгоритмы есть, но они очень специлизированные, например знаменитый алгоритм из исходников doom.

Что сумма последовательных нечётных чисел даёт полные квадраты я знал давно, это совсем не секрет, а вот применять это для вычисления квадратного корня я не догадался, да. Я и хотел уточнить насчёт практической применимости этого алгоритма. Или кто-то просто предложил его, не оценивая необходимые вычислительные ресурсы — работает и ладно?

[Shaos]

Зато красиво и нестандартно

[Andnor]

Кажется, я разобрался в том, как пользоваться методом цифра-за-цифрой.
Метод опять же основан на формуле квадрата суммы: (10x+y)²=100x²+20xy+y²=100x²+(20x+y)*y.

Вначале записывается √число, число разбивается на двойки цифр, отсчитываемые от запятой влево и вправо. Затем по первой двойке подбирается однозначное число, чтобы его квадрат был меньше, но квадрат следующего был больше. Это легко сделать зная таблицу умножения, или хотя бы её главную диагональ: 1 4 9 16 25 36 49 64 81..., ну а при её незнании можно воспользоваться суммой последовательных нечётных чисел.

Это число будет первой значащей цифрой результата. Его записывают, например, над числом. Ну или можно справа от числа, как при делении уголком.

Далее сносятся две цифры (если цифры кончились, но надо продолжать, то 00), а имеющийся результат умножается на 20 с игнорированием запятой. Например цифра 5 уже есть, значит умножаем на 20, получаем 100. У нас есть 412, но 104*4 = 416, значит берём по 3, затем целая часть результата кончается, ставится десятичная точка и процедура повторяется: 53*20=1060, берём по 9, получаем 1069*9 = 9621 и так далее, если даже 1 не подходит, то в результат добавляется ноль и сносится только одна цифра, а в следующий раз сносится уже три цифры... Вот с этим я пока не совсем разобрался.

Code: Select all

  53.9629502529...
√2912
 25
  412
  309
  10300
   9621
    67900
    64716
     318400
     215844
     10255600
      9713241
       54235900
       53962925
         272975000
         215851804
          57123196000
          53962950225
           316024577500
           215851801004
           10017277649600
            9713331045441
             30394660415900
                        ...

[b2m]

Кажется, я разобрался в том, как пользоваться методом цифра-за-цифрой.

А раньше это кажется в четвёртом классе проходили...

Между прочим, в двоичной системе подбор будет тривиальным, всего одно сравнение. Помнится, писал я реализацию такого алгоритма для нашего любимого КР580ВМ80А. Для 16-битного числа всего 8 итераций.

[Shaos]

В школе такое не давали, но помню вроде алгоритм ручного расчёта корня двойками был в каком-то советском журнале - то ли Квант, то ли ещё какой-то...

[b2m]

Может и так. У нас видимо училка по математике продвинутая была. Хотя может в 60-х - 70-х годах была такая тема на уроках арифметики. Я ещё удивлялся, что ученики того времени умели больше (без подручных средств типа калькулятора), чем мы. Я ещё таблицы Брадиса застал

[Lavr]

Ну хорошо, есть способ — складывать нечётные числа. Но его сложность экспоненциально растёт от количества цифр в корне. Например для нахождения одной значащей цифры нужно сложить от одного до девяти чисел, а для нахождения двух уже от 10 до 99 чисел и так далее. В то же время, алгоритм Герона очень быстро сходится.

Вот ещё пример покажу. Предположим, нужен корень 19619
1. Для получения первой цифры убираем по две цифры справа пока не останется одна или две: 1, убрано 4 цифры. Значит первое приближение: 100
2. По формуле квадрата суммы получаем следующее приближение: (19619 - 100²) / (2*100)+100 = 148.095.

А теперь смотрим, как на арифмометре Одонера (aka Феликсъ) выполняется деление.
Andnor пишет, что считал на нём, но, видимо, подзабыл...

деление.PNG

Алгоритм-то может и быстро сходится, но и на компьютерах, где лишь сложение и вычитание,
деление не самая быстрая операция...
А уж на арифмометре Одонера... - пусть сам Andnor делит...

Кстати говоря, метод со сложением нечетных - похоже единственный метод, не использующий деление.
На арифмометре его не зря рекомендуют! Даже думать не надо - каждое следующее число - это
счетчик оборотов х 2 + 1, и крути ручку...
Арифмометры не для того придумали, чтобы считать в уме или на бумажке...

Есть и обратный его вариант:

Метод вычетов нечётного числа (арифметический способ). Алгоритм извлечения квадратного корня: Вычитать нечётные числа по порядку, пока остаток не станет меньше следующего вычитаемого числа или равен нулю. Подсчитать количество выполненных действий – это число есть целая часть числа извлекаемого квадратного корня.
Пример 1: вычислить √9
1. 9 − 1 = 8;
2. 8 − 3 = 5;
3. 5 − 5 = 0.
Итого: Выполнено 3 действия

Формула нечётных чисел z=2n+1, где n - целое число.

[Lavr]

Кажется, я разобрался в том, как пользоваться методом цифра-за-цифрой.
Метод опять же основан на формуле квадрата суммы: (10x+y)²=100x²+20xy+y²=100x²+(20x+y)*y.
...
Вот с этим я пока не совсем разобрался.

А вы скачайте и почитайте "умну книжку - Паталогии безмозглых" (с) (щютка)

Байков.PNG

[Lavr]

Зато красиво и нестандартно

Тут ещё в тему логарифмов вот попалось, может тебе будет интересно:

эксп.PNG