見出し画像

📐GCD ユークリッドの互除法とへんてこ言語大集合 ずらり195言語

https://editor.p5js.org/setapolo/sketches/mWTItpRpW

ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。

(問題) 1071 と 1029 の最大公約数を求める。

1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。

日本全国の小学生はみんなユークリッドの門下生といえるかもしれない

そしてロゼッタコード(をらが言語をあるテーマに沿って博覧会のようにソース展示しているサイト)との長い闘いがはじまる。

有名なアルゴリズムだけあって195のコンピュータ言語が参戦している。あらためて、そんなにあんのか言語って。

Contents hide

最初のエントリは11l

アルファベット順で先頭をキープしているが、どんな言語なんだまず。

11l は [準密教的な] 高レベル汎用プログラミング言語で、ハードウェアへのシンプルで直接的なマッピングを提供し、C++ のようなゼロオーバーヘッドの原則に従うことを目指しています。11lは静的型付けされていますが、動的型付けされた言語(例えばPython)に非常に似ているように感じます。

(使用者の感想です)

他の既存のプログラミング言語と11lの明らかな違いは、キーワードが単なるリストではなく、ツリーで構成されていることです。ツリーの根元には11個のキーワードがあり、それぞれの単語は1文字として書くことができます。
C, I, E, F, L, N, R, S, T, V, Xです。

のっけからドアあつい言語やのう。。。

キャプチャ

あー、最初が11で最後がL

キャプチャ

サイト自体はしぶかっこいい

F gcd(=u, =v)
  L v != 0
     (u, v) = (v, u % v)
  R abs(u)

さすが11l、簡潔に書いてあるたぶんLはloopのLだろうか、次

いくつかのアセンブリ言語と次世代forth 8thを飛ばして新人Aloreへ

def gcd(a as Int, b as Int) as Int
  while b != 0
     a,b = b, a mod b
  end
  return Abs(a)
end

分かりやすい、分かりやすいAlore君は芸歴何年なの?

Aloreは、PythonやLuaに似たクリーンな構文を持つオブジェクト指向プログラミング言語です。AloreはGoogle Dartのようにオプションで型付けされており、動的スクリプト言語であると同時に静的型付けを持つ汎用言語でもあります。短いスクリプトから複雑なアプリケーションまで、多様なプログラミングタスクを対象としています。また、プログラム内で静的型付けと動的型付けを自由に組み合わせることができます。

Alore君「いろんな言語リスペクトしてるっすけど、しいて言うとpython先輩みたいな言語っすかねー。。。」

その安定志向はおいといて、アルゴリズムとしては単にmodしてグルグル回せばいいみたいだ。あとはp5.jsでそれを面白おかしく書いて終わりにしよう。

残りの195言語のなかから、おもしろいものだけいくつか。。

・安定のAPL、今回はDyalog APLというわけのわからん仲間を引き連れています。
・名前のおもろいArendelle
・MS言語と言いながら評価順がきになるAutoIt
・なんかきたなかっこいいAWK
・誰もしらないAXE

まだA欄しか終わらん、AXE君の影響受けたコードが「しいていえばTI-83 BASICっすかね」って、それが分からんのやないか、

テキサスさんの電卓だそうだ。めちゃめちゃかっこいい。記述が独特なのも分かったAXE

Bracmat

Bracmatは、記号計算のためのインタプリタ型プログラミング言語です。元々は(80年代に)コンピュータ代数システムとして設計されましたが、自然言語処理の分野でもその利点を発揮しています。Bracmatは一般相対性理論の分野では、与えられた時空メトリクスからのリッチテンソルの代数的計算、仮想世界プロジェクトでの対話マネージャの実装、「制御言語」プロジェクトでのテキストの解析、数百のHTMLページの自動エラー訂正などに利用されています。また、Bracmatは、匿名化する必要がある事前にタグ付けされたテキストから個人や企業などを特定するなど、実際のアプリケーションでもその有用性を示しています。

なんか、ストイックなコント師みたいな言語がきた。

