はじめに
CPythonのC拡張を使って素因数分解する方法を紹介します。
この記事の対象者
- ある程度PythonとCの知識があり、PythonのC拡張を使ってみたい。
前提知識
- 基本的なPython/Cの記法と仕様を理解している
実装
Cで書かれたコードをコンパイルしてPython側で呼び出すのでmain.pyとfactorizer.cのふたつのファイルを用意してください。
実際のコード
from factorizer import factorize
print(factorize(11111111111111111)) # [2071723, 5363222357]
#include <Python.h>
#include <math.h>
static PyObject* factorize(PyObject* self, PyObject* args) {
long num;
if (!PyArg_ParseTuple(args, "l", &num)) {
return NULL;
}
if (num <= 0) {
PyErr_SetString(PyExc_ValueError, "Input must be a positive integer");
return NULL;
}
PyObject* factor_list = PyList_New(0);
while (num % 2 == 0) {
PyList_Append(factor_list, PyLong_FromLong(2));
num /= 2;
}
for (long i = 3; i * i <= num; i += 2) {
while (num % i == 0) {
PyList_Append(factor_list, PyLong_FromLong(i));
num /= i;
}
}
if (num > 2) {
PyList_Append(factor_list, PyLong_FromLong(num));
}
return factor_list;
}
static PyMethodDef methods[] = {
{"factorize", factorize, METH_VARARGS, "Factorize a number"},
{NULL, NULL, 0, NULL}
};
static struct PyModuleDef module = {
PyModuleDef_HEAD_INIT,
"factorizer",
NULL,
-1,
methods
};
PyMODINIT_FUNC PyInit_factorizer(void) {
return PyModule_Create(&module);
}
解説
インクルードと定義
#include <Python.h>
#include <math.h>
この部分では、Pythonの拡張機能を使用するために必要なヘッダーファイル <Python.h> をインクルードしています。また、後で使用する数学関数を利用するために <math.h> もインクルードしています。
factorize 関数
static PyObject* factorize(PyObject* self, PyObject* args) {
long num;
if (!PyArg_ParseTuple(args, "l", &num)) {
return NULL;
}
if (num <= 0) {
PyErr_SetString(PyExc_ValueError, "Input must be a positive integer");
return NULL;
}
この部分では、factorize 関数が定義されています。この関数は、Pythonから呼び出される際に使用されます。関数の引数として、PyObject* self と PyObject* args が渡されます。self はメソッドが属するオブジェクト自体を表し、args は関数に渡された引数を表します。
PyArg_ParseTuple 関数は、Pythonから渡された引数をパースしてCの変数に格納します。ここでは、"l" フォーマット文字列を使用して、整数値を表す引数を受け取り、その値を num 変数に格納しています。もし PyArg_ParseTuple が失敗した場合（例えば、引数が整数ではない場合）、NULL を返しています。
もし num が 0 以下のとき、ValueErrorを発生させます。
素因数分解
PyObject* factor_list = PyList_New(0);
while (num % 2 == 0) {
PyList_Append(factor_list, PyLong_FromLong(2));
num /= 2;
}
for (long i = 3; i * i <= num; i += 2) {
while (num % i == 0) {
PyList_Append(factor_list, PyLong_FromLong(i));
num /= i;
}
}
if (num > 2) {
PyList_Append(factor_list, PyLong_FromLong(num));
}
この部分では、与えられた整数 num を素因数分解しています。factor_list という新しいリストオブジェクトを作成し、素因数を格納します。
まず、2で割り切れるだけ割っていきます。次に、3以上の奇数で割り切れるだけ割っていきます。素因数を見つけるたびに、それを factor_list リストに追加しています。
最後に、num が2より大きい場合、それ自身も素数である可能性があるので、factor_list に追加しています。
多分もっといい方法があると思います。
PyMethodDef 構造体
static PyMethodDef methods[] = {
{"factorize", factorize, METH_VARARGS, "Factorize a number"},
{NULL, NULL, 0, NULL}
};
この部分では、Pythonから呼び出せる関数のリストを定義しています。各要素は、関数の名前、その関数を実行するためのポインタ、引数の形式、関数の説明を示しています。最後の要素は必ず {NULL, NULL, 0, NULL} で終わります。
PyModuleDef 構造体
static struct PyModuleDef module = {
PyModuleDef_HEAD_INIT,
"factorizer",
NULL,
-1,
methods
};
この部分では、拡張モジュールの定義を行っています。PyModuleDef_HEAD_INIT は、この構造体を初期化するためのマクロです。"factorizer" はモジュールの名前を示しています。methods は、先ほど定義した関数のリストです。
PyInit_factorizer 関数
PyMODINIT_FUNC PyInit_factorizer(void) {
return PyModule_Create(&module);
}
この部分では、モジュールを初期化するための関数が定義されています。この関数は、Pythonがこのモジュールをロードする際に呼び出されます。PyModule_Create 関数を使用して、先ほど定義した module を基にモジュールオブジェクトを作成し、それを返しています。
コンパイル
gcc -shared -o factorizer.so factorizer.o $(python3-config --ldflags)
gcc(GNU Compiler Collection)を使ってコンパイルを行い、共有ライブラリファイル(.so)として出力します。
終わりに
最後まで読んで頂きありがとうございます。不備があれば是非コメントで指摘して下さい。