Оптимизация программы генератора троек

[Alek]

Не нашёл адекватного способа в паскале абс нет – для операций только с натуральными числами.
В «самодельном» варианте, пришлось выкручиваться посредством frac.

Ещё: генератор считает, применяя все подряд коэффициенты, тогда ограничил вывод результатов, но программа всё так же пересчитывает балластные значения, хоть их не видно, что в случае счёта больших величин, возможно помешает.

Есть ли идеи оптимизации?

program WHILE_IF_Pythagorean_Triples_1;

var x, k: integer; 
    y, z: real;

begin
  writeln('For x² + y² = z² – Enter X:');
    readln(x); 
      k:=0;

while k <= sqr(x)/k do
  begin
    k := k + 1;
      if k <> 0 then
        y := (sqr(x)/k - k)/2; z := y + k;

if y <> 0 then 
  if frac(y) = 0 then 
      println('Pythagorean Triple:',x,y,z);

end;
    end.

[wrest]

Alek в сообщении #1594046 писал(а):

while k <= sqr(x)/k do

Это эквивалентно

while k <= x do

Но чтобы потом не проверять что y не равно нулю, можно сразу делать условие

while k < x do

Это лишнее

Alek в сообщении #1594046 писал(а):

if k <> 0 then

Поскольку k всегда не равно нулю.

Это

Alek в сообщении #1594046 писал(а):

z := y + k;

Я бы перенёс после

Alek в сообщении #1594046 писал(а):

if frac(y) = 0 then

Поскольку нет смысла вычислять z если y не подходит.

С точки зрения исключения неподходящих k не смотрел, т.к. не очень ясна сама задача.

Программа на PARI/GP которая делает то же вычисление
Alek_Triples(x)=for(k=1,x-1,y=(x^2-k^2)/(2*k);if(denominator(y)==1,print("x=",x," y=",y," z=",y+k," k=",k)))

На вход подаём x, работает так:
? Alek_Triples(15)
x=15 y=112 z=113 k=1
x=15 y=36 z=39 k=3
x=15 y=20 z=25 k=5
x=15 y=8 z=17 k=9
?

[Dmitriy40]

Alek
Зачем что-то здесь оптимизировать если цикл в любом случае перебирает не более 46341 значений k, что точно быстрее секунды (а скорее всего единицы миллисекунд)?

Alek в сообщении #1594046 писал(а):

Не нашёл адекватного способа в паскале абс нет – для операций только с натуральными числами.

Всё есть: заменяйте / на div, frac на mod (разумеется от других аргументов).

[wrest]

Чётность x и k совпадает, так что можно
Вместо

begin
  writeln('For x² + y² = z² – Enter X:');
    readln(x);
      k:=0;

Писать

begin
  writeln('For x² + y² = z² – Enter X:');
    readln(x);
      k:= x mod 2;
      if k=1 then k=-1;

И далее вместо

while k <= sqr(x)/k do
  begin
    k := k + 1;

писать

while k < x do
  begin
    k := k + 2;

Это сократит перебор в 2 раза.

Для простых x будет только одна тройка, при k=1.

Ну и ясно что перебор сокращается в зависимости от факторизации x но сходу неясно как.

[Alek]

wrest в сообщении #1594062 писал(а):

Alek в сообщении #1594046 писал(а):

Цитата:

while k < x do

Переделал вайл, и убрал

Цитата:

if k <> 0 then

всё работает, благодарю))

Но:

Цитата:

z := y + k; Я бы перенёс после if frac(y) = 0 then

А кода переставил зет, тогда фрак не смог больше рарешать значения только с нулевой дробной частью, и прога на х=3, выдала кроме тройки, лишнюю хрень:

Pythagorean Triple: 3 4 5
Pythagorean Triple: 3 1.25 5
Pythagorean Triple: 3 0 3
Pythagorean Triple: 3 -0.875 3

Так как стала показывать вообще все результаты делений, со всеми коэффициентами, это ответ на ваш вопрос ниже:

Цитата:

С точки зрения исключения неподходящих k не смотрел, т.к. не очень ясна сама задача.

-- 16.05.2023, 19:18 --

Dmitriy40 в сообщении #1594065 писал(а):

Alek
Зачем что-то здесь оптимизировать если цикл в любом случае перебирает не более 46341 значений k, что точно быстрее секунды (а скорее всего единицы миллисекунд)?

Alek в сообщении #1594046 писал(а):

Не нашёл адекватного способа в паскале абс нет – для операций только с натуральными числами.

Всё есть: заменяйте / на div, frac на mod (разумеется от других аргументов).

Оптимизировать программу с тем, чтобы могла работать почти с любыми большими значениями, так как после введеиня иксов величинами свыше 200 000 000, программа дополняет тройки всякой ерундой, в ҡонце. Не принципиально, но значит где-то вылезает ошибка кода.

Насчёт див и мод: я чуть больше недели в прогр., поэтому вообще не понял, от каких аргументов чего надо менять))

