fork download
copy 
  1. #include <string.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <time.h>
  5.  
  6. const int MSZ = 3;
  7.  
  8. struct Mat {
  9.   int d[MSZ][MSZ];
  10.  
  11.   Mat() {
  12.     memset(d, 0, sizeof d);
  13.     for (int i = 0; i < MSZ; i++)
  14.       d[i][i] = 1;
  15.   }
  16.  
  17.   void operator*=(const Mat &m2) {
  18.     int res[MSZ][MSZ];
  19.     memset(res, 0, sizeof res);
  20.     for (int i = 0; i < MSZ; i++)
  21.     for (int j = 0; j < MSZ; j++)
  22.     for (int k = 0; k < MSZ; k++)
  23.       res[i][j] += d[i][k] * m2.d[k][j];
  24.     memcpy(d, res, sizeof d);
  25.   }
  26. };
  27.  
  28. Mat pow1(Mat a, int b) {
  29.   Mat res;
  30.   for (; b; b >>= 1, a *= a)
  31.     if (b & 1) res *= a;
  32.   return res;
  33. }
  34.  
  35. Mat pow2(Mat a, int b) {
  36.   if (b == 0) return Mat();
  37.   if (b & 1) {
  38.     Mat res = pow2(a, b - 1);
  39.     res *= a;
  40.     return res;
  41.   }
  42.   Mat res = pow2(a, b >> 1);
  43.   res *= res;
  44.   return res;
  45. }
  46.  
  47. const int POW = 1e9;
  48. const int STEPS = 3e5;
  49.  
  50. int main() {
  51.   Mat src;
  52.   for (int i = 0; i < MSZ; i++)
  53.   for (int j = 0; j < MSZ - i; j++)
  54.     src.d[i][j] = 1;
  55.  
  56.   clock_t st = clock();
  57.   for (int step = 0; step < STEPS; step++)
  58.     pow1(src, POW);
  59.   printf("%d\n", clock() - st);
  60.  
  61.   st = clock();
  62.   for (int step = 0; step < STEPS; step++)
  63.     pow2(src, POW);
  64.   printf("%d\n", clock() - st);  
  65.   return 0;
  66. }
  67.  
Success #stdin #stdout 1.43s 2680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
630000
790000
https://ideone.com/7ez6K
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!