「ユークリッドステア」または「PostgreSQLを使用したGCDのカウント」

どういうわけか、誰かDavid FetterがPostgreSQLを使用して2つの数値のGCD （同名の同胞ではなく、最大公約数）を計算する方法についての投稿を書いています 。 そして彼はそれを「迅速な方法」と呼びました。

WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .

1. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
2. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
3. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
4. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
5. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
6. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
7. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   
8. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
   
   
   
   

WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .

しかし、大学で正直に5年間座っていた私の熱心な性質は、意見の相違を望みました。 これから、実際、私の研究が始まりました。



まず第一に、非常に簡単なオプション：

1. 再帰 t（a、b） AS （
2. 値 （ 38、12 ）
3. UNION ALL
4. SELECT b、mod（a、b） FROM t
5. WHERE b> 0
6. ）
7. SELECT a AS gcd FROM t WHERE b = 0;

*このソースコードは、 ソースコードハイライターで強調表示されました。

多くの人がこの実装で有名なユークリッドアルゴリズムを認識すると確信しています。 この特定の例では、2であるGCD（38、12）を見つけます。



この奇跡の将来の使用を促進し促進するために、関数を書くことが決定されました。

1. 関数の作成 または置換 gcd（bigint、bigint）は、bigint ASを返します
2. $$
3. 再帰 t（a、b） AS （
4. 値 （abs（$ 1）:: bigint、abs（$ 2）:: bigint）
5. UNION ALL
6. SELECT b、mod（a、b） FROM t
7. WHERE b> 0
8. ）
9. SELECT a AS gcd FROM t WHERE b = 0;
10. $$
11. 不変
12. 厳密
13. LANGUAGE SQL ;

*このソースコードは、 ソースコードハイライターで強調表示されました。

いくつかの改善に注意してください：

• 型bigintの関数は機能し、int8です。
• 入力パラメータは、避けるために直ちにモジュロになります。
• この関数はIMMUTABLEとしてマークされています。これにより、オプティマイザーの操作が楽になります。これは、同じ入力データに対して同じ結果が返されることを意味するためです。
• 関数はSTRICTとしてマークされます。つまり、少なくとも1つの引数がNULLの場合、結果はNULLになります。

これらすべての結果として、 wiki.postgresql.orgで私の作品を不滅にするのに十分でした 。



このオプスが理解されている場合、 NOC （最小一般倍数）の計算方法に関する続きがあります。