{"id":15428,"date":"2019-04-16T08:08:10","date_gmt":"2019-04-16T12:08:10","guid":{"rendered":"http:\/\/scruss.com\/blog\/?p=15428"},"modified":"2019-04-16T08:08:15","modified_gmt":"2019-04-16T12:08:15","slug":"gleeful-bash-scripting-contrived-gcd-function","status":"publish","type":"post","link":"https:\/\/scruss.com\/blog\/2019\/04\/16\/gleeful-bash-scripting-contrived-gcd-function\/","title":{"rendered":"gleeful bash scripting: contrived GCD function"},"content":{"rendered":"\n

The greatest common divisor<\/a> (gcd) of two natural numbers is the largest number that evenly divides both. For instance gcd(8, 12)<\/em> is 4. There are many clever and efficient<\/a> ways to calculate the gcd of two numbers on a Linux machine. The method presented here is not among them.<\/p>\n\n\n\n

#!\/bin\/bash
gcd(){ comm -12 --nocheck-order <(factor $1|sed 's\/^[^ ]*\/1\/;s\/ \/\\n\/g') <(factor $2|sed 's\/^[^ ]*\/1\/;s\/ \/\\n\/g')|tr '\\n' \\*|sed 's\/.$\/\\n\/'|bc;}
gcd $1 $2 <\/pre>\n\n\n\n
(Contrived) example:<\/p>\n\n\n\n
gcd.sh 24691357802469135780246913578 61728394506172839450617283945
12345678901234567890123456789<\/pre>\n\n\n\n
Which breaks down as:<\/p>\n\n\n\n\n  \n    
prime factors of
24691357802469135780246913578<\/td>\n    		prime factors of
61728394506172839450617283945<\/td>\n  <\/tr>\n  
2<\/td> <\/td><\/tr>\n  
3<\/td>3<\/td><\/tr>\n  
3<\/td>3<\/td><\/tr>\n  
3<\/td>3<\/td><\/tr>\n  
 <\/td>5<\/td><\/tr>\n  
7<\/td>7<\/td><\/tr>\n  
13<\/td>13<\/td><\/tr>\n  
31<\/td>31<\/td><\/tr>\n  
37<\/td>37<\/td><\/tr>\n  
211<\/td>211<\/td><\/tr>\n  
241<\/td>241<\/td><\/tr>\n  
2161<\/td>2161<\/td><\/tr>\n  
3607<\/td>3607<\/td><\/tr>\n  
3803<\/td>3803<\/td><\/tr>\n  
2906161<\/td>2906161<\/td><\/tr>\n<\/table>\n\n\n\n
Multiply the factors common to both:<\/p>\n\n\n\n
3 \u00c3\u2014 3 \u00c3\u2014 3 \u00c3\u2014 7 \u00c3\u2014 13 \u00c3\u2014 31 \u00c3\u2014 37 \u00c3\u2014 211 \u00c3\u2014 241 \u00c3\u2014 2161 \u00c3\u2014 3607 \u00c3\u2014 3803 \u00c3\u2014 2906161 = 12345678901234567890123456789<\/p>\n\n\n\n
I’m sure someone else has used the output of factor<\/a> and comm<\/a> in this way before. The hard part was getting coprime<\/a> numbers to output 1.
<\/p>\n","protected":false},"excerpt":{"rendered":"
The greatest common divisor (gcd) of two natural numbers is the largest number that evenly divides both. For instance gcd(8, 12) is 4. There are many clever and efficient ways to calculate the gcd of two numbers on a Linux machine. The method presented here is not among them. #!\/bin\/bashgcd(){ comm -12 –nocheck-order <(factor $1|sed […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[2],"tags":[],"class_list":["post-15428","post","type-post","status-publish","format-standard","hentry","category-goatee-stroking-musing-or-something"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/pQNZZ-40Q","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/posts\/15428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/comments?post=15428"}],"version-history":[{"count":8,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/posts\/15428\/revisions"}],"predecessor-version":[{"id":15436,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/posts\/15428\/revisions\/15436"}],"wp:attachment":[{"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/media?parent=15428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/categories?post=15428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scruss.com\/blog\/wp-json\/wp\/v2\/tags?post=15428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}