[Booker48]

Для больших $x$ программа не будет работать, нужна длинная арифметика, какие-то библиотеки подключать.
Как пример, при $x=622402679=24943\cdot 24953$ должно получиться ровно две тройки (из евклидовой параметризации), но программа выдаёт сотни троек.
Нельзя $y$ объявлять как $real$, будут накапливаться ошибки округления, проверки будут просто неправильно работать.

[wrest]

Alek в сообщении #1594072 писал(а):

А кода переставил зет, тогда фрак не смог больше рарешать значения только с нулевой дробной частью, и прога на х=3, выдала кроме тройки, лишнюю хрень:

Не так переставили. Надо было так:

  if frac(y) = 0 then
      z := y + k;
      println('Pythagorean Triple:',x,y,z);

-- 16.05.2023, 12:31 --

Alek в сообщении #1594072 писал(а):

так как после введеиня иксов величинами свыше 200 000 000, программа дополняет тройки всякой ерундой, в ҡонце.

А... ну тут дело такое. Придется вам изучать типы, что такое integer, какие ещё целые типы бывают, что делать если числа слишком большие и т.п.

[Alek]

wrest в сообщении #1594077 писал(а):

Alek в сообщении #1594072 писал(а):

А кода переставил зет, тогда фрак не смог больше рарешать значения только с нулевой дробной частью, и прога на х=3, выдала кроме тройки, лишнюю хрень:

Не так переставили. Надо было так:

  if frac(y) = 0 then
      z := y + k;
      println('Pythagorean Triple:',x,y,z);

Я так и сделал)) Выдаёт лишнее.

[wrest]

Alek в сообщении #1594078 писал(а):

Я так и сделал)) Выдаёт лишнее.

Не может быть. Что-то где-то напутали.

[Alek]

wrest в сообщении #1594070 писал(а):

Чётность x и k совпадает, так что можно...

Писать

 if k=1 then k=-1;

Это сократит перебор в 2 раза. Для простых x будет только одна тройка, при k=1.
Ну и ясно что перебор сокращается в зависимости от факторизации x но сходу неясно как.

Не принимает

 k=-1

курор перед равно:
Program3.pas(8) : Встречено '=', а ожидалось ';'

[wrest]

Alek в сообщении #1594072 писал(а):

Насчёт див и мод: я чуть больше недели в прогр.,

Э... ясно.

-- 16.05.2023, 12:39 --

Alek в сообщении #1594082 писал(а):

Не принимает
Код:

k=-1

Да, в Паскале же надо писать k:=-1

[Alek]

wrest в сообщении #1594079 писал(а):

Alek в сообщении #1594078 писал(а):

Я так и сделал)) Выдаёт лишнее.

Не может быть. Что-то где-то напутали.

  if frac(y) = 0 then
      z := y + k;
      println('Pythagorean Triple:',x,y,z);

Вот точно так же! И раньше пробовал, даёт лишние вещественные. Вернул – всё норм))
Все поправки сделал, коме той*, всё работает))

[wrest]

Alek в сообщении #1594085 писал(а):

Вот точно так же! И раньше пробовал, даёт лишние вещественные. Вернул – всё норм))

Значит где-то раньше в тексте напутали.

[Booker48]

wrest в сообщении #1594070 писал(а):

Ну и ясно что перебор сокращается в зависимости от факторизации x но сходу неясно как.

Вообще никакой перебор не нужен, если факторизовать $x$.
Из параметризации Евклида $x=m^2-n^2=(m-n)(m+n)$
Имея все делители, рассматриваем их попарно, вычисляем $m$ и $n$, а из них автоматически получаем второй катет и гипотенузу пифагоровой тройки.

[Dmitriy40]

Alek в сообщении #1594072 писал(а):

Оптимизировать программу с тем, чтобы могла работать почти с любыми большими значениями, так как после введеиня иксов величинами свыше 200 000 000, программа дополняет тройки всякой ерундой, в ҡонце. Не принципиально, но значит где-то вылезает ошибка кода.

Разумеется ошибка вылезает в Sqr(x), потому что при x>46340 результат возведения в квадрат больше максимально представимого числа в формате integer.
И кстати замена integer на int64 и даже BigInteger не спасёт: тогда деление Sqr(x)/k для k<6 и при x>3e8 будет возвращать число, которое после деления на 2 в любом случае будет иметь нулевую дробную часть, просто потому что она не умещается в 54 бита мантиссы типа real.

Про одинаковую чётность x и k уже написали.

Для деления вместо / надо использовать div.
Для проверки на делимость (т.е. будет ли дробная часть после деления) использовать mod.
Как именно - изучайте справку по операциям.

Это если не трогать сам алгоритм, потому что иначе его надо чуть ли не весь выкинуть и сделать по другому - например как описал Booker48. И факторизация - разложение на простые множители, действие достаточно стандартное, хоть и не реализуемое одной какой-то функцией в паскале.