Text 20, 77 rader
Skriven 2004-08-02 16:27:52 av DAVID WILLIAMS (1:250/514)
     Kommentar till en text av JASEN BETTS
Ärende: Pythagorean triples
===========================
Well... I think I've BASICally solved the problem. Try the following 
thing. It's remarkably fast! I think the time it takes is roughly 
proportional to N^(3/2), so it does slow down as N increases, but not 
very much. 
  
The clue came when I realized that the "difficult case" I mentioned 
previously is really just like the problem as a whole. So the solution 
is *almost* recursive, though not quite. 
  
Try it! 
  
                         dow 
  
---------------------------------------------------- 
  
' pythagorean triples 
DEFLNG A-Z 
DEFDBL Q 
L = 1000 ' limiting length of shortest side 
DIM B(1 TO SQR(L)), C(1 TO SQR(L)) 
P = 0 
CLS 
FOR A = 3 TO L 
  Z = 0 
  IF A MOD 2 THEN 
    FOR D = 1 TO SQR(A) STEP 2 
      E# = A / D 
      E = E# 
      B = (E * E - D * D) \ 2 
      GOSUB XX 
    NEXT 
  END IF 
  FOR T = 1 TO 2 * SQR(A / 2) 
    Q1 = T / 2 
    Q2 = A / T 
    E# = Q1 + Q2 
    E = E# 
    D = Q2 - Q1 
    B = D * E 
    GOSUB XX 
  NEXT 
  FOR S = 1 TO Z 
    P = P + 1 
    PRINT P, , A, B(S), C(S) 
  NEXT 
NEXT 
END 
XX: 
IF B > A THEN 
 IF D MOD 2 AND E MOD 2 THEN 
  IF ABS(E# - E) < .000000000001# THEN 
   U = B 
   V = A 
   DO WHILE V > 1 
    W = U MOD V 
    U = V 
    V = W 
   LOOP 
   IF U = 1 OR V = 1 THEN 
    C = (E * E + D * D) \ 2 
    Z = Z + 1 
    B(Z) = B 
    C(Z) = C 
    FOR S = Z TO 2 STEP -1 
      IF B(S - 1) < B(S) THEN EXIT FOR 
      SWAP B(S - 1), B(S) 
      SWAP C(S - 1), C(S) 
    NEXT 
   END IF 
  END IF 
 END IF 
END IF 
RETURN 
  
---------------------------------------------------- 
--- Platinum Xpress/Win/WINServer v3.0pr5
 * Origin: The Bayman BBS,Toronto, (416)698-6573 - 1:250/514 (1:250/514)