Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <Python.h>
- struct Matrix {
- PyObject *m[2][2];
- };
- static struct Matrix matrix_mult(struct Matrix mat1, const struct Matrix mat2)
- {
- struct Matrix matrix;
- PyObject *mults[8];
- for (int i = 0; i < 8; i++) {
- mults[i] = PyNumber_Multiply(mat1.m[i/4][i%2], mat2.m[i%2][(i/2)&1]);
- }
- for (int i = 0; i < 4; i++) {
- matrix.m[i/2][i%2] = PyNumber_Add(mults[2*i], mults[2*i+1]);
- }
- for (int i = 0; i < 8; i++) {
- Py_DECREF(mults[i]);
- }
- return matrix;
- }
- static void matrix_free(struct Matrix *matrix)
- {
- for (int i = 0; i < 2; i++) {
- for (int j = 0; j < 2; j++) {
- Py_DECREF(matrix->m[i][j]);
- }
- }
- }
- static struct Matrix matrix_pow(struct Matrix matrix, int n)
- {
- struct Matrix result = {{
- {PyLong_FromLong(1L), PyLong_FromLong(0L)},
- {PyLong_FromLong(0L), PyLong_FromLong(1L)}
- }};
- struct Matrix result_old;
- struct Matrix matrix_old;
- while (n > 0) {
- if (n % 2 == 0) {
- n /= 2;
- matrix_old = matrix;
- matrix = matrix_mult(matrix_old, matrix_old);
- matrix_free(&matrix_old);
- } else {
- //n--;
- n /= 2;
- result_old = result;
- matrix_old = matrix;
- result = matrix_mult(result_old, matrix);
- matrix = matrix_mult(matrix_old, matrix_old);
- matrix_free(&result_old);
- matrix_free(&matrix_old);
- }
- }
- return result;
- }
- static PyObject *fib_mat(PyObject *self, PyObject *args)
- {
- long long int n;
- if(!PyArg_ParseTuple(args, "L", &n))
- return NULL;
- struct Matrix fib_matrix = {{
- {PyLong_FromLong(0L), PyLong_FromLong(1L)},
- {PyLong_FromLong(1L), PyLong_FromLong(1L)}
- }};
- struct Matrix result = matrix_pow(fib_matrix, n + 1);
- PyObject *inswer = result.m[0][0];
- Py_INCREF(inswer);
- matrix_free(&result);
- matrix_free(&fib_matrix);
- return inswer;
- }
- static PyMethodDef func_table[] = {
- { "fib_mat", fib_mat, METH_VARARGS, "Calculates fib number" },
- { NULL, NULL, 0, NULL }
- };
- static struct PyModuleDef fib_module = {
- PyModuleDef_HEAD_INIT,
- "fib_module",
- "fibonacci Module",
- -1,
- func_table
- };
- PyMODINIT_FUNC PyInit_fib_module(void)
- {
- return PyModule_Create(&fib_module);
- }
Advertisement
Add Comment
Please, Sign In to add comment