Приближённые вычисления арктангенса в MIDP 2.0

Как известно, объект java.lang.Math в MIDP 2.0 лишён функции atan(), как впрочем и многих других обратных тригонометрических функций. Однако арктангенс практически незаменим при вычислении значений углов прямоугольного треугольника по известным длинам его катетов. Ниже представлена одна из возможных реализаций функции арктангенса, дающая вполне хорошие результаты для аргументов в самом широком диапазоне. Следует лишь напомнить, что данная функция принимает в качестве аргумента величину отношения противолежащего катета прямоугольного треугольника к прилежащему, и возвращает значение соответствующего угла в радианах.

    // Константы, необходимые для вычисления арктангенса
    private static final double tanPI12 = Math.tan(Math.PI/12);
    private static final double tanPI6 = Math.tan(Math.PI/6);
    private static final double PI6 = Math.PI/6;
    private static final double PI2 = Math.PI/2;

    private static final double c1 = 1.6867629106;
    private static final double c2 = 0.4378497304;
    private static final double c3 = 1.6867633134;

    /**
     * Функция приближённого вычисления арктангенса.
     *
     * @param a Отношение противолежащего катета прямоугольного треугольника к прилежащему
     * @return Значение соответствующего угла в радианах
     */
    public static double atan(double a)
    {
        double result = 0;

        boolean complement = false; // Принимает значение true если аргумент "a" больше 1.0
        boolean region = false; // Принимает значение true если аргумент "a" больше значения Math.tan(Math.PI/12)
        boolean sign = false; // Принимает значение true если аргумент "a" отрицательный

        if (a < 0)
        {
            a = -a;      // Дать аргументу "а" позитивное значение
            sign = true; // Дать результату негативное значение
        }

        if (a > 1.0)
        {
            a = 1.0 / a; // Преобразовать аргумент "а" в значение от 0 до 1.0
            complement = true;
        }

        if (a > tanPI12)
        {
            a = (a - tanPI6) / (1 + tanPI6 * a); // Ограничить аргумент "а" значениями от 0 до Math.tan(Math.PI/12)
            region = true;
        }

        // Вычислить приблизительное значение арктангенса для значения "а" в диапазоне от 0 до Math.PI/12
        result = a * (c1 + a * a * c2) / (a * a + c3);

        if (region)
        {
            result += PI6; // Поправить значение угла, так как аргумент имел значение больше Math.tan(Math.PI/12)
        }

        if (complement)
        {
            result = PI2 - result; // Поправить значение угла, так как аргумент имел значение больше 1.0
        }

        if (sign)
        {
            result =- result; // Поправить значение угла, так как аргумент был негативным
        }

        return result;
    } 

Решение задач в "Пректе Эйлера"

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

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

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


Картинка всем на зависть.

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

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

Проект Эйлера

Возможно, что все чёкнутые программисты уже в курсе, но я вчера открыл для себя весьма интересный "Проект Эйлера". Суть такова: вам, (чёкнутому программисту), предлагается решить более трёхсот математических задач при помощи программирования и имеющихся в вашем распоряжении среднестатистических вычислительных мощностей.

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

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

Следует отметить, что часть вопросов была переведена энтузиастами на русский язык, и выложена на сайте euler.jakumo.org.

Тех же программистов, кто хочет отдохнуть от программирования, и кого больше интересуют математические задачи, возможно заинтересует ресурс MathsChallenge.Net, от которого, в своё время и отделился "Проект Эйлера".

За сим, как говорится, кланяюсь и желаю удачи в нелёгком деле усиления собственных творческих, мыслительных и вычислительных способностей.

Приближенные значения числа Пи

Сегодня я, по случаю пятницы, решил усомниться в правдивости открытий древних математиков, и решил перепроверить: так ли уж были хороши рациональные дроби, найденные древними для нахождения приблизительного значения числа Пи?

