Text 138, 246 rader
Skriven 2004-08-22 10:47:40 av DAVID WILLIAMS (1:250/514)
     Kommentar till en text av JASEN BETTS
Ärende: Pythagorean triples
===========================
->  DW> midnight, I would see it briefly show "24:00:00", and then, 1/6 of a 
->  DW> second later, it changed to "00:00:00". So the flip-back to zero must 
->  DW> have occurred at least one interrupt *after* midnight. 
 
-> if it did go back to 0 and not to 1, or possibly this overrun was to correct

-> some innacuracy in the crystal used to drive the clock? (hmm that shouldn't 

-> wasn't interrupt for the the clock was driven by the video hardware? hmm IST

-> it could programmed to interrupt on different video scan-lines...) 
  
I don't think the clock was anything like that accurate, anyway. If TI 
gained or lost 1/60 of a second per day, that would be only about 6 
seconds per year. 
  
I know that on the VIC 20, it was possible to POKE some addresses and 
make fine adjustments to the *speed* of the clock. I think the clock 
speed (interrupt frequency) was generated by dividing the frequency (1 
MHz) of the crystal that clocked the CPU. This crystal wasn't very 
precisely made, so different machines ran at slightly different 
speeds. But the divisor could be varied by POKEing addresses, so the 
speed of the TI clock could be changed. It could be made accurate to 
within a few seconds per year. I used this when I used a VIC to control 
a heliostat. 
  
->  DW> The Mac BASIC with which I am most familiar used BCD arithmetic, 
->  DW> which 
->  DW> was a tad slow, but wonderfully precise. Commodore never had anything 
->  DW> like that. Nor do most PCs, even today. 
 
-> The mac people had some interesting ideas when it came to implementing 
-> languages :) 
 
-> Jasen 
  
Maybe so. But the Mac BASIC was strictly MicroSoft. There were two 
versions, one with BCD arithmetic, and the other with pure binary. The 
binary one was faster, but I *far* preferred the BCD one. 
  
Incidentally, here's the latest version of the triples program. 
*Surely* Miles will find that this executes (with the PRINT line 
disabled) in less than 4 seconds, out to 10,000. 
  
                              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& (X&, Y&) 
DECLARE SUB PrintOut (A&, B&, C&) 
  
DEFLNG A-Z 
  
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", , " A", " B", " 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 
              D = G - F 
              E = F + G 
              B = D * E 
              C = (E * E + D * D) \ 2 
              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 
            B = ((E + D) * (E - D)) \ 2 
            C = (E * E + D * D) \ 2 
            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 them to calculate D and E, and thence B and C. 
  
' (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 coding 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. 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 (X, Y) ' non-zero if X and Y have no common factors 
  U = Y 
  V = X 
  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, , A, B, C 
END SUB 
  
------------------------------------------------------- 
--- Platinum Xpress/Win/WINServer v3.0pr5
 * Origin: The Bayman BBS,Toronto, (416)698-6573 - 1:250/514 (1:250/514)