BracmatはSNOBOL4(パターンマッチング、成功/失敗)、Lisp(BracmatのプログラムはBracmatのデータと同じもので構成されています)、Prolog(バックトラッキング)、そしてオブジェクト指向言語からインスピレーションを受けています。

あー、もうこれ実力派だわ三年目なのに準決勝確実のやつ。B列は不作かとおもったが(シュール系でBefunge君とか)、本当に実力ありそうだなBracmatは。

C欄はC、C#、Cloureとレジェンドと中堅勢で抑える

LIP系のクロージャーのコードだけ見ておこう。だいぶ見た目に慣れてきた。

(defn gcd 
 "(gcd a b) computes the greatest common divisor of a and b."
 [a b]
 (if (zero? b)
   a
   (recur b (mod a b))))

きれいだな。

モノクロ映画みたいにEDCACコードが やる気の伝わるエリクサー

defmodule RC do
 def gcd(a,0), do: abs(a)
 def gcd(a,b), do: gcd(b, rem(a,b))
end
IO.puts RC.gcd(1071, 1029)
IO.puts RC.gcd(3528, 3780)

見た目がもうなんか遅延評価もなんも全部できそうな雰囲気。

ライブラリでずるするErlang Excel

なんか持ってる印象とだぶる。エクセルもさすがにいっちょかみたかったとみえる。この後定期的にライブラリ関数推奨してくる勢があらわれる。

ダイバーシティー強化のためのEzhil。めっちゃクールなFACTOR

: gcd ( a b -- c )
   [ abs ] [
       [ nip ] [ mod ] 2bi gcd
   ] if-zero ;

ええなあ

期待してたぜforth教授!

最初ライブラリ使ってコメント書いてずるしてるのかと思ったくらいの自然さ。

: gcd ( a b -- n )
 begin dup while tuck mod repeat drop ;

やっぱかっこいいなあ。

私もしゃべくりできますよ、みたいな感じでgnuplot

言語がよくわからん。なんかスクリプト言語が独自にあるっぽい。後でみよー

そしてでた、まさかのプリミティブ採用した言語、さらにしたのが件のJ先輩

こんな書き方

x+.y

コメントも来てます

