Computes the Greatest Common Divisor [or Highest Common Factor] of a LIST of integers. Also includes an LCM/LCD program. v1.0 for TI-82. ----begin documentation---- GCDLCM v1.0 is Freeware Commercial Distribution Restricted Copyright (C) 1994 by Mikael Bonnier, Lund, Sweden. 1. System and Memory Requirements This program is for the TI-82. It consists of two main programs, and one sub program that together uses 219 bytes. It requires additionally a minimum of 108 bytes, and a maximum of 973 bytes for data to run, depending on the number of numbers :-). GCDHCF and LCMLCD uses or alters these variables: Real: J,K,L,M,N List: L1 2. Installation If you have TI-GRAPH LINK UUDecode this file, and send the resulting GCDLCM.82G program to the calculator. If you don't have a link you will have to enter the three ASCII82P listings below. 3. User Instructions The program computes the Greatest Common Divisor (GCD) or the Highest Common Factor (HCF) of some numbers. The GCD is defined as the largest number which divides all the given numbers evenly (i.e. with remainder zero). This is same as the HCF. GCDHCF handles lists as long as the TI-82 allows i.e. 99 elements. The elements must be integers greater than or equal to zero. The program uses the list stored in Ans. Example: {20,70,80}:prgmGCDHCF [ENTER] Ans=10 Example: {294,210,126,462} [ENTER] prgmGCDHCF [ENTER] Ans=42 Which can be tested by: {294,210,126,462}/42 [ENTER] Ans={7 5 3 11} A common manual algorithm is to divide all numbers with a small prime number, that divide all the numbers evenly. Write out the results and then 'Da Capo al Fine'. Then one multiplies together the divisors [factors] to get the GCD [HCF]. However this is not the algorithm this program uses. LCMLCD has the same user interface as GCDHCF but computes the Least Common Multiple or the Least Common Denominator. The LCM is defined as least number that is a multiple of each number in the list. A multiple of a number is the product of that number and an integer. The LCD is same as the LCM. Example: {21,24,26,28}:prgmLCMLCD [ENTER] Ans=2184 Warning: This program is not secure. You can enter erroneous indata without the program complaining, and you may receive reasonable but incorrect outdata. (This is famous SISO priniple, Shit In Shit Out.) But it is not difficult to add code to make it safe. 4. Program Comments The program uses Euclid's GCD [HCF] algorithm. GCDHCF and LCMLCD uses the same subprogram: ZGCDHCF. 'MfPart (N/M)' computes the remainder of N integer-divided by M. The 'round(' function prevents build-up of floating point errors. 5. References Check out any reasonable text on algebra or algorithms, e.g.: Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. "Introduction to Algorithms". The MIT Press, Cambridge, Massachusetts, 1990. John Daintith and R. D. Nelson (Editors). "The Penguin Dictionary of Mathematics". Penguin Books Ltd, London, 1989. A. K. Dewdney. "The (New) Turing Omnibus". Computer Science Press and W. H. Freeman and Company, New York, 1993. Suggestions, improvements, bug, and bad-English-in-doc reports are always welcome to: Mikael Bonnier Osten Undens gata 88 SE-227 62 LUND SWEDEN Or use my internet addresses: mikael.bonnier@gmail.com http://www.df.lth.se.orbin.se/~mikaelb/ // Mikael Bonnier ///////////////////////////////////////////////////////////////////// ----begin ascii---- \START82\ \COMMENT=1994 Mikael Bonnier,mikael.bonnier@gmail.com \NAME=GCDHCF \FILE=GCDHCF.82P Ans\->\\L1\ abs \L1\(1)\->\N For(J,2,dim \L1\) prgmZGCDHCF round(N,0)\->\N End N \STOP82\ \START82\ \COMMENT=1994 Mikael Bonnier,mikael.bonnier@gmail.com \NAME=LCMLCD \FILE=LCMLCD.82P Ans\->\\L1\ abs \L1\(1)\->\N For(J,2,dim \L1\) N\->\K prgmZGCDHCF round(K\L1\(J)/N,0)\->\N End N \STOP82\ \START82\ \COMMENT=1994 Mikael Bonnier,mikael.bonnier@gmail.com \NAME=ZGCDHCF \FILE=ZGCDHCF.82P min(N,abs \L1\(J))\->\M max(N,abs \L1\(J))\->\N While M>.5 MfPart (N/M)\->\L M\->\N L\->\M End Return Disp "MIKAEL BONNIER,LUND,SWEDEN" \STOP82\ ----begin uue---- begin 644 GCDLCM.82G M*BI423@R*BH:"@!'