Skip to content

Instantly share code, notes, and snippets.

@lucainnocenti
Created April 29, 2021 17:38
Show Gist options
  • Save lucainnocenti/c77cf083b0f00205f0ff613702d2a753 to your computer and use it in GitHub Desktop.
Save lucainnocenti/c77cf083b0f00205f0ff613702d2a753 to your computer and use it in GitHub Desktop.
Perform and visualise Euclidean algorithm on a pair of integers
euclideanAlgorithmList[a_Integer, b_Integer] := NestWhileList[
With[{newSortedPair = {Max@# - Floor[Max@#/Min@#] Min@#, Min@#}},
If[#[[1]] > #[[2]], newSortedPair, Reverse@newSortedPair]
] &,
{a, b},
Min @ # > 1 &
];
DynamicModule[{a = 17, b = 10},
EventHandler[
Deploy @ Graphics[{PointSize @ 0.02,
{Point @ #, Line @ #, PointSize @ 0.03, Red, Point @ First @ #} &@
euclideanAlgorithmList[a, b] // Dynamic,
Red, InfiniteLine[{0, 0}, {1, 1}]
}, Frame -> True, GridLines -> Automatic,
AspectRatio -> 1, PlotRange -> ConstantArray[{0, 20}, 2]
],
{"MouseDragged" :> Set[{a, b}, Round /@ MousePosition["Graphics"]]}
]
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment