TI 30Xa Algorithms: Greatest Common Divisor

TI 30Xa Algorithms: Greatest Common Divisor

To find the greatest common divisor between two positive integers U and V:

Let U ≥ V. Let U = A * V + R where A is the quotient of U / V and R is the remainder. If R≠0, then V becomes the new U and R become the new V. The process repeats until R=0. At that point the value of V prior to the last calculation is the greatest common divisor (GCD) of U and V.

Example:

gcd(166, 78)

U = 166, V = 78

Algorithm Loop:

1. A = int(U / V)

2. R = U – V * int(U / V)

	A	R	U	V
Start	n/a	n/a	166	78
A = int(166 / 78) = 2 R = 166 – 2 * 78 = 10	2	10	78	10
A = int(78 / 10) = 7, R = 78 – 7 * 10 = 8	7	8	10	8
A = int(10 / 8) = 1 R = 10 – 1 * 8 = 2	1	2	8	2
A = int(8 / 2) = 4 R = 8 – 4 * 2 = 0	4	0 *STOP*

Procedure

1. Store the greater of the two numbers in memory register 1: [ STO ] [ 1 ].

2. Store the lesser of the two numbers in memory register 2: [ STO ] [ 2 ].

3. Divide memory register 1 by memory register 2. Store the integer part (no fractional part) in memory register 3: [ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ], (integer part) [ STO ] [ 3 ]

4. Figure the remainder and store the result in memory 3: [ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] [ STO ] [ 3 ]

5. If the remainder is 0, stop. The GCD is stored in memory 2.

6. If the remainder is non-zero, then store memory 2 into memory 1 then memory 3 into memory 2. You need to do it in this order. [ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]. Go back to Step 3 and repeat.

Examples

Example 1: GCD(26, 14)

M1 = 26, M2 = 14

	M1	M2	M3
26 [ STO ] [ 1 ], 14 [ STO ] [ 2 ]	26	14
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.857142857 1 [ STO ] [ 3 ]	26	14	1
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 12 [ STO ] [ 3 ] R is not zero, so we continue.	26	14	12
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]	14	12	12
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.166666667 1 [ STO ] [ 3 ]	14	12	1
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 2 [ STO ] [ 3 ] R is not zero, so we continue.	14	12	2
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]	12	2	2
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 6 6 [ STO ] [ 3 ]	12	2	6
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 0 [ STO ] [ 3 ] R is zero, so we stop. GCD: [ RCL ] [ 2 ]: GCD(26, 14) = 2	12	2	0

Example 2: GCD(27, 15)

M1 = 27, M2 = 15

	M1	M2	M3
27 [ STO ] [ 1 ], 15 [ STO ] [ 2 ]	27	15
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.8 1 [ STO ] [ 3 ]	27	15	1
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 12 [ STO ] [ 3 ] R is not zero, so we continue.	27	15	12
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]	15	12	12
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.25 1 [ STO ] [ 3 ]	15	12	1
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 3 [ STO ] [ 3 ] R is not zero, so we continue.	15	12	3
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]	12	3	3
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 4 4 [ STO ] [ 3 ]	12	3	4
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 0 [ STO ] [ 3 ] R is zero, so we stop. GCD: [ RCL ] [ 2 ]: GCD(27, 15) = 3	12	3	0

I hope you find this useful. What I hope to do with the monthly series is to demonstrate various calculations with the TI-30Xa.

Note: For June and July 2024, I will be posting on Saturdays only. I plan to resume the Saturday-Sunday schedule in August.

Eddie

All original content copyright, © 2011-2024. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.

Swiss Micros DM32: Spherical Triangle ft. Law of Cosines

Swiss Micros DM32: Spherical Triangle ft. Law of Cosines

Introduction

The state file spheretri.d32 is about solving triangles on the spherical space.

The programs solve spherical triangles in two common problems: SSS (side-side-side, really arc lengths) and SAS (side-angle-side). All the inputs are in decimal degrees.

Also calculated are the surface area and perimeter, both in radians. The radius is assumed to be 1.

Surface Area = ( A° + B° + C° ) * π / 180 – π = A + B + C – π

Perimeter = ( X° + Y° + Z°) * π / 180 = X + Y + Z

The sum of the angles (A, B, C) must be greater than 180° (π radians). Due to this requirement, in solving for angles and sides, the Law of Cosines will be used in each instance. The Law of Sines is only advised to check ratios.

Equation listing

Law of Sines – can be used as a check on triangles:

SIN(A)÷SIN(X)=SIN(B)÷SIN(Y)

Law of Cosines – two equations:

COS(Z)=COS(X)×COS(Y)+SIN(X)×SIN(Y)×COS(C)

