Kuina-chan

くいなちゃん2018年12月11日


プログラミング言語Kuin」の言語仕様106、「mathライブラリ」についてです。

1mathライブラリ

数学、科学、高度なアルゴリズムに関するライブラリ「math.kn」を解説します。
名前 説明
math@bellmanFord 有向グラフの最短経路をベルマン・フォード法で求める関数
math@dijkstra 有向グラフの最短経路をダイクストラ法で求める関数
math@fact 階乗をfloatで求める関数
math@factInt 階乗をintで求める関数
math@floydWarshall 有向グラフの最短経路をワーシャル・フロイド法で求める関数
math@gamma ガンマ関数
math@gcd 最大公約数を求める関数
math@knapsack ナップサック問題を解く関数
math@lcm 最小公倍数を求める関数
math@modMul オーバーフローさせずに乗算の剰余を求める関数
math@modPow オーバーフローさせずに冪の剰余を求める関数
math@prime 素数かどうかを高速に判定する関数
math@primeFactors 素因数分解を高速に行う関数

2math@bellmanFord

「math@bellmanFord」は、有向グラフの最短経路をベルマン・フォード法で求める関数です。

func bellmanFord(nodeNum: int, fromNodes: []int, toNodes: []int, values: []int, beginNode: int): []int

nodeNum ノードの数(ノードには0以上nodeNum未満の番号がつけられる)
fromNodes エッジの開始ノード
toNodes エッジの終端ノード
values エッジのコスト
beginNode 経路の開始地点のノード
戻り値 beginNodeから各ノードへの最小のコスト
fromNodesとtoNodesとvaluesの要素数は一致しなければなりません。
この関数は、valuesに負の値が含まれていても正しく計算できます。 valuesに負の値が含まれない場合はmath@dijkstra関数のほうが高速です。

3math@dijkstra

「math@dijkstra」は、有向グラフの最短経路をダイクストラ法で求める関数です。

func dijkstra(nodeNum: int, fromNodes: []int, toNodes: []int, values: []int, beginNode: int): []int

nodeNum ノードの数(ノードには0以上nodeNum未満の番号がつけられる)
fromNodes エッジの開始ノード
toNodes エッジの終端ノード
values エッジのコスト
beginNode 経路の開始地点のノード
戻り値 beginNodeから各ノードへの最小のコスト
fromNodesとtoNodesとvaluesの要素数は一致しなければなりません。
valuesに負の値が含まれてはいけません。 valuesに負の値が含まれる場合はmath@bellmanFord関数を使う必要があります。

4math@fact

「math@fact」は、階乗をfloatで求める関数です。

func fact(n: float): float

n 任意の値
戻り値 「n!」の値
この関数は、「n!=n×(n-1)!」が成り立つように階乗を実数に拡張しており、ガンマ関数を用いて「n!=Γ(n+1)」と定義されています。

5math@factInt

「math@factInt」は、階乗をintで求める関数です。

func factInt(n: int): int

n 任意の値
戻り値 「n!」の値
nが負の場合は未定義で、nが21以上になるとオーバーフローするため、nは0以上20以下の範囲で指定する必要があります。
表5-1: math@factIntの例外
発生条件 ビルド 例外コード
(16進数)
nが0未満 dbgのみ E9170006
nが21以上 dbgのみ E9170003
  • すべてのnに対する結果を保持しているため、この関数は瞬時に値を返す。
図5-1: math@factIntの仕様

6math@floydWarshall

「math@floydWarshall」は、有向グラフの最短経路をワーシャル・フロイド法で求める関数です。

func floydWarshall(nodeNum: int, fromNodes: []int, toNodes: []int, values: []int): [][]int

nodeNum ノードの数(ノードには0以上nodeNum未満の番号がつけられる)
fromNodes エッジの開始ノード
toNodes エッジの終端ノード
values エッジのコスト
戻り値 各ノードから各ノードへの最小のコスト
fromNodesとtoNodesとvaluesの要素数は一致しなければなりません。
この関数は、valuesに負の値が含まれていても正しく計算できます。
例えば戻り値を「d」とすると、ノード2からノード5への最小コストは「d[2][5]」に格納されています。

7math@gamma

「math@gamma」は、ガンマ関数です。

func gamma(n: float): float

n 任意の値
戻り値 「Γ(n)」の値

8math@gcd

「math@gcd」は、最大公約数を求める関数です。

func gcd(a: int, b: int): int

a 整数1
b 整数2
戻り値 aとbの最大公約数
aとbのどちらかは0以外でなければなりません。 aやbが負の場合は、絶対値の最大公約数に等しいです。 すなわち、
表8-1: math@gcdの例外
発生条件 ビルド 例外コード
(16進数)
aとbがともに0 dbgのみ E9170006

9math@knapsack

「math@knapsack」は、ナップサック問題を解く関数です。

func knapsack(weights: []int, values: []int, maxWeight: int, reuse: bool): int

weights 物の重さ
weights 物の価値
maxWeight ナップサックに入る最大の重さ
reuse 物を複数回利用できるならtrue、1回ずつしか利用できないならfalse
戻り値 ナップサックに入りうる最大の価値
weightsとvaluesの要素数は一致しなければなりません。

10math@lcm

「math@lcm」は、最小公倍数を求める関数です。

func lcm(a: int, b: int): int

a 整数1
b 整数2
戻り値 aとbの最小公倍数
aとbのどちらかは0以外でなければなりません。 aやbが負の場合は、絶対値の最小公倍数に等しいです。 すなわち、
表10-1: math@lcmの例外
発生条件 ビルド 例外コード
(16進数)
aとbがともに0 dbgのみ E9170006

11math@modMul

「math@modMul」は、オーバーフローさせずに乗算の剰余を求める関数です。

func modMul(a: int, b: int, modulus: int): int

a 整数1
b 整数2
modulus 除算する値
戻り値 「a*b%modulus」に相当する値
単に「a*b%modulus」を計算すると、大きな値のときにオーバーフローして正確な結果が求まりませんが、この関数はオーバーフローを回避して計算するため正確な値が求まります。

12math@modPow

「math@modPow」は、オーバーフローさせずに冪の剰余を求める関数です。

func modPow(value: int, exponent: int, modulus: int): int

value 整数1
exponent 整数2
modulus 除算する値
戻り値 「value^exponent%modulus」に相当する値
単に「value^exponent%modulus」を計算すると、大きな値のときにオーバーフローして正確な結果が求まりませんが、この関数はオーバーフローを回避して計算するため正確な値が求まります。

13math@prime

「math@prime」は、素数かどうかを高速に判定する関数です。

func prime(n: int): bool

n 整数
戻り値 nが素数ならtrue、素数でなければfalse
  • ミラー・ラビン素数判定法と素数バッファを併用し、誤りのない素数判定を高速に行う。
図13-1: math@primeの仕様

14math@primeFactors

「math@primeFactors」は、素因数分解を高速に行う関数です。

func primeFactors(n: int): []int

n 整数
戻り値 nの素因数
戻り値の配列には、nの素因数が昇順に格納されます。 例えばnが18のとき、戻り値は「[2, 3, 3]」になります。
  • ポラード・ロー素因数分解法の改良版を繰り返し適用し、誤りのない素因数分解を高速に行う。
図14-1: math@primeFactorsの仕様
1544533478jaf