РАСШИРЕНИЕ МОЩНОСТИ УРАВНЕНИЯ ПИФАГОРОВЫХ ТРОЕК

АННОТАЦИЯ

В предыдущей статье «Исследование мощности уравнения Пифагоровых троек»[1] мы сформулировали задачу для исследования. В настоящей статье рассмотрим модификацию программы для вычислений и проведем анализ уравнения для нового случая.

ABSTRACT

In the previous article “Investigation of the power of the Pythagorean triples equation” [1], we formulated the problem for the study. In this article, we consider a modification of the program for calculations and analyze the equation for a new case.

Ключевые слова: пифагоровы тройки, мощность, теория чисел.

Keywords: pythagorean triples, cardinality, number theory.

В предыдущей статье «Исследование мощности уравнения Пифагоровых троек»[1] мы сформулировали задачу для исследования. В настоящей статье рассмотрим модификацию программы для вычислений и проведем анализ уравнения для нового случая.

В предыдущем случае местом вызывающем переполнение типа int64_t были значения x*x, y*y, z*z при проведении проверки корректности решений.

Перепишем процесс проверки решений таким образом: допустим, нам известны числа x, y и z. Получим из них искомые числа i и j. Заметим, что мы можем сделать это двумя разными способами.

1) i1 = sqrt((z+y)/2)

    j1 = sqrt((z-y)/2)

2) i2 = (sqrt(z-x)+sqrt(z+x))/2

    j2 = (sqrt(z+x)-sqrt(z-x))/2

В таком методе вычисления, мы не превышаем величину в 2⁶³ [2].

Перепишем программу и проанализируем результаты вычислений:

#include <stdio.h>

#include <inttypes.h>

#include <unistd.h>

#include <math.h>

int check(int64_t x, int64_t y, int64_t z, int show){

double i1, j1, i2, j2;

i1 = sqrt((z+y)/2);

j1 = sqrt((z-y)/2);

i2 = (sqrt(z-x)+sqrt(z+x))/2;

j2 = (sqrt(z+x)-sqrt(z-x))/2;

if(show) printf(" %"PRIu64" %"PRIu64" %"PRIu64" %"PRIu64"\n", i1, i2, j1, j2);

return (i1!=i2 || j1!=j2) ? 0:1;

}

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*/!check(x, y, 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 ~ 2³¹ [4].

Если оценить время на вычисление всех треугольников для новой программы, в годах, то получится примерно 2*10⁹ сек ~ 100 лет.

Оценка ограничения мощности решений уравнения Пифагоровых троек.

Теоретическая - на основе уравнения: z= i²+j² и возможного максимального значения z = 2⁶³.

Получены значения i=2 147 483 647.

И экспериментального, методом подбора значений i и j, при которых происходит сообщение об ошибке.

Получены значения i=1 518 500 251, j=1 518 500 249

Необходимо отметить, что экспериментально получено минимальное значение, при котором происходит переполнение.

Вычислим мощность уравнения Пифагора для экспериментального значения:

Количество решения для каждого шага i равно N_i=i*(i-1)

Если просуммировать все N_i, то получим интеграл:

i³/3-i²/2, где i от 2 до экспериментального значения.

Подставив пределы в формулу, получим число примерно ~10²⁷.

Таким образом, мощность последней программы на вычисления троек 10²⁷

Сравним полученную мощность со значением из статьи: [1]

i = 38 969

Мощность ~ 10¹²

Таким образом, для модифицированной программы мы получили выигрыш в 10¹⁵ раз.

Список литературы:

1. Тихомиров Е.П., Васильев А.В. “ИЗУЧЕНИЕ МОЩНОСТИ УРАВНЕНИЯ ПИФАГОРОВЫХ ТРОЕК”, СТУДЕНЧЕСКИЙ, 2021, № 1-2(129), 11-14
2. Длинная арифметика в c++. http://cppstudio.com/post/5036/
3. Пифагоровы тройки чисел. Выписка из свободной энциклопедии «Википедия» от 26.10.2016.
4. Выгодский М. Я. Справочник по элементарной математике. Москва, 2006. С. 509