fork(3) download
copy 
  1. // https://i...content-available-to-author-only...e.com/6BG7hf
  2. // 2^(expn2)を有効数字disp10桁の10進数で指数表示する。
  3. // Usage: print_by_decimal <expn2> <disp10>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stdint.h>
  7. #include <assert.h>
  8. #include <vector>
  9. #include <utility>
  10.  
  11. #include <time.h>
  12.  
  13. // 指数の型
  14. typedef uint64_t expn_t;
  15.  
  16. // 2乗したものを足し合わせてもuint64_tが桁あふれしない10進数
  17. #define BIG_DECIMAL		10000000ULL
  18.  
  19. static_assert(UINT64_MAX - (BIG_DECIMAL - 1) * (BIG_DECIMAL - 1) >= 2 * (BIG_DECIMAL - 1), "*** ERR ***");
  20. static_assert(2 * (BIG_DECIMAL - 1) + (BIG_DECIMAL - 1) * (BIG_DECIMAL - 1) <= UINT64_MAX, "*** ERR ***");
  21.  
  22. namespace
  23. {
  24. 	/// 先頭の0を切り詰めたサイズを返す。
  25. 	size_t truncated_size(const std::vector<uint32_t>& mbuf)
  26. 	{
  27. 		const size_t sz = mbuf.size();
  28. 		for (size_t i = sz; i > 0; i--) {
  29. 			if (mbuf[i - 1] != 0UL) {
  30. 				return i;
  31. 			}
  32. 		}
  33. 		return sz;
  34. 	}
  35.  
  36. 	/// 乗算
  37. 	/// メモリ消費を半分にするため、キャリー伝搬を単純に桁の積和の都度行う。
  38. 	std::vector<uint32_t> mlen_mul(const std::vector<uint32_t>& lhs, const std::vector<uint32_t>& rhs)
  39. 	{
  40. 		const size_t sz_lhs = truncated_size(lhs);
  41. 		const size_t sz_rhs = truncated_size(rhs);
  42.  
  43. 		std::vector<uint32_t> mbuf(sz_lhs + sz_rhs, 0UL);
  44. 		for (expn_t i = 0; i < sz_lhs; i++) {
  45. 			uint32_t cy = 0UL;
  46. 			for (expn_t j = 0; j < sz_rhs; j++) {
  47. 				const uint64_t val64 = (uint64_t)mbuf[i + j] + (uint64_t)lhs[i] * (uint64_t)rhs[j] + (uint64_t)cy;
  48. 				cy = (uint32_t)(val64 / BIG_DECIMAL);
  49. 				mbuf[i + j] = (uint32_t)(val64 - cy * BIG_DECIMAL);
  50. 			}
  51. 			{
  52. 				const expn_t j = sz_rhs;
  53. 				const uint64_t val64 = (uint64_t)mbuf[i + j] + (uint64_t)cy;
  54. 				cy = (uint32_t)(val64 / BIG_DECIMAL);
  55. 				mbuf[i + j] = (uint32_t)(val64 - cy * BIG_DECIMAL);
  56. 				assert(cy == 0UL);
  57. 			}
  58. 		}
  59.  
  60. 		return mbuf;
  61. 	}
  62.  
  63. 	/// 2^nをBIG_DECIMAL進数で計算する。
  64. 	std::vector<uint32_t> pow2(const expn_t n_)
  65. 	{
  66. 		const time_t startTmg = time(NULL);
  67.  
  68. 		std::vector<uint32_t> mbuf((size_t)1, 1UL);
  69. 		std::vector<uint32_t> mbuf_work((size_t)1, 2UL);
  70. 		expn_t n = n_;
  71. 		for (;;) {
  72. 			if ((n & 0x1) != 0) {
  73. 				mbuf = mlen_mul(mbuf, mbuf_work);
  74. 			}
  75. 			const time_t now = time(NULL);
  76. 			printf("n=%llu, mbuf sz=%zu --- %lld sec\n", n, mbuf.size(), now - startTmg);
  77. 			n >>= 1;
  78. 			if (n == 0ULL) {
  79. 				break;
  80. 			}
  81. 			mbuf_work = mlen_mul(mbuf_work, mbuf_work);
  82. 		}
  83. 		return mbuf;
  84. 	}
  85.  
  86. }	// namespace
  87.  
  88. int main(const int argc, char* argv[])
  89. {
  90. 	// 2のべきの指数
  91. 	//expn_t expn2 = 1717986918;
  92. 	//expn_t expn2 = 171798;
  93. 	expn_t expn2 = 1000;
  94. 	//expn_t expn2 = 64;
  95. 	//expn_t expn2 = 32;
  96. 	//expn_t expn2 = 16;
  97. 	//expn_t expn2 = 8;
  98. 	//expn_t expn2 = 0;
  99.  
  100. 	// 表示桁数(有効数字)
  101. 	expn_t disp10 = 64;
  102.  
  103. #ifdef _WIN32
  104. 	if (argc >= 2) {
  105. 		expn2 = _atoi64(argv[1]);
  106. 	}
  107. 	if (argc >= 3) {
  108. 		disp10 = _atoi64(argv[2]);
  109. 	}
  110. #else
  111. 	(void)(argc, argv);
  112. #endif
  113.  
  114. 	// テスト
  115. 	//std::vector<uint32_t> lhs((size_t)1, 9000000UL);
  116. 	//std::vector<uint32_t> rhs((size_t)1, 9000000UL);
  117. 	//std::vector<uint32_t> result = mlen_mul(lhs, rhs);
  118. 	//printf("%07lu %07lu\n", result[1], result[0]);
  119.  
  120. 	// 2^(expn2)
  121. 	std::vector<uint32_t> result = pow2(expn2);
  122.  
  123. 	printf("2^%llu = ", expn2);
  124. 	const size_t sz = result.size();
  125. 	expn_t cnt = 0;
  126. 	for (size_t i = sz; i > 0; i--) {
  127. 		if (cnt < 10) {
  128. 			printf(" %07lu", result[i - 1]);
  129. 		}
  130. 		cnt++;
  131. 	}
  132. 	if (cnt < 10) {
  133. 		printf("\n");
  134. 	}
  135. 	else {
  136. 		printf(". x 10^%llu\n", 7ULL * cnt - 10);
  137. 	}
  138. }
  139.  
Success #stdin #stdout 0s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n=1000, mbuf sz=1 --- 0 sec
n=500, mbuf sz=1 --- 0 sec
n=250, mbuf sz=1 --- 0 sec
n=125, mbuf sz=2 --- 0 sec
n=62, mbuf sz=2 --- 0 sec
n=31, mbuf sz=3 --- 0 sec
n=15, mbuf sz=5 --- 0 sec
n=7, mbuf sz=11 --- 0 sec
n=3, mbuf sz=22 --- 0 sec
n=1, mbuf sz=44 --- 0 sec
2^1000 =  0000001 0715086 0718626 7320948 4250490 6000181 0561404 8117055 3360744 3750388. x 10^298
https://ideone.com/TWKDT6
language:
C++14 (clang 8.0)
created:
3 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!