Кіру немесе тіркелу

статья


Введение
Идея написания статьи родилась при составлении программы для вычисления мощности (количества членов множества) решений уравнения пифагоровых троек на компьютере. Первая версия программы была достаточно ограниченной из-за неразвитой математики больших чисел. Исходники первой программы были написаны на языке программирования Паскаль. Наиболее большой по мощности тип в языке был тип longint, что соответствовало типу long int в с (2 147 483 647). Запуск программы на персональном компьютере быстро упирался в ограничения типа. После чего было принято решение написания программы на языке программирования c. По причине большей свободы работы с памятью у последнего языка. Прошло более 15 лет, алгоритмы работы с большими числами совершенствовались. В последствии, появился тип данных int64_t, максимальное значение которого равно 264-1=18 446 744 073 709 551 615. В связи с чем, задача можно сказать обрела новый смысл.


Методическая часть
Логика задачи следующая: есть уравнение пифагоровых троек
x^2+y^2=z^2
Которое имеет простое решение, выражающееся путем введения двух новых переменных.
x = 2*i*j;
y = i*i-j*j;
z = i*i+j*j;
Теория математики предсказывает, что число таких решений бесконечно.
Теперь опустимся, так скажем, на Землю. Реально никто не проверял, действительно ли
все правила математики выполняются для всех значений i,j. В теории это выполняется. Но как дела обстоят на практике, остается под вопросом.
Вручную проверку произвести нереально. Поэтому единственная возможность — поручить проверку компьютеру. Задать ему задачу, и пусть себе решает пока не столкнется с ограничениями.
Введенный тип данных uin64_t работает от — 18 446 744 073 709 551 615 до
+18 446 744 073 709 551 615. Что вполне годится для нашей работы.

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


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

#include
#include
#include

int main()
{
uint64_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;j0;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) до (2 359 000, 1) работа алгоритма не обнаруживала ошибок в вычислениях.

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


  • Бөлісу

Тәріздес шығармалар