fork download
copy 
  1. import time
  2.  
  3.  
  4. def mul(m1, m2):
  5.     (a1, b1),\
  6.     (c1, d1) = m1
  7.  
  8.     (a2, b2),\
  9.     (c2, d2) = m2
  10.  
  11.     return [[a1 * a2 + b1 * c2, a1 * b2 + b1 * d2],
  12.             [c1 * a2 + d1 * c2, c1 * b2 + d1 * d2]]
  13.  
  14.  
  15. def mod(m, n):
  16.     (a, b),\
  17.     (c, d) = m
  18.  
  19.     return [[a % n, b % n],
  20.             [c % n, d % n]]
  21.  
  22.  
  23. fib_generator = [[1, 1],
  24.                  [1, 0]]
  25.  
  26.  
  27. one = [[1, 0],
  28.        [0, 1]]
  29.  
  30.  
  31. def modpow_log(m, p, n):
  32.     binary_power = list("{0:b}".format(p))
  33.     res = one
  34.     mm = m
  35.     for b in reversed(binary_power):
  36.         if b == '1':
  37.             res = mod(mul(res, mm), n)
  38.  
  39.         mm = mod(mul(mm, mm), n)
  40.  
  41.     return res
  42.  
  43.  
  44. def fib_linear(x):
  45.     if x < 2:
  46.         return 1
  47.  
  48.     a = 1
  49.     b = 1
  50.     for i in xrange(x - 2):
  51.         c = a + b
  52.         a = b
  53.         b = c
  54.  
  55.     return b
  56.  
  57.  
  58. def modfib_mat_log(x, n):
  59.     return modpow_log(fib_generator, x - 1, n)[0][0]
  60.  
  61. N = 123456
  62. M = 12345
  63.  
  64. print "Linear algo, N =", N, "M =", M
  65. start = time.clock()
  66. print fib_linear(N) % M
  67. end = time.clock()
  68. print "time:", end - start
  69.  
  70. print "Log algo, N =", N, "M =", M
  71. start = time.clock()
  72. print modfib_mat_log(N, M)
  73. end = time.clock()
  74. print "time:", end - start
  75.  
  76. N = 123456789012345678
  77. print "Log algo, N =", N, "M =", M
  78. start = time.clock()
  79. print modfib_mat_log(N, M)
  80. end = time.clock()
  81. print "time:", end - start
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
Success #stdin #stdout 0.62s 8968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Linear algo, N = 123456 M = 12345
1122
time: 0.606475
Log algo, N = 123456 M = 12345
1122
time: 0.000113
Log algo, N = 123456789012345678 M = 12345
10499
time: 0.000263
https://ideone.com/V5CrsQ
language:
Python (cpython 2.7.16)
created:
8 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!