COS(C)=-COS(A)×COS(B)+SIN(A)×SIN(B)×COS(Z)

Here the variables are general place holders.

Program Listing

Labels:

Label H: help program

Label I: Initialization routine. Sets the angles mode to degrees and clears the variables.

Label C: Starts the solve spherical triangle routine: given the three arc lengths X, Y, and Z.

Label Z: Starts the solve spherical triangle routine: given the arc lengths X and Y and and the angle between the arcs, angle C

Label F: Routine to solve for angles A and B, perimeter, and area

General Instructions

1. To start a new problem, execute program I.

2. To solve a spherical triangle given the sides (arc lengths), execute program C. (SSS)

3. To solve a spherical triangle given two sides and the internal angle, execute program Z. (SAS)

This program also solves for the surface area, assuming a radius of 1, and perimeter of the triangle.

Program Code

H01 LBL H

H02 SF 10

H03 EQN: A N G L E _ A _ B _ C

H04 EQN: S I D E S _ X _ Y _ Z

H05 EQN: X E Q _ C _ S S S

H06 EQN: X E Q _ Z _ S A S

H07 EQN: E Q N S _ A R E _ S I N E

H08 EQN: A N D _ C O S I N E _ L A W S

H09 CF 10

H10 RTN

I01 LBL I

I02 DEG

I03 CLVARS

I04 CLx

I05 RTN

C01 LBL C

C02 INPUT X

C03 INPUT Y

C04 INPUT Z

C05 RCL Z

C06 COS

C07 RCL X

C08 COS

C09 RCL Y

C10 COS

C11 ×

C12 -

C13 RCL X

C14 SIN

C15 RCL Y

C16 SIN

C17 ×

C18 ÷

C19 ACOS

C20 STO C

C21 VIEW C

C22 XEQ F

C23 RTN

Z01 LBL Z

Z02 INPUT X

Z03 INPUT Y

Z04 INPUT C

Z05 RCL X

Z06 COS

Z07 RCL Y

Z08 COS

Z09 ×

Z10 RCL X

Z11 SIN

Z12 RCL Y

Z13 SIN

Z14 ×

Z15 RCL C

Z16 COS

Z17 ×

Z18 +

Z19 ACOS

Z20 STO Z

Z21 VIEW Z

Z22 XEQ F

Z23 RTN

F01 LBL F

F02 RCL X

F03 COS

F04 RCL Z

F05 COS

F06 RCL Y

F07 COS

F08 ×

F09 -

F10 RCL Z

F11 SIN

F12 RCL Y

F13 SIN

F14 ×

F15 ÷

F16 ACOS

F17 STO A

F18 RCL Y

F19 COS

F20 RCL X

F21 COS

F22 RCL Z

F23 COS

F24 ×

F25 -

F26 RCL X

F27 SIN

F28 RCL Z

F29 SIN

F30 ×

F31 ÷

F32 ACOS

F33 STO B

F34 RCL A

F35 RCL+ B

F36 RCL+ C

F37 →RAD

F38 π

F39 -

F40 STO R

F41 RCL X

F42 RCL+ Y

F43 RCL+ Z

F44 →RAD

F45 STO P

F46 VIEW A

F47 VIEW B

F48 VIEW R

F49 VIEW P

F50 RTN

You can download the DM32 state file here:

https://drive.google.com/file/d/1qX-y2G5sCOmm4ktmZbnGoPI3uzrx6IfF/view?usp=sharing

Examples  (FIX 5)

SSS Problem (LBL C)

X = 18.66°

Y = 20.49°

Z = 19.95°

Results:

C = 62.04726°

A = 55.92702°

B = 64.98954°

R = 0.05173 radians (surface area)

P = 1.03149 radians (perimeter)

SAS Problem (LBL Z)

X = 17.00 °

Y = 23.32°

C = 64.55°

Results:

Z = 21.88733°

A = 45.08768°

B = 73.51096 °

R = 0.05495 radians (surface area)

P = 1.08572 radians (perimeter)

Sources

Wikipedia. “Spherical Triangle” Updated April 9, 2024. Retrieved April 11, 2024.

https://en.wikipedia.org/wiki/Spherical_trigonometry#:~:text=Spherical%20trigonometry%20is%20the%20branch,sphere%2C%20geodesics%20are%20great%20circles.

Gray, Glen. “Spherical Trigonometry – An Introduction and Basic Theorems” Video. February 12, 2023. Retrieved April 11, 2024. https://www.youtube.com/watch?v=McWv9bcvMYg

Note: The blog will be posted on Saturdays only on June and July 2024.

Eddie

All original content copyright, © 2011-2024. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.