fork(1) download
copy 
  1. #define PRIu64 "llu"
  2.  
  3. #include <stdio.h>
  4. #include <stdint.h>
  5. #include <math.h>
  6.  
  7. //
  8. // ひたすら足し算の方法
  9. //
  10. uint64_t fibonacci_z(unsigned int n_) {
  11.  
  12. 	switch (n_) {
  13. 		case 0:
  14. 			return 0;
  15. 		case 1:
  16. 			return 1;
  17. 		default: {
  18.  
  19. 			uint64_t u_l = 0;
  20. 			uint64_t u_r = 1;
  21. 			uint64_t u_y = 1;
  22.  
  23. 			for (unsigned int i = 1; i < n_; ++i) {
  24. 				u_y += u_l;
  25. 				u_l = u_r;
  26. 				u_r = u_y;
  27. 			}
  28. 			return u_y;
  29. 		}
  30. 	}
  31. }
  32.  
  33. //
  34. // 一般項
  35. //
  36. uint64_t fibonacci_f(unsigned int n_) {
  37. 	const long double r_r5 = sqrtl((long double)5.0);
  38. 	const long double r_phi = ((long double)1.0 + r_r5) / (long double)2.0;
  39. 	long double r_fibonacci = ((powl(r_phi, (long double)n_) - powl((long double)1.0 - r_phi, (long double)n_)) / r_r5);
  40. 	return (uint64_t)(r_fibonacci + 0.5);
  41. }
  42.  
  43. // 再帰階乗計算
  44. // https://w...content-available-to-author-only...i.edu/~eppstein/161/960109.html
  45. // This is a recursive algorithm, so as usual we get a recurrence relation defining time,
  46. // just by writing down the time spent in a call to matpow (O(1)) plus the time in each recursive call
  47. // (only one recursive call, with argument n/2). So the recurrence is
  48. //
  49. //    time(n) = O(1) + time(n / 2)
  50.  
  51. typedef uint64_t Muint64_2x2_t[2][2];
  52.  
  53. static void matpow(Muint64_2x2_t M_, unsigned int n_) {
  54.  
  55. 	static Muint64_2x2_t const IM = { {1, 1}, {1, 0} };
  56. 	static Muint64_2x2_t TM;
  57.  
  58.     if (n_ > 1) {
  59. 		matpow(M_, n_ >> 1);
  60.  
  61. 		// M = M * M;
  62. 		TM[0][0] = M_[0][0] * M_[0][0] + M_[0][1] * M_[1][0];
  63. 		TM[0][1] = M_[0][0] * M_[0][1] + M_[0][1] * M_[1][1];
  64. 		TM[1][0] = M_[1][0] * M_[0][0] + M_[1][1] * M_[1][0];
  65. 		TM[1][1] = M_[1][0] * M_[0][1] + M_[1][1] * M_[1][1];
  66.  
  67. 		M_[0][0] = TM[0][0];
  68. 		M_[0][1] = TM[0][1];
  69. 		M_[1][0] = TM[1][0];
  70. 		M_[1][1] = TM[1][1];
  71. 	}
  72.  
  73. 	if (n_ & 1) {
  74. 		// M = M * IM;
  75. 		TM[0][0] = M_[0][0] * IM[0][0] + M_[0][1] * IM[1][0];
  76. 		TM[0][1] = M_[0][0] * IM[0][1] + M_[0][1] * IM[1][1];
  77. 		TM[1][0] = M_[1][0] * IM[0][0] + M_[1][1] * IM[1][0];
  78. 		TM[1][1] = M_[1][0] * IM[0][1] + M_[1][1] * IM[1][1];
  79.  
  80. 		M_[0][0] = TM[0][0];
  81. 		M_[0][1] = TM[0][1];
  82. 		M_[1][0] = TM[1][0];
  83. 		M_[1][1] = TM[1][1];
  84. 	}
  85. }
  86.  
  87. uint64_t fibonacci_m(unsigned int n_) {
  88.  
  89. 	switch (n_) {
  90. 		case 0:
  91. 			return 0;
  92. 		case 1:
  93. 			return 1;
  94. 		default: {
  95.  
  96. 			Muint64_2x2_t M = { {1, 0}, {0, 1} };
  97. 			matpow(M, n_ - 1);
  98. 			return M[0][0];
  99. 		}
  100. 	}
  101.  
  102. }
  103.  
  104. // ｱﾎが書いたｺｰﾄﾞ
  105. // t は 0 のまま
  106. // a は 1 のまま
  107. // b は 0 のまま
  108. // なにをやってるかは不明
  109. uint64_t fibonacci_aho(unsigned int n) {
  110. 	n++;
  111. 	uint64_t a = 1;
  112. 	uint64_t b = 0;
  113. 	uint64_t t;
  114. 	for (int i = 0 ; i < 64 ; i++) {
  115. 		t = b * b; // t ← 0 = 0 * 0
  116. 		b = 2 * a * b + t; // t ← 0 = 2 * 1 * 0 + 0
  117. 		a = a * a + t; // a ← 1 = 1 * 1 + 0
  118. 		if (n & 0x8000000000000000) {
  119. 			// ﾏｲﾅｽにはならない ここはとおらない
  120. 			t = b;
  121. 			b = a + b;
  122. 			a = t;
  123. 		}
  124. 		n += n; // 一切使わない総和(1～n)を求めてる
  125. 	}
  126. 	return a;
  127. }
  128.  
  129. int main(int argc, char* argv[]) {
  130.  
  131. 	for (unsigned int i = 0; i < 94; ++i) {
  132. 		printf ("n = %d (z)%" PRIu64 " (f)%" PRIu64 " (m)%" PRIu64 " (aho)%" PRIu64 "\n", i, fibonacci_z(i), fibonacci_f(i), fibonacci_m(i), fibonacci_aho(i));
  133. 	}
  134. 	getchar();
  135. 	return 0;
  136. }
  137.  
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n = 0 (z)0 (f)0 (m)0 (aho)1
n = 1 (z)1 (f)1 (m)1 (aho)1
n = 2 (z)1 (f)1 (m)1 (aho)1
n = 3 (z)2 (f)2 (m)2 (aho)1
n = 4 (z)3 (f)3 (m)3 (aho)1
n = 5 (z)5 (f)5 (m)5 (aho)1
n = 6 (z)8 (f)8 (m)8 (aho)1
n = 7 (z)13 (f)13 (m)13 (aho)1
n = 8 (z)21 (f)21 (m)21 (aho)1
n = 9 (z)34 (f)34 (m)34 (aho)1
n = 10 (z)55 (f)55 (m)55 (aho)1
n = 11 (z)89 (f)89 (m)89 (aho)1
n = 12 (z)144 (f)144 (m)144 (aho)1
n = 13 (z)233 (f)233 (m)233 (aho)1
n = 14 (z)377 (f)377 (m)377 (aho)1
n = 15 (z)610 (f)610 (m)610 (aho)1
n = 16 (z)987 (f)987 (m)987 (aho)1
n = 17 (z)1597 (f)1597 (m)1597 (aho)1
n = 18 (z)2584 (f)2584 (m)2584 (aho)1
n = 19 (z)4181 (f)4181 (m)4181 (aho)1
n = 20 (z)6765 (f)6765 (m)6765 (aho)1
n = 21 (z)10946 (f)10946 (m)10946 (aho)1
n = 22 (z)17711 (f)17711 (m)17711 (aho)1
n = 23 (z)28657 (f)28657 (m)28657 (aho)1
n = 24 (z)46368 (f)46368 (m)46368 (aho)1
n = 25 (z)75025 (f)75025 (m)75025 (aho)1
n = 26 (z)121393 (f)121393 (m)121393 (aho)1
n = 27 (z)196418 (f)196418 (m)196418 (aho)1
n = 28 (z)317811 (f)317811 (m)317811 (aho)1
n = 29 (z)514229 (f)514229 (m)514229 (aho)1
n = 30 (z)832040 (f)832040 (m)832040 (aho)1
n = 31 (z)1346269 (f)1346269 (m)1346269 (aho)1
n = 32 (z)2178309 (f)2178309 (m)2178309 (aho)1
n = 33 (z)3524578 (f)3524578 (m)3524578 (aho)1
n = 34 (z)5702887 (f)5702887 (m)5702887 (aho)1
n = 35 (z)9227465 (f)9227465 (m)9227465 (aho)1
n = 36 (z)14930352 (f)14930352 (m)14930352 (aho)1
n = 37 (z)24157817 (f)24157817 (m)24157817 (aho)1
n = 38 (z)39088169 (f)39088169 (m)39088169 (aho)1
n = 39 (z)63245986 (f)63245986 (m)63245986 (aho)1
n = 40 (z)102334155 (f)102334155 (m)102334155 (aho)1
n = 41 (z)165580141 (f)165580141 (m)165580141 (aho)1
n = 42 (z)267914296 (f)267914296 (m)267914296 (aho)1
n = 43 (z)433494437 (f)433494437 (m)433494437 (aho)1
n = 44 (z)701408733 (f)701408733 (m)701408733 (aho)1
n = 45 (z)1134903170 (f)1134903170 (m)1134903170 (aho)1
n = 46 (z)1836311903 (f)1836311903 (m)1836311903 (aho)1
n = 47 (z)2971215073 (f)2971215073 (m)2971215073 (aho)1
n = 48 (z)4807526976 (f)4807526976 (m)4807526976 (aho)1
n = 49 (z)7778742049 (f)7778742049 (m)7778742049 (aho)1
n = 50 (z)12586269025 (f)12586269025 (m)12586269025 (aho)1
n = 51 (z)20365011074 (f)20365011074 (m)20365011074 (aho)1
n = 52 (z)32951280099 (f)32951280099 (m)32951280099 (aho)1
n = 53 (z)53316291173 (f)53316291173 (m)53316291173 (aho)1
n = 54 (z)86267571272 (f)86267571272 (m)86267571272 (aho)1
n = 55 (z)139583862445 (f)139583862445 (m)139583862445 (aho)1
n = 56 (z)225851433717 (f)225851433717 (m)225851433717 (aho)1
n = 57 (z)365435296162 (f)365435296162 (m)365435296162 (aho)1
n = 58 (z)591286729879 (f)591286729879 (m)591286729879 (aho)1
n = 59 (z)956722026041 (f)956722026041 (m)956722026041 (aho)1
n = 60 (z)1548008755920 (f)1548008755920 (m)1548008755920 (aho)1
n = 61 (z)2504730781961 (f)2504730781961 (m)2504730781961 (aho)1
n = 62 (z)4052739537881 (f)4052739537881 (m)4052739537881 (aho)1
n = 63 (z)6557470319842 (f)6557470319842 (m)6557470319842 (aho)1
n = 64 (z)10610209857723 (f)10610209857723 (m)10610209857723 (aho)1
n = 65 (z)17167680177565 (f)17167680177565 (m)17167680177565 (aho)1
n = 66 (z)27777890035288 (f)27777890035288 (m)27777890035288 (aho)1
n = 67 (z)44945570212853 (f)44945570212853 (m)44945570212853 (aho)1
n = 68 (z)72723460248141 (f)72723460248141 (m)72723460248141 (aho)1
n = 69 (z)117669030460994 (f)117669030460994 (m)117669030460994 (aho)1
n = 70 (z)190392490709135 (f)190392490709135 (m)190392490709135 (aho)1
n = 71 (z)308061521170129 (f)308061521170129 (m)308061521170129 (aho)1
n = 72 (z)498454011879264 (f)498454011879264 (m)498454011879264 (aho)1
n = 73 (z)806515533049393 (f)806515533049393 (m)806515533049393 (aho)1
n = 74 (z)1304969544928657 (f)1304969544928657 (m)1304969544928657 (aho)1
n = 75 (z)2111485077978050 (f)2111485077978050 (m)2111485077978050 (aho)1
n = 76 (z)3416454622906707 (f)3416454622906707 (m)3416454622906707 (aho)1
n = 77 (z)5527939700884757 (f)5527939700884757 (m)5527939700884757 (aho)1
n = 78 (z)8944394323791464 (f)8944394323791464 (m)8944394323791464 (aho)1
n = 79 (z)14472334024676221 (f)14472334024676221 (m)14472334024676221 (aho)1
n = 80 (z)23416728348467685 (f)23416728348467685 (m)23416728348467685 (aho)1
n = 81 (z)37889062373143906 (f)37889062373143906 (m)37889062373143906 (aho)1
n = 82 (z)61305790721611591 (f)61305790721611591 (m)61305790721611591 (aho)1
n = 83 (z)99194853094755497 (f)99194853094755497 (m)99194853094755497 (aho)1
n = 84 (z)160500643816367088 (f)160500643816367088 (m)160500643816367088 (aho)1
n = 85 (z)259695496911122585 (f)259695496911122585 (m)259695496911122585 (aho)1
n = 86 (z)420196140727489673 (f)420196140727489673 (m)420196140727489673 (aho)1
n = 87 (z)679891637638612258 (f)679891637638612258 (m)679891637638612258 (aho)1
n = 88 (z)1100087778366101931 (f)1100087778366101931 (m)1100087778366101931 (aho)1
n = 89 (z)1779979416004714189 (f)1779979416004714189 (m)1779979416004714189 (aho)1
n = 90 (z)2880067194370816120 (f)2880067194370816121 (m)2880067194370816120 (aho)1
n = 91 (z)4660046610375530309 (f)4660046610375530310 (m)4660046610375530309 (aho)1
n = 92 (z)7540113804746346429 (f)7540113804746346431 (m)7540113804746346429 (aho)1
n = 93 (z)12200160415121876738 (f)12200160415121876740 (m)12200160415121876738 (aho)1
https://ideone.com/vhpLPV
language:
C (gcc 8.3)
created:
5 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!