Guest User

python3 c module extention fibonacci using matrix

a guest
Sep 29th, 2018
305
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.41 KB | None | 0 0
  1. #include <Python.h>
  2.  
  3. struct Matrix {
  4.     PyObject *m[2][2];
  5. };
  6.  
  7. static struct Matrix matrix_mult(struct Matrix mat1, const struct Matrix mat2)
  8. {
  9.     struct Matrix matrix;
  10.     PyObject *mults[8];
  11.    
  12.     for (int i = 0; i < 8; i++) {
  13.         mults[i] = PyNumber_Multiply(mat1.m[i/4][i%2], mat2.m[i%2][(i/2)&1]);
  14.     }
  15.  
  16.     for (int i = 0; i < 4; i++) {
  17.         matrix.m[i/2][i%2] = PyNumber_Add(mults[2*i], mults[2*i+1]);
  18.     }
  19.  
  20.    for (int i = 0; i < 8; i++) {
  21.        Py_DECREF(mults[i]);
  22.    }
  23.  
  24.    return matrix;
  25. }
  26.  
  27. static void matrix_free(struct Matrix *matrix)
  28. {
  29.     for (int i = 0; i < 2; i++) {
  30.         for (int j = 0; j < 2; j++) {
  31.             Py_DECREF(matrix->m[i][j]);
  32.         }
  33.     }
  34. }
  35.  
  36. static struct Matrix matrix_pow(struct Matrix matrix, int n)
  37. {
  38.     struct Matrix result = {{
  39.         {PyLong_FromLong(1L), PyLong_FromLong(0L)},
  40.         {PyLong_FromLong(0L), PyLong_FromLong(1L)}
  41.     }};
  42.  
  43.     struct Matrix result_old;
  44.     struct Matrix matrix_old;
  45.  
  46.     while (n > 0) {
  47.         if (n % 2 == 0) {
  48.             n /= 2;
  49.             matrix_old = matrix;
  50.             matrix = matrix_mult(matrix_old, matrix_old);
  51.             matrix_free(&matrix_old);
  52.         } else {
  53.             //n--;
  54.             n /= 2;
  55.             result_old = result;
  56.             matrix_old = matrix;
  57.             result = matrix_mult(result_old, matrix);
  58.             matrix = matrix_mult(matrix_old, matrix_old);
  59.             matrix_free(&result_old);
  60.             matrix_free(&matrix_old);
  61.         }
  62.     }
  63.  
  64.     return result;
  65. }
  66.  
  67. static PyObject *fib_mat(PyObject *self, PyObject *args)
  68. {
  69.     long long int n;
  70.     if(!PyArg_ParseTuple(args, "L", &n))
  71.         return NULL;
  72.  
  73.     struct Matrix fib_matrix = {{
  74.         {PyLong_FromLong(0L), PyLong_FromLong(1L)},
  75.         {PyLong_FromLong(1L), PyLong_FromLong(1L)}
  76.     }};
  77.  
  78.     struct Matrix result = matrix_pow(fib_matrix, n + 1);
  79.  
  80.  
  81.     PyObject *inswer = result.m[0][0];
  82.  
  83.    
  84.     Py_INCREF(inswer);
  85.  
  86.     matrix_free(&result);
  87.     matrix_free(&fib_matrix);
  88.  
  89.     return inswer;
  90. }
  91.  
  92. static PyMethodDef func_table[] = {
  93.     { "fib_mat", fib_mat, METH_VARARGS, "Calculates fib number" },
  94.     { NULL, NULL, 0, NULL }
  95. };
  96.  
  97. static struct PyModuleDef fib_module = {
  98.     PyModuleDef_HEAD_INIT,
  99.     "fib_module",
  100.     "fibonacci Module",
  101.     -1,
  102.     func_table
  103. };
  104.  
  105. PyMODINIT_FUNC PyInit_fib_module(void)
  106. {
  107.     return PyModule_Create(&fib_module);
  108. }
Advertisement
Add Comment
Please, Sign In to add comment