GCDはJ のプリミティブです。
(そして、正しい数学を勉強したことのある人なら誰でも、なぜGCDとORの両方に同じ演算が使われるのかすぐにわかるはずです。

お説教からだわ。。。さらにソースをあえてかくとこうなるJ

gcd=: (| gcd [)^:(0<[)&|

ほしかったのはp5のための再帰コード

function gcd_rec(a, b) {
 return b ? gcd_rec(b, a % b) : Math.abs(a);
}

これだこれ、ずいぶん遠回りしちまったなあ。。。

せっかくJまで来たから、最後まで見ようか。。。

Kもヤバいぜ

APL系で一文字埋め尽くすつもりか、MIBなのか

イラスト参戦Labview

これもダイバーシティー強化の一環か、しかし、今まで無視してたかもしれない。結構いいな。

キャプチャ

数値系はプライドのように組み込み関数で

なぜかmaximaだけソース提供

覚えるチャンスだProlog

gcd(X, 0, X):- !.
gcd(0, X, X):- !.
gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D).
gcd(X, Y, D):- Z is Y mod X, gcd(X, Z, D).

まさかのダイバーシティー SED

超長かったです

#! /bin/sed -nf

# gcd.sed Copyright (c) 2010        by Paweł Zuzelski <pawelz@pld-linux.org>
# dc.sed  Copyright (c) 1995 - 1997 by Greg Ubben <gsu@romulus.ncsc.mil>

# usage:
#
#     echo N M | ./gcd.sed
#
# Computes the greatest common divisor of N and M integers using euclidean
# algorithm.

s/^/|P|K0|I10|O10|?~/

s/$/ [lalb%sclbsalcsblb0<F]sF sasblFxlap/

:next
s/|?./|?/
s/|?#[	 -}]*/|?/
/|?!*[lLsS;:<>=]\{0,1\}$/N
/|?!*[-+*/%^<>=]/b binop
/^|.*|?[dpPfQXZvxkiosStT;:]/b binop
/|?[_0-9A-F.]/b number
/|?\[/b string
/|?l/b load
/|?L/b Load
/|?[sS]/b save
/|?c/ s/[^|]*//
/|?d/ s/[^~]*~/&&/
/|?f/ s//&[pSbz0<aLb]dSaxsaLa/
/|?x/ s/\([^~]*~\)\(.*|?x\)~*/\2\1/
/|?[KIO]/ s/.*|\([KIO]\)\([^|]*\).*|?\1/\2~&/
/|?T/ s/\.*0*~/~/
#  a slow, non-stackable array implementation in dc, just for completeness
#  A fast, stackable, associative array implementation could be done in sed
#  (format: {key}value{key}value...), but would be longer, like load & save.
/|?;/ s/|?;\([^{}]\)/|?~[s}s{L{s}q]S}[S}l\1L}1-d0>}s\1L\1l{xS\1]dS{xL}/
/|?:/ s/|?:\([^{}]\)/|?~[s}L{s}L{s}L}s\1q]S}S}S{[L}1-d0>}S}l\1s\1L\1l{xS\1]dS{x/
/|?[ ~	cdfxKIOT]/b next
/|?\n/b next
/|?[pP]/b print
/|?k/ s/^\([0-9]\{1,3\}\)\([.~].*|K\)[^|]*/\2\1/
/|?i/ s/^\(-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}\)\(~.*|I\)[^|]*/\2\1/
/|?o/ s/^\(-\{0,1\}[1-9][0-9]*\.\{0,1\}[0-9]*\)\(~.*|O\)[^|]*/\2\1/
/|?[kio]/b pop
/|?t/b trunc
/|??/b input
/|?Q/b break
/|?q/b quit
h
/|?[XZz]/b count
/|?v/b sqrt
s/.*|?\([^Y]\).*/\1 is unimplemented/
s/\n/\\n/g
l
g
b next

:print
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~.*|?p/!b Print
/|O10|/b Print

#  Print a number in a non-decimal output base.  Uses registers a,b,c,d.
#  Handles fractional output bases (O<-1 or O>=1), unlike other dc's.
#  Converts the fraction correctly on negative output bases, unlike
#  UNIX dc.  Also scales the fraction more accurately than UNIX dc.
#
s,|?p,&KSa0kd[[-]Psa0la-]Sad0>a[0P]sad0=a[A*2+]saOtd0>a1-ZSd[[[[ ]P]sclb1\
!=cSbLdlbtZ[[[-]P0lb-sb]sclb0>c1+]sclb0!<c[0P1+dld>c]scdld>cscSdLbP]q]Sb\
[t[1P1-d0<c]scd0<c]ScO_1>bO1!<cO[16]<bOX0<b[[q]sc[dSbdA>c[A]sbdA=c[B]sbd\
B=c[C]sbdC=c[D]sbdD=c[E]sbdE=c[F]sb]xscLbP]~Sd[dtdZOZ+k1O/Tdsb[.5]*[.1]O\
X^*dZkdXK-1+ktsc0kdSb-[Lbdlb*lc+tdSbO*-lb0!=aldx]dsaxLbsb]sad1!>a[[.]POX\
+sb1[SbO*dtdldx-LbO*dZlb!<a]dsax]sadXd0<asbsasaLasbLbscLcsdLdsdLdLak[]pP,
b next

