Новая статья

Введение
Историческая справка
Пифаго;рова тро;йка — упорядоченный набор из трёх натуральных чисел удовлетворяющих следующему однородному квадратному уравнению:
x^2+y^2=z^2

Наиболее известной в развитых древних культурах была тройка (3, 4, 5), которая позволяла древним строить прямые углы. Витрувий считал эту тройку высшим достижением математики, а Платон — символом супружества, что говорит о большом значении, которое придавали древние тройке (3, 4, 5).
В архитектуре древнемесопотамских надгробий встречается равнобедренный треугольник, составленный из двух прямоугольных со сторонами 9, 12 и 15 локтей. Пирамиды фараона Снофру (XXVII век до н. э.) построены с использованием треугольников со сторонами 20, 21 и 29, а также 18, 24 и 30 десятков египетских локтей.
Вавилонские математики умели вычислять пифагоровы тройки. Вавилонская глиняная табличка, названная Plimpton 322, содержит пятнадцать пифагоровых троек (точнее пятнадцать пар чисел (a, b, c), таких что a^2+b^2=c^2). Считается, что эта табличка была создана около 1800 года до н. э.
Идея написания статьи родилась при составлении программы для вычисления мощности (количества членов множества) решений уравнения пифагоровых троек на компьютере. Первая версия программы была достаточно ограниченной из-за неразвитой математики больших чисел. Исходники первой программы были написаны на языке программирования Паскаль. Наиболее большой по мощности тип в языке был тип longint, что соответствовало типу long int в с (2 147 483 647). Запуск программы на персональном компьютере быстро упирался в ограничения типа. После чего было принято решение написания программы на языке программирования c. По причине большей свободы работы с памятью у последнего языка. Прошло более 15 лет, алгоритмы работы с большими числами совершенствовались. В последствии, появился тип данных int64_t, максимальное значение которого равно 264-1=18 446 744 073 709 551 615. В связи с чем, задача можно сказать обрела новый смысл.

Актуальность задачи
В связи с быстрым развитием портативных компьютеров у обычных пользователей сети, возникает вопрос о доступности математических вычислений большого объема. Данная статья делает обзор возможностей существующего языка программирования «c», и возможные пути для обхода ограничений связанных с максимальными значениями типов.

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

Методическая часть
Логика задачи следующая: есть уравнение пифагоровых троек
x^2+y^2=z^2
Которое имеет простое решение, выражающееся путем введения двух новых переменных.
x = 2*i*j;
y = i*i-j*j;
z = i*i+j*j;
Теория математики предсказывает, что число таких решений бесконечно.
Теперь опустимся, так скажем, на Землю. Реально никто не проверял, действительно ли
все правила математики выполняются для всех значений i,j. В теории это выполняется. Но как дела обстоят на практике, остается под вопросом.
Вручную проверку произвести нереально. Поэтому единственная возможность - поручить проверку компьютеру. Задать ему задачу, и пусть себе решает пока не столкнется с ограничениями.
Введенный тип данных int64_t работает от - 9 223 372 036 854 775 807 до
+9 223 372 036 854 775 807. Что вполне годится для нашей работы.

Согласно введенному типу в программе, ориентировочное время выполнения 1-2 месяца при полной загрузке процессора.


Текст программы следующий:

#include <stdio.h>
#include <inttypes.h>
#include <unistd.h>

int main()
{
int64_t x, y, z, i, j, i0, j0;
long int counter=0;//добавим счетчик треугольников пифагора
FILE *f;
char str[1024];
//прочитаем последнюю запись лога, чтобы не считать все заново при перезапуске
f = fopen("log.txt", "r");
while(fgets(str, 1024, f)){
sscanf(str, "x:%"PRIu64" y:%"PRIu64" z:%"PRIu64" i:%"PRIu64" j:%"PRIu64"\n", &x, &y, &z, &i, &j);
}
i0 = i;
j0 = j+1;//выбираем следующий треугольник
printf(" \n", i0, j0);
//return 1;

for(i=i0;i>0;i++)//не будем ограничивать сверху цикл,
{ //оставим только проверку на переполнение
for(j=j0;j<i && j>0;j++)//проверка на переполнение
{
x = 2*i*j;
y = i*i-j*j;
z = i*i+j*j;
if(x*x+y*y!=z*z || x*x<0 || y*y<0 || z*z<0 || x<0 || y<0 || z<0)
{//включаем проверку переполнения
printf("ошибка в вычислениях\n");printf("error in math\n");
//выведем текущие значения и выбросим ошибку
printf("x:%"PRIu64" y:%"PRIu64" z:%"PRIu64" i:%"PRIu64" j:%"PRIu64"\n", x, y, z, i, j);
return 1;
}
counter++;//инкрементируем счетчик
if((counter % 1000000000)==0){
//на 1 миллиард выбрасываем текущее значение и обнуляем счетчик
printf("x:%"PRIu64" y:%"PRIu64" z:%"PRIu64" i:%"PRIu64" j:%"PRIu64"\n", x, y, z, i, j);
//запишем значение в лог-файл
FILE *f;
f = fopen("log.txt", "a");
fprintf(f, "x:%"PRIu64" y:%"PRIu64" z:%"PRIu64" i:%"PRIu64" j:%"PRIu64"\n", x, y, z, i, j);
fclose(f);
counter=0;
}
//usleep(5);//дадим отдохнуть процессору 5 миллисекунд
}
j0 = 1;
}
return 0;
}


Результаты.
Разработана программа, в которой рассмотрен алгоритм расчета пифагоровских троек. По результатам запуска и отработки программ получены следующие результаты:
Рассмотрен диапазон значений (i, j) работы программы, при которых не обнаруживается ошибок в работе компьютера. Проведение эксперимента еще на закончено, но уже получено следующее:
начиная от (2, 1) до (38 969, 38 967) работа алгоритма не обнаруживала ошибок в вычислениях. Дальнейшая работа программы приводит к появлению сообщения об ошибке в расчетах на шаге i:38969 j:38967. Это означает, что 64 битов для вычислений мало. В качестве решения данной проблемы предлагаю разделить задачу на два этапа:
1. калькуляция набора треугольников пифагора и запись их в файлы.
2. Для первоначальной работы предлагаю записывать не все подряд тройки, а с каким-то интервалом, скажем те же 1 миллиард троек, что используются в написанной программе в качестве реперных точек. При обнаружении неполадок или сбоев, можно рассмотреть диапазон пошагово.
После подготовки пачки файлов, следующая программа будет обрабатывать тройки на предмет корректности.

Заключение
Как видите, прогресс сферы информационных технологий не стоит на месте: был введен новый тип данных int64_t. Но к сожалению даже такое простое уравнение как пифагоровы тройки быстро сталкиваются с физическими ограничениями компьютера. Надеюсь, данная статья подтолкнет следующее поколение физиков и математиков к дальнейшему развитию методов.


Список литературы
1. Длинная арифметика в c++. http://cppstudio.com/post/5036/


Рецензии