wszystkie trojki pitagorejskie

od kilku dni (z przerwami nawet tygodni) pisze (probuje napisac) program generujacy wszystkie trojki pitagorejskie z jakiegos przedzialu [0..c]. rozwiazanie typu 3 zagniezdzone petelki nie wchodzi w gre gdyz bardzo wazna jest szybkosc tego programu. w skrocie: jaki jest najbardziej wydajny algorytm znajdowania wszystkich trojek pitagorejskich z danego przedzialu? moze ktos juz sie tym kiedys zajmowal i bedzie w stanie mi pomoc. bede bardzo wdzieczny ;]

sam doszedlem do czegos takiego:

var
  a: double;
  b,m,x,c,i,ile: integer;
begin
ile:=1;
c:=StrToInt(Edit1.Text);
b:=100;
m:=0;
a:=1;

for i:=5 to c do
    begin
        while a<b do
          begin
                m:=m+1;
                a:=sqrt(m*(2*i-m));
                b:=i-m;
                x:=Floor(a);
                if (x=a) and (b>a) then
                  begin
                        StringGrid1.Cells[0,ile]:=FloatToStr(a);
                        StringGrid1.Cells[1,ile]:=FloatToStr(b);
                        StringGrid1.Cells[2,ile]:=FloatToStr(i);
                        StringGrid1.RowCount:=StringGrid1.RowCount+1;
                        inc(ile);
                  end;
          end;
    b:=100;
    m:=0;
    a:=1;
    ProgressBar1.Position:=i;
    end;
end;

raczej watpie w to ze jest to algorytmy optymalny..... blagam o pomoc :)</b>

Coś takiego powinno być bardzo szybkie. Dla swojego ułatwienia minimum i maksimum zdefiniowałem jako stałe, a wynik zapisuje w ListBox, ale idea powinna być dobra.

var a,b:integer;
    c:double;
const min=1;
      max=1000;
begin
ListBox1.Items.BeginUpdate;
for a:=min to max do
  begin
  b:=a;
  while (b<=max) do
    begin
    c:=sqrt(sqr(a)+sqr(b));
    if (c<=max) and (c>=min) and (c=round(c)) then
      ListBox1.Items.Add(IntToStr(a)+' '+IntToStr(b)+' '+IntToStr(round(c)));
    inc(b);
    end;
  end;
ListBox1.Items.EndUpdate;
end;

[DOPISANE]

Trójki pitagorejskie o liczbach z zakresu [1..10000] - a jest ich 12471, nie wliczając powtórzeń (3 4 5 oraz 4 3 5 na liście pojawią się tylko raz, jako 3 4 5) - na moim Athlon 1,2GHz wypisuje w czasie poniżej 4 sekund. Po obniżeniu zakresu do [1..1000] wyszukiwanie trwa około 50ms - 881 wyników bez powtórzeń.

wielkie thx!! :D ze wstepnych testow juz widze ze twoja procedurka jest szybsza :D a moze ktos jeszcze ma jakies pomysly? :D no nic ja lece sobie testowac :) Sczawik [browar]

hm dziwna sprawa.. zmodyfikowalem swoja procedurke tak aby korzystala z listboxa zamiast stringgrida.. okazalo sie ze jednak moja procedurka jest szybsza

Jeszcze szybsze jest:

http://pl.freeglossary.com/Teoria_liczb napisał(a)

Klasycznym przykładem równania diofantycznego rozwiązanego w liczbach naturalnych już przez samego Diofantosa (to od jego nazwiska ukuto nazwę tego działu matematyki) jest problem trójkątów pitagorejskich. Szukamy rozwiązań w liczbach naturalnych równania: x 2 + y 2 = z 2 . Przykładowe rozwiązania to następujące trójki pitagorejskie : (3 4 5) (5 12 13) .... Rozwiązania nie będące wielokrotnościami innych rozwiazań to tzw. "rozwiązania właściwe".

Takich trójkątów pitagorejskich (o bokach całkowitej długości) jest nieskończenie wiele. Wszystkie rozwiązania właściwe równania Pitagorasa w liczbach naturalnych (x y z) można uzyskać ze wzorów które znał już Diofantos: <math>x=k^2-l2<math> <math>y=2kl<math> <math>z=k^2+l2<math>; gdzie k l to liczby naturalne przy czym k > l. Jeśli k i l są względnie pierwsze uzyskuje się rozwiązania właściwe nie będące wielokrotnością innych rozwiązań. W ten sposób można uzyskać wszystkie rozwiązania.

var
  k,l:integer;
  ksqr, lsqr:integer;
  a,b,c:integer;
  f:dword;
const min=1;
      max=1000;
begin
f:=timeGetTime();
ListBox1.Clear;
ListBox1.Items.BeginUpdate;
for k:=min to round(sqrt(max)) do
  begin
  l:=min;
  while (l<k) do
    begin
    ksqr:=round(sqr(k));
    lsqr:=round(sqr(l));
    a:=ksqr-lsqr;
    b:=(k*l) shl 1;
    c:=ksqr+lsqr;
    if (a>=min) and (a<=max) and (b>=min) and (b<=max) and (c>=min) and (c<=max) then
    ListBox1.Items.Add(IntToStr(a)+' '+IntToStr(b)+' '+IntToStr(c)+' : '+IntToStr(k)+' '+IntToStr(l));
    inc(l);
    end;
  end;
ListBox1.Items.EndUpdate;
Caption:=inttostr(ListBox1.Items.Count)+' ~ '+Inttostr(timegettime()-f);
end;

Tylko nie wiem czemu, nie pokazuje mi połowy kombinacji.. Choć powinien teoretycznie pokazywac wszystkie. Ale jest bardzo szybkie.

[DOPISANE]

Nie pokazuje kombinacji, w których k oraz l powinny nie być całkowite: (9 12 15) k=2*(3^{0,5) l=(3}0,5)

no wlasnie te wzorki o ktorych mowisz sa bardzo przydatne.. tylko jak je zmusic zeby generowaly wszystkie mozliwe trojki pitagorejskie?

taki zestaw wzorow
a=kk-ll
b=2kl
c=kk+ll
dla k>l rzeczywiscie generuje trójki ale niestety nie wszystkie..

taki zestaw wzorow
a=d(kk-ll)
b=d(2kl)
c=d(kk+ll)
gdzie k>l i d{1,2,...} pozwalaja obliczyc wszystkie trojki pitagorejskie niestety wiele z nich bedzie sie powtarzac.. nie mam pomyslu jakby to optymalnie zapetlic..

aby trojki sie nie powtarzaly musielibysmy stwierdzic czy k i l sa wzglednie pierwsze i dopiero wtedy mnozyc przez "d".. problem w tym ze algorytm staje sie wtedy malo efektywny..

tak wyglada funkcja wyznaczajaca najwiekszy wspolny dzielnik

Function gcf(a, b: Word): Word;
{ a > b and a, b > 0 }
{ return greatest common factor of a and b }
{ Euclids method (AKA Euclidian Algorithm)
    any number that divides a and b must divide (a - b) }
var alpha, g, z: integer;
begin
  alpha:= a;
  g:= b;
  if b > 0 then
    repeat
      z:= alpha mod g;
      alpha:= g;
      g:= z;
    until g = 0;
  result:= alpha;
end;