:Print
/|?p/s/[^~]*/&\
~&/
s/\(.*|P\)\([^|]*\)/\
\2\1/
s/\([^~]*\)\n\([^~]*\)\(.*|P\)/\1\3\2/
h
s/~.*//
/./{ s/.//; p; }
#  Just s/.//p would work if we knew we were running under the -n option.
#  Using l vs p would kind of do \ continuations, but would break strings.
g

:pop
s/[^~]*~//
b next

:load
s/\(.*|?.\)\(.\)/\20~\1/
s/^\(.\)0\(.*|r\1\([^~|]*\)~\)/\1\3\2/
s/.//
b next

:Load
s/\(.*|?.\)\(.\)/\2\1/
s/^\(.\)\(.*|r\1\)\([^~|]*~\)/|\3\2/
/^|/!i\
register empty
s/.//
b next

:save
s/\(.*|?.\)\(.\)/\2\1/
/^\(.\).*|r\1/ !s/\(.\).*|/&r\1|/
/|?S/ s/\(.\).*|r\1/&~/
s/\(.\)\([^~]*~\)\(.*|r\1\)[^~|]*~\{0,1\}/\3\2/
b next

:quit
t quit
s/|?[^~]*~[^~]*~/|?q/
t next
#  Really should be using the -n option to avoid printing a final newline.
s/.*|P\([^|]*\).*/\1/
q

:break
s/[0-9]*/&;987654321009;/
:break1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^;]*\3\(9*\).*|?.\)[^~]*~/\1\5\6\4/
t break1
b pop

:input
N
s/|??\(.*\)\(\n.*\)/|?\2~\1/
b next

:count
/|?Z/ s/~.*//
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}$/ s/[-.0]*\([^.]*\)\.*/\1/
/|?X/ s/-*[0-9A-F]*\.*\([0-9A-F]*\).*/\1/
s/|.*//
/~/ s/[^~]//g

s/./a/g
:count1
	s/a\{10\}/b/g
	s/b*a*/&a9876543210;/
	s/a.\{9\}\(.\).*;/\1/
	y/b/a/
/a/b count1
G
/|?z/ s/\n/&~/
s/\n[^~]*//
b next

:trunc
#  for efficiency, doesn't pad with 0s, so 10k 2 5/ returns just .40
#  The X* here and in a couple other places works around a SunOS 4.x sed bug.
s/\([^.~]*\.*\)\(.*|K\([^|]*\)\)/\3;9876543210009909:\1,\2/
:trunc1
	s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^:]*X*\3\(9*\)[^,]*\),\([0-9]\)/\1\5\6\4\7,/
t trunc1
s/[^:]*:\([^,]*\)[^~]*/\1/
b normal

:number
s/\(.*|?\)\(_\{0,1\}[0-9A-F]*\.\{0,1\}[0-9A-F]*\)/\2~\1~/
s/^_/-/
/^[^A-F~]*~.*|I10|/b normal
/^[-0.]*~/b normal
s:\([^.~]*\)\.*\([^~]*\):[Ilb^lbk/,\1\2~0A1B2C3D4E5F1=11223344556677889900;.\2:
:digit
    s/^\([^,]*\),\(-*\)\([0-F]\)\([^;]*\(.\)\3[^1;]*\(1*\)\)/I*+\1\2\6\5~,\2\4/
t digit
s:...\([^/]*.\)\([^,]*\)[^.]*\(.*|?.\):\2\3KSb[99]k\1]SaSaXSbLalb0<aLakLbktLbk:
b next

