Математические алгоритмы

[Ramzai]

Кто-нить знает алгоритмы sqrt, корень произвольной степени, sin, cos...

[Sirik]

Алгоритм извлечения корня квадратного

Рассмотрим на примере sqrt(273529).
Для нахождения произведем следующие действия:
1) десятичную запись числа 273529 разобьем на группы по две цифры, начиная справа;
2) для старшей группы, образующей число 27, подберем такую цифру, чтобы ее квадрат был наибольшим, но не превосходил числа 27; такой цифрой будет 5, ее запишем в качестве первой цифры ответа;
3) из старшей группы цифр вычтем найденный в предыдущем пункте квадрат первой цифры ответа и к полученной разности 27 – 25 = 2 припишем справа следующую группу цифр 35; получим число 235;
4) удвоив записанное в ответе число 5, припишем справа такую цифру , чтобы произведение полученного в результате числа на эту цифру было наибольшим, но не превосходило числа 235; такой цифрой будет 2 (ибо 102 x 2 = 204 < 235, но 103 x 3 = 309 > 235), ее и запишем в качестве второй цифры ответа;
5) из числа 235 вычтем найденное в предыдущем пункте произведение 204 и к остатку 31 снесем следующую группу цифр 29; получим число 3129;
6) удвоив записанное в ответе число 52, припишем справа такую цифру, чтобы произведение полученного в результате числа на эту цифру было наибольшим, но не превосходило числа 3129; такой цифрой будет 3 (ибо 1043 x 3 = 3129), ее и запишем в качестве третьей цифры ответа;
7) разность между снесенным числом 3129 и полученным в предыдущем пункте произведением равна 0, поэтому корень квадратный из числа 273529 извлекается нацело и равен записанному в ответе числу 523.

Расчёт sin(x)
Общий вид такой sin (x) = x - x^3/3! + x^5/5! - x^7/7! + ....
Организуй цикл и проверяй знак точности до требуемого.

На счёт остальных не помню...

[Ramzai]

2Sirik: Спасибо! Вся тригонометрия есть...

1. т.е. sin(x) = (-1)^n * (x^(2n-1)) / (2n-1)!
2. корень произвольной степени...

[Sirik]

Кубический корень. Для извлечения кубического корня из положительного действительного числа существуют алгоритмы, аналогичные алгоритмам извлечения квадратного корня. Например, чтобы найти кубический корень из числа n, сначала мы аппроксимируем корень некоторым числом r1. Затем строим более точное приближение r2 = (1/3)(2r1 + n/r12), которое в свою очередь уступает место еще более точному приближению r3 = (1/3)(2r2 + n/r22) и т.д. Процедура построения все более точных приближений корня может продолжаться сколь угодно долго.
Рассмотрим, например, вычисление кубического корня из числа, заключенного между 1 и 1000, скажем, числа 200. Так как 53 = 125 и 63 = 216, мы заключаем, что 6 – ближайшее к кубическому корню из 200 целое число. Следовательно, выбираем r1 = 6 и последовательно вычисляем r2 = 5,9, r3 = 5,85, r4 = 5,8480. В каждом приближении, начиная с третьего, разрешается удерживать число знаков, которое на единицу меньше удвоенного числа знаков в предыдущем приближении. Если же число, из которого требуется извлечь кубический корень, не заключено между 1 и 1000, то предварительно его необходимо разделить (или умножить) на некоторую, скажем, k-ю, степень числа 1000 и тем самым привести в нужный интервал чисел. Кубический корень из вновь полученного числа лежит в интервале от 1 до 10. После того, как он будет вычислен, его необходимо умножить (или разделить) на 10k , чтобы получить кубический корень из исходного числа.
Второй, более сложный, алгоритм нахождения кубического корня из положительного действительного числа основан на использовании алгебраического тождества (a + b)3 = a3 + (3a2 + 3ab + b2)b. В настоящее время алгоритмы извлечения кубических корней, равно как и корней более высоких степеней, в средней школе не изучают, так как их легче находить с помощью логарифмов или алгебраическими методами.