Таких рациональных дробей известно предостаточно. Взять хотя бы вычисления Архимеда. Древний мудрец вычислил, что число Пи больше 223 / 71 и меньше 22 / 7. Древние вавилоняне считали, что число Пи примерно равно 25 / 8. Древние египтяне представили свои варианты дробей: 22 / 7 и 256 / 81. Индийский гений Рамануджан, живший в начале прошлого века, определил число Пи как дробь 355 / 113.

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

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double constantPi = 3.1415926535897932384626433832795028841971693993751;
    double calculatedPi;
    double minPi = 3.14149; // Нижняя граница точности наших вычислений.
    double maxPi = 3.14160; // Верхняя граница точности наших вычислений.

    cout.precision(50); // Выжмем из потока вывода все возможное и невозможное!

    cout << "Constant Pi = " << constantPi << "\n" << endl; // Образец для подражания.

    // Вычислим в пределах тысячи все подходящие числители и знаменатели.

    for (int i = 2; i <= 1000; i++)
    {
        for (int j = 2; j <= 1000; j++)
        {
            calculatedPi = (double) j / i;

            if (calculatedPi <= maxPi && calculatedPi >= minPi)
            {
                cout << j << " / " << i << " = " << calculatedPi << endl;
                cout << "Constant - Calculated = " << constantPi - calculatedPi << "\n" << endl;
            }
        }
    }

    return 0;
}

В результате работы этой замечательной программы я получил следующие результаты:

Constant Pi = 3.141592653589793115997963468544185161590576171875

333 / 106 = 3.1415094339622640084996874065836891531944274902344
Constant - Calculated = 8.3219627529107498276061960496008396148681640625e-005

355 / 113 = 3.141592920353982520964564173482358455657958984375
Constant - Calculated = -2.667641894049666007049381732940673828125e-007

666 / 212 = 3.1415094339622640084996874065836891531944274902344
Constant - Calculated = 8.3219627529107498276061960496008396148681640625e-005

688 / 219 = 3.1415525114155249397640545794274657964706420898438
Constant - Calculated = 4.014217426817623390888911671936511993408203125e-005

710 / 226 = 3.141592920353982520964564173482358455657958984375
Constant - Calculated = -2.667641894049666007049381732940673828125e-007

999 / 318 = 3.1415094339622640084996874065836891531944274902344
Constant - Calculated = 8.3219627529107498276061960496008396148681640625e-005

И что же мы получаем? А получаем мы шесть замечательных дробей, которые каждый из нас теперь может взять в качестве приближенного значения числа Пи. При этом дроби 333 / 106, 666 / 212 и 999 / 318 по вполне понятным законам арифметики и квантовой механики дают один и тот же результат. То же самое касается и дробей 355 / 113 и 710 / 226.

Однако дробь 355 / 113 дает наилучший результат, лучше остальных приближая нас к заветному значению числа Пи. Стоит ли лишний раз говорить, что эту дробь открыл гениальный индус Рамануджан, проживший столь недолгую и трагичную жизнь?

А как же, вы скажете, быть с открытиями древних вавилонян, египтян, Архимеда, и всех остальных, неравнодушных к математике? Очень просто. Нужно всего лишь изменить критерии точности наших вычислений. Уверяю вас, что изменяя переменные minPi и maxPi мы легко сможем получить все те замечательные результаты, что уже знаем о приблизительных значениях числа Пи. А может быть, - кто знает? - вы откроете свою, неизвестную науке замечательную дробь, приближающую нас к значению числа Пи.

Компиляция библиотеки GMP под Windows при помощи MinGW

Библиотека GMP, или GNU Multi-Precision Library используется во многих программах, так или иначе связанных с точными вычислениями. Библиотека GMP содержит множество алгоритмов и функций, благодаря которым вы можете выполнять в своих программах основные математические операции с заданной точностью. К примеру, расчитать число π до десятитысячного знака. Так как код GMP написан на Си и ассемблере, компиляцию библиотеки приходится осуществлять вручную под конкретную платформу и используемый вами процессор.

Если вы работаете в Линуксе или на Юниксе, то проблем с компиляцией библиотеки GMP у вас практически не возникает. Инструменты компиляции и сборки GMP изначально ориентируются на Unix-подобные системы. Однако если вы работаете в Windows, то можете столкнуться с некоторыми сложностями. Ниже я привожу вариант компиляции данной библиотеки при помощи инструментов MinGW и MSYS. Справедливости ради стоит отметить, что сборку библиотеки GMP можно так же осуществить при помощи среды Cygwin, однако я предпочитаю использовать MSYS, которая после настройки позволяет легко компилировать в Windows многие библиотеки и проекты, созданные под Unix-подобные системы. Итак:

I. Настройка Windows для компиляции GMP

1. Cначала необходимо установить MinGW. Устанавливать MinGW лучше всего в папку C:\MinGW, так как в последствии у вас будет меньше проблем с настройкой других инструментов.

2. После установки MinGW, необходимо установить набор утилит MSYS. Устанавливать MSYS лучше всего в его папку "по умолчанию", то есть в C:\msys\1.0. При установке MSYS будет производиться дополнительная конфигурация, во время которой вас попросят указать местоположение MinGW (папка C:\MinGW в нашем случае).

3. Помимо MSYS-а вам так же понадобятся его дополнительные модули: MSYS DTK 1.0, MSYS flex, MSYS regex и MSYS bison. Все указанные библиотеки и модули вы распаковываете и просто копируете в папку C:\msys\1.0, где образуется ваша Unix-подобная среда. Хотя установка MSYS-а выглядит сложной, на самом деле никаких сложностей с установкой нет, а в итоге вы получаете очень удобную среду для компиляции библиотек и программ из Unix-подобных систем на машине с Windows.

4. После успешной установки MSYS-а, внутри папки C:\msys\1.0\home у вас должна появиться соответствующая домашняя директория пользователя. Вы можете переименовать эту домашнюю пользовательскую директорию в любое другое, удобное для вас имя. Я для удобства переименовал ее в username. Если вы не хотите ничего переименовывать, то в нижеприведенных командах используйте вместо username имя вашей домашней директории.

5. Теперь нужно скачать библиотеку GMP, и распаковать её в вашу домашнюю пользовательскую директорию, то есть в папку C:\msys\1.0\home\username.

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

II. Компиляция библиотеки GMP под Си

1. Откройте папку C:\msys\1.0, и запустите MSYS при помощи файла msys.bat. После запуска убедитесь, что вы находитесь внутри своей домашней директории username.

2. Введите команду mkdir gmp. В эту папку будут помещаться скомпилированные модули библиотеки GMP, а так же её заголовочный файл.

3. Перейдите в папку с библиотекой GMP при помощи команды cd gmp-x.x.x

4. Введите команду ./configure --prefix=/home/username/gmp

5. После окончания конфигурации, введите команду make

6. Теперь, когда библиотека GMP скомпилирована, можно запустить её тестирование при помощи команды make check

7. Очистите компиляцию от ненужных файлов при помощи команды make clean

8. Теперь, когда конфигураци, компиляция, тестирование и очистка библиотеки GMP успешно завершены, скопируйте модули libgmp.a и libgmp.la из папки C:\msys\1.0\home\username\gmp\lib в папку C:\MinGW\lib, а заголовочный файл gmp.h из папки C:\msys\1.0\home\username\gmp\include - в папку C:\MinGW\include. Так же можно скопировать содержимое папки C:\msys\1.0\home\username\gmp\share\info в папку C:\MinGW\share\info.

Теперь ваша среда MinGW получила полноценную библиотеку GMP. Следует отметить, что получившиеся модули и заголовочный файл предназначены для использования в Си-программах. Конечно, никто не запрещает использование Си-библиотек внутри программ, написанных на Си++, однакое если вы хотите явно получить библиотеку для Си++, то на шаге №4 вам следует ввести команду ./configure --prefix=/home/username/gmp --enable-cxx, а все остальное - выполнить точно так же, как и в случае с библиотекой для Си. Единственное, что будет другим - это имена скомпилированных модулей и полученного заголовочного файла. В случае с библиотекой для Си++, они будут соответственно libgmpxx.a, libgmpxx.la и gmpxx.h.

Стивен Фольфрам рассказывает о вычислимости природы

Очень интересная презентация от создателя "Математики" - Стивена Фольфрама. В этот раз Фольфрам рассказывает как о "вычислении на основе знаний", так и о фундаментальной "вычислимости природы":