Text 151, 227 rader
Skriven 2004-08-27 12:57:32 av DAVID WILLIAMS (1:250/514)
Ärende: Another one
===================
I realized that I could make the program handle very large numbers 
without getting rid of all the integer operations. Only a few numbers 
(B and C in the triple, and things that are immediately involved in 
calculating them) can be huge. All the other numbers are relatively 
small, and won't overflow "long" integers until B and C get so vast 
that even "doubles" won't handle them precisely. 
  
So, here's a version in which A can go past 100 million, and which is 
only moderately slower than the most recent all-integer one. Miles will 
probably find that it takes 4 seconds, under his standard test 
conditions. 
  
                             dow 
  
-------------------------------------------------------------- 
  
' PYTRIPLE.BAS - Pythagorean Triples 
  
' David O. Williams. 2004 
' david.williams@ablelink.org 
  
' Calculates and prints integer triples, A, B, C, such that 
' A < B < C,  they have no common factors (>1), and A^2 + B^2 = C^2. 
' The list is printed in order of increasing A, then of B. 
' A counter of triples is also shown. 
  
' A more detailed explanation is at the end of the main module. 
  
DECLARE FUNCTION NoComFacs& (S&, T&) 
DECLARE SUB PrintOut (A&, B#, C#) 
  
DEFLNG A-Z 
DEFDBL B-C 
  
CLS 
  
DO 
  PRINT "Both values must be >= 0, and Maximum >= Minimum" 
  PRINT 
  INPUT "Minimum value of smallest number in triple"; Mn 
  INPUT "Maximum value of smallest number in triple"; Mx 
  PRINT 
  IF Mn >= 0 AND Mx >= 0 AND Mx >= Mn THEN EXIT DO 
  BEEP 
  PRINT "Illegal value/s!" 
  PRINT 
LOOP 
  
IF Mx > 2 AND (Mx > Mn OR (Mn <> 4 AND Mn MOD 4 <> 2)) THEN 
  PRINT "Count"; TAB(16); "A"; TAB(33); "B"; TAB(56); "C" 
  PRINT 
ELSE 
  PRINT "There are no triples in this range!" 
  END 
END IF 
  
Z# = SQR(2) + 1 
  
Q = INT(SQR(Mn / Z#)) - 1 OR 1 ' initial loop limit for odd cases 
J = Q + 2 
K = INT(J * J * Z#) 
  
R = INT(SQR(Mn / (Z# + Z#))) ' initial loop limit for even cases 
L = R + 1 
M = INT(L * L * Z#) 
  
' start of main loop 
FOR A = Mn TO Mx 
  SELECT CASE A MOD 4 
    CASE 0 
      S = A \ 2 
      IF S > M THEN 
        R = L 
        L = L + 1 
        M = INT(L * L * Z#) 
      END IF 
      FOR F = R TO 1 STEP -1 
        IF S MOD F = 0 THEN 
          G = S \ F 
          IF (F XOR G) AND 1 THEN 
            IF NoComFacs(F, G) THEN 
              X# = 1# * G * G 
              Y = F * F 
              B = X# - Y 
              C = X# + Y 
              PrintOut A, B, C 
            END IF 
          END IF 
        END IF 
      NEXT 
    CASE 1, 3 
      IF A > K THEN 
        Q = J 
        J = J + 2 
        K = INT(J * J * Z#) 
      END IF 
      FOR D = Q TO 1 STEP -2 
        IF A MOD D = 0 THEN 
          E = A \ D 
          IF NoComFacs(D, E) THEN 
            T = D * D 
            B = (1# * E * E - T) / 2 
            C = B + T 
            PrintOut A, B, C 
          END IF 
        END IF 
      NEXT 
  END SELECT 
NEXT 
  
END 
  
'---------------------------------------------------------- 
  
' Brief explanation: 
  
' Pythagorean triples, if they are in lowest terms with no common 
' factors, can be written as: Odd#^2 + Even#^2 = Big#^2. Big# is the 
' largest integer (corresponding to the hypotenuse of the right-angled 
' triangle). However, Odd# may be smaller or larger than Even#. 
  
' If the three above numbers have no common factors, it is possible 
' to define two odd positive integers, D and E, with E > D, such that: 
  
' Odd# = D * E 
' Even# = (E^2 - D^2) / 2 
' Big# = (E^2 + D^2) / 2 
  
' These definitions satisfy Pythagoras's Theorem. It is possible to 
' prove that all valid triples, in lowest terms, can be written this 
' way, with odd-integer values of D and E. (They must both be odd, so 
' that their product is Odd#.) 
  
' If a triple is written as A, B, C, with A < B < C, C must correspond 
' to Big#, but A can be either Odd# or Even#, and B will be the other. 
  
' The program treats these two possibilities separately. If A is odd, 
' so it must be Odd#, the program simply searches for two odd integers 
' whose product is A. After confirming that they have no common 
' factors, which would mean that the triple is not in lowest terms, 
' the program calculates B and C from them, and prints them out. 
  
' If A is even, it is useful to define two further numbers, F and G, 
' with G > F, such that: 
  
' D = G - F 
' E = F + G 
  
' This means that: 
  
' F = (E - D) / 2 
' G = (D + E) / 2 
  
' Since D and E are both odd, their sum and difference are both even, 
' so F and G are integers. However, the sum and difference of F and G 
' are E and D, which are odd, which implies that the parities of F 
' and G must be opposites, so one is odd and the other even. 
  
' Since, in this case, A is the same as Even#, it is given by: 
  
' A = (E^2 - D^2) / 2 
  
' Writing G - F for D and G + F for E, and simplifying, this gives: 
  
' A / 2 = F * G 
  
' Since F and G are of opposite parity, this means that A / 2 must be 
' even, so A must be a multiple of 4. There are no valid triples when 
' A MOD 4 = 2. 
  
' When A is a multiple of 4, the program looks for factors of A / 2. 
' It checks that they are of opposite parity, and have no common 
' factors. It then uses these values of F and G to calculate B and 
' C, using the easily-proved formulae: 
  
' B = G^2 - F^2 
' C = G^2 + F^2 
  
' (Strictly, the parity check could be omitted. Since they are factors 
' of an even number, at least one of the found values of F and G must 
' be even. The possibility that they are both even would be detected 
' by the common-factor test. However, the parity check is much simpler 
' and faster than the common-factor routine, so having it in the 
' program saves some time.) 
  
' The FOR ... NEXT loops in the odd and even CASEs search for the 
' factors D and E, or F and G, respectively, The loops run from 
' high to low values of the counting variables, since this makes the 
' triples appear in the desired order. Also, the ranges of the loops 
' are limited so that only triples in which B > A appear. The 
' variables Q and R govern these ranges. They are initialized near 
' the start of the program, and are incremented in the main loop as 
' the value of A increases. The numbers K and M are pre-calculated 
' limits. When A (or S, which is just A \ 2 when A is even) passes 
' the relevant limit, Q or R is incremented appropriately, and a new 
' value of K or M is calculated. In the vast majority of iterations 
' around the loops, it is not necessary to increment Q or R, so all 
' that has to be done is a simple comparison, e.g IF A > K THEN, 
' which turns out not to be true. This saves a lot of time. Also, 
' this method does not use the slow operation SQR inside any loops. 
' A full mathematical treatment of the situation uses the number 
' (SQR(2) + 1) several times. This number is therefore treated as a 
' constant in the program, named Z#. 
  
'                       = end = 
  
  
FUNCTION NoComFacs (S, T) ' non-zero if S and T have no common factors 
  U = T 
  V = S 
  DO WHILE V > 1 
    W = U MOD V 
    U = V 
    V = W 
  LOOP 
  NoComFacs = V 
END FUNCTION 
  
SUB PrintOut (A, B, C) 
  STATIC N 
  N = N + 1 
  PRINT N; TAB(15); A; TAB(32); B; TAB(55); C 
END SUB 
  
-------------------------------------------------------------- 
--- Platinum Xpress/Win/WINServer v3.0pr5
 * Origin: The Bayman BBS,Toronto, (416)698-6573 - 1:250/514 (1:250/514)