И еще вот что-то:
В последние годы вычислители демонстрируют извлечение корней больших степеней, и успехи в данном виде заинтересовали Книгу Рекордов Гиннесса. В 11 издании (1972 стр. 43) было сообщено, что 5 Октября 1970 года, Герберт Б. дэ Грот из Мехико извлек в уме корень 13-й степени из 100-значного числа за 23 минуты.
С тех пор извлечение корней высоких степеней стало чрезвычайно популярно, без сомнения благодаря доступности компьютеров, как для производства данных с которыми вычислители могут создать алгоритмы так и для предоставления самих заданий для выступлений.
В 16-м издании (1977), был представлен рекорд Вима Клейна из Нидерландов, который извлек корень 23-й степени из 200-значного числа за 10.5 минут. В издании 1978 года сообщено что Клейн извлек корень 73-степени из 500-значного числа за 2 минуты 43 секунды.
Трудности с извлечением точных корней мало зависят от величины степени. Гораздо более важно количество цифр в ответе и конкретные особенности выбранных степеней (отметим, что ни в одном из случаев не использовались четные степени). Митчелл (1907, стр. 94) замечает: "в основном, большие степени облегчают проблему, и квадратные или кубические корни наиболее часто используются." В этом отношении времена изменились.
Книга Рекордов Гиннеса сейчас считает корень 13-й степени из 100-значного числа как стандартный тест возможностей по извлечению точных корней. Вим Клейн держит рекорд в этом упражнении со временем менее чем две минуты. Клейн комментирует: "Проблема тем сложнее, чем больше цифр в ответе. Корень 23-й степени из 200-значного числа имеет девять цифр в результате, и это столько же, сколько корень седьмой степени из 63-значного числа. Корень 13-й степени из 100 цифр имеет 8 знаков, а корень 19-й степени из 133 цифр и 73-й степени из 500 цифр имеют только семь знаков. Я не вижу дальнейшего интереса в семизначных ответах. Для меня сейчас это просто игра."
"С восьмью знаками, одна цифра сложно распознаваема, и это требует использования специальных тестов. С девятью знаками уже две неизвестных в середине, что делает работу значительно более жесткой. Кубический корень из 30 цифр дает десять знаков - и это просто адова работа."
Метод Клейна по извлечению корня 13-й степени может быть проиллюстрирован на следующем числе:

14762420839370760705665953772022217870318956930659
27236796230563061507768203333609354957218480390144

Первые пять знаков корня находятся с помощью логарифмов. Клейн помнит до пятого знака логарифмы всех натуральных чисел до 150, что в паре с его способностью разлагать на множители большие числа позволяет ему аппроксимировать логарифмы первых пяти знаков степени, что обычно достаточно для определения первых пяти цифр корня, хотя, как он сам замечает "пятая цифра немного рискованная."
Клейн начинает с разложения 1476 на произведение 36 на 41 и использования логарифма (десятичного) каждого из них: log(36)=1.55630, а log(41)=1.61278; суммирование мантисс дает 0.16908, но этого, конечно, мало. Используя различные интерполяции Клейн выясняет, что мантисса логарифма числа 147624 равна 0.16925 (это почти 0.16916).

Таким образом Клейн получает приближение логарифма 100-значного числа полностью - 99.16925. Это число должно быть разделено на 13 для получения логарифма ответа. Поскольку 99=13X7 с остатком 8, чтобы получить мантиссу антилогарифма 13-го корня он делит 8.16925 на 13, что приблизительно дает 0.62840. Оценив антилогарифм как половину между 4.2 и 4.3 он решил попробовать 4.25. Результат был точен, и получилось, что первые пять цифр корня должны быть 42500, как и оказалось на самом беле.

Теперь необходимо определить последние три цифры корня. Это он делает исследуя последние три цифры степени. В случае с нечетным числом, они однозначно определяют последние три цифры корня, но в случае четных корней, как здесь, этот метод предлагает четыре возможности; в случае с 144 возможны ответы 014, 264, 514 и 764. (Они всегда отличаются друг от друга на 250) Для выбора правильного варианта Клейн делит исходное число на 13 и запоминает остаток. В случае с 13-й степенью, остаток корня и степени должны быть одинаковыми. Остаток степени 7; только 764 как окончание корня дает в остатке 7. Таким образом искомый корень 13-й степени определяется как 42.500.764.

Как вариант нечетного числа возьмем:

75185285487713563581947553291145079861723813162341
53935861550997297991815299022662358976308065985831


Первые пять цифр степени 75185, что близко к 7519, а 7519 можно представить как 73 на 103. Мантисса логарифма 73 равна 0.86332, а 103 - 0.01284. Их сумма 0.87616. Деление 8.87616 на 13 дает 0.68278. Это расположено между мантиссой логарифмов 48 и 49, но гораздо ближе к 48. Поскольку 481 это 13 (мантисса 0.11394) на 37 (мантисса 0.56820), мантисса их логарифмов будет 0.68214; сделано но слишком приближенно; 4816 может быть разложено на 16 (мантисса 0.20412) помноженное на 7 (мантисса 0.84510) и на 43 (мантисса 0.63347). Это дает мантиссу 0.68269. 4818 раскладывается на 66 (мантисса 0.81954) умноженное на 73 (мантисса 0.86332), что дает мантиссу 0.68286. Таким образом, интерполируя мы хотим получить 9/17 от 20, что приблизительно 10½. Первые пять цифр корня должны быть 48170 (48160 + 10). И действительно это так.

Когда Клейн действительно делал вычисления то сделал небольшую ошибку (он искал антилогарифм 0.68277 вместо 0.68278) и сначала взял 48169 для первых пяти цифр корня. В этом случае, однако, раз корень нечетный, последние три цифры имеют уникальное соответствие и поскольку степень оканчивается на 831, корень должен оканчиваться на 311. При делении степени на 13 Клейн получает остаток 7. Но деление 48169311 на 13 дает остаток 8. Для приведения обоих остатков в соответствие он меняет результат на 48170311, что является правильным ответом.

А вобще-то можешь зайти на http://www.ya.ru там и ищи

[Faust]

http://algolist.manual.ru/ - раздел Математика.

[Ramzai]

Огромное спасибо всем, тема закрыта