:string
/|?[^]]*$/N
s/\(|?[^]]*\)\[\([^]]*\)]/\1|{\2|}/
/|?\[/b string
s/\(.*|?\)|{\(.*\)|}/\2~\1[/
s/|{/[/g
s/|}/]/g
b next

:binop
/^[^~|]*~[^|]/ !i\
stack empty
//!b next
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/[^~]*\(.*|?!*[^!=<>]\)/0\1/
/^[^~]*~-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/~[^~]*\(.*|?!*[^!=<>]\)/~0\1/
h
/|?\*/b mul
/|?\//b div
/|?%/b rem
/|?^/b exp

/|?[+-]/ s/^\(-*\)\([^~]*~\)\(-*\)\([^~]*~\).*|?\(-\{0,1\}\).*/\2\4s\3o\1\3\5/
s/\([^.~]*\)\([^~]*~[^.~]*\)\(.*\)/<\1,\2,\3|=-~.0,123456789<></
/^<\([^,]*,[^~]*\)\.*0*~\1\.*0*~/ s/</=/
:cmp1
	s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/
t cmp1
/^<\([^~]*\)\([^~]\)[^~]*~\1\(.\).*|=.*\3.*\2/ s/</>/
/|?/{
	s/^\([<>]\)\(-[^~]*~-.*\1\)\(.\)/\3\2/
	s/^\(.\)\(.*|?!*\)\1/\2!\1/
	s/|?![^!]\(.\)/&l\1x/
	s/[^~]*~[^~]*~\(.*|?\)!*.\(.*\)|=.*/\1\2/
	b next
}
s/\(-*\)\1|=.*/;9876543210;9876543210/
/o-/ s/;9876543210/;0123456789/
s/^>\([^~]*~\)\([^~]*~\)s\(-*\)\(-*o\3\(-*\)\)/>\2\1s\5\4/

s/,\([0-9]*\)\.*\([^,]*\),\([0-9]*\)\.*\([0-9]*\)/\1,\2\3.,\4;0/
:right1
	s/,\([0-9]\)\([^,]*\),;*\([0-9]\)\([0-9]*\);*0*/\1,\2\3,\4;0/
t right1
s/.\([^,]*\),~\(.*\);0~s\(-*\)o-*/\1~\30\2~/

:addsub1
	s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/
	s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
#	  could be done in one s/// if we could have >9 back-refs...
/^~.*~;/!b addsub1

:endbin
s/.\([^,]*\),\([0-9.]*\).*/\1\2/
G
s/\n[^~]*~[^~]*//

:normal
s/^\(-*\)0*\([0-9.]*[0-9]\)[^~]*/\1\2/
s/^[^1-9~]*~/0~/
b next

:mul
s/\(-*\)\([0-9]*\)\.*\([0-9]*\)~\(-*\)\([0-9]*\)\.*\([0-9]*\).*|K\([^|]*\).*/\1\4\2\5.!\3\6,|\2<\3~\5>\6:\7;9876543210009909/

:mul1
    s/![0-9]\([^<]*\)<\([0-9]\{0,1\}\)\([^>]*\)>\([0-9]\{0,1\}\)/0!\1\2<\3\4>/
    /![0-9]/ s/\(:[^;]*\)\([1-9]\)\(0*\)\([^0]*\2\(.\).*X*\3\(9*\)\)/\1\5\6\4/
/<~[^>]*>:0*;/!t mul1

s/\(-*\)\1\([^>]*\).*/;\2^>:9876543210aaaaaaaaa/

:mul2
    s/\([0-9]~*\)^/^\1/
    s/<\([0-9]*\)\(.*[~^]\)\([0-9]*\)>/\1<\2>\3/

    :mul3
	s/>\([0-9]\)\(.*\1.\{9\}\(a*\)\)/\1>\2;9\38\37\36\35\34\33\32\31\30/
	s/\(;[^<]*\)\([0-9]\)<\([^;]*\).*\2[0-9]*\(.*\)/\4\1<\2\3/
	s/a[0-9]/a/g
	s/a\{10\}/b/g
	s/b\{10\}/c/g
    /|0*[1-9][^>]*>0*[1-9]/b mul3

    s/;/a9876543210;/
    s/a.\{9\}\(.\)[^;]*\([^,]*\)[0-9]\([.!]*\),/\2,\1\3/
    y/cb/ba/
/|<^/!b mul2
b endbin

:div
#  CDDET
/^[-.0]*[1-9]/ !i\
divide by 0
//!b pop
s/\(-*\)\([0-9]*\)\.*\([^~]*~-*\)\([0-9]*\)\.*\([^~]*\)/\2.\3\1;0\4.\5;0/
:div1
	s/^\.0\([^.]*\)\.;*\([0-9]\)\([0-9]*\);*0*/.\1\2.\3;0/
	s/^\([^.]*\)\([0-9]\)\.\([^;]*;\)0*\([0-9]*\)\([0-9]\)\./\1.\2\30\4.\5/
t div1
s/~\(-*\)\1\(-*\);0*\([^;]*[0-9]\)[^~]*/~123456789743222111~\2\3/
s/\(.\(.\)[^~]*\)[^9]*\2.\{8\}\(.\)[^~]*/\3~\1/
s,|?.,&SaSadSaKdlaZ+LaX-1+[sb1]Sbd1>bkLatsbLa[dSa2lbla*-*dLa!=a]dSaxsakLasbLb*t,
b next

:rem
s,|?%,&Sadla/LaKSa[999]k*Lak-,
b next

:exp
#  This decimal method is just a little faster than the binary method done
#  totally in dc:  1LaKLb [kdSb*LbK]Sb [[.5]*d0ktdSa<bkd*KLad1<a]Sa d1<a kk*
/^[^~]*\./i\
fraction in exponent ignored
s,[^-0-9].*,;9d**dd*8*d*d7dd**d*6d**d5d*d*4*d3d*2lbd**1lb*0,
:exp1
	s/\([0-9]\);\(.*\1\([d*]*\)[^l]*\([^*]*\)\(\**\)\)/;dd*d**d*\4\3\5\2/
t exp1
G
s,-*.\{9\}\([^9]*\)[^0]*0.\(.*|?.\),\2~saSaKdsaLb0kLbkK*+k1\1LaktsbkLax,
s,|?.,&SadSbdXSaZla-SbKLaLadSb[0Lb-d1lb-*d+K+0kkSb[1Lb/]q]Sa0>a[dk]sadK<a[Lb],
b next

:sqrt
#  first square root using sed:  8k2v at 1:30am Dec 17, 1996
/^-/i\
square root of negative number
/^[-0]/b next
s/~.*//
/^\./ s/0\([0-9]\)/\1/g
/^\./ !s/[0-9][0-9]/7/g
G
s/\n/~/
s,|?.,&K1+k KSbSb[dk]SadXdK<asadlb/lb+[.5]*[sbdlb/lb+[.5]*dlb>a]dsaxsasaLbsaLatLbk K1-kt,
b next

#  END OF GSU dc.sed

待ってましたのSNOBOLだったが。。。

SEDみたいな感じともしかして一緒?

	define('gcd(i,j)')	:(gcd_end)
gcd	?eq(i,0)	:s(freturn)
	?eq(j,0)	:s(freturn)
loop	gcd = remdr(i,j)
	gcd = ?eq(gcd,0) j	:s(return)
	i = j
	j = gcd			:(loop)
gcd_end
	output = gcd(1071,1029)
end

言われてなかったからやんなかっただけで、できますよ? SQL

かなりずるいが、勉強になるからのっける

DROP TABLE tbl;
CREATE TABLE tbl
(
       u       NUMBER,
       v       NUMBER
);
INSERT INTO tbl ( u, v ) VALUES ( 20, 50 );
INSERT INTO tbl ( u, v ) VALUES ( 21, 50 );
INSERT INTO tbl ( u, v ) VALUES ( 21, 51 );
INSERT INTO tbl ( u, v ) VALUES ( 22, 50 );
INSERT INTO tbl ( u, v ) VALUES ( 22, 55 );
commit;
WITH
       FUNCTION gcd ( ui IN NUMBER, vi IN NUMBER )
       RETURN NUMBER
       IS
               u NUMBER := ui;
               v NUMBER := vi;
               t NUMBER;
       BEGIN
               while v > 0
               loop
                       t := u;
                       u := v;
                       v:= MOD(t, v );
               END loop;
               RETURN abs(u);
       END gcd;
       SELECT u, v, gcd ( u, v )
       FROM tbl

もちろんできます、SHELL

gcd() {
	# Calculate $1 % $2 until $2 becomes zero.
	until test 0 -eq "$2"; do
		# Parallel assignment: set -- 1 2
		set -- "$2" "`expr "$1" % "$2"`"
	done
	# Echo absolute value of $1.
	test 0 -gt "$1" && set -- "`expr 0 - "$1"`"
	echo "$1"
}

ほかの言語の供養になるきがしたので、のっけた













お願い致します