fork download
copy 
  1. 	class BigInteger
  2. 	{
  3. 		char *m_ptr;
  4. 		size_t m_length;
  5. 		bool sign;
  6.  
  7. 	public:
  8.  
  9. 		BigInteger()
  10. 			: m_ptr(nullptr)
  11. 			, m_length(0)
  12. 			, sign(false)
  13. 		{
  14. 		}
  15.  
  16. 		~BigInteger()
  17. 		{
  18. 			if ( m_ptr != nullptr )
  19. 				delete[] m_ptr;
  20. 		}
  21.  
  22. 		void Add(const char * s)
  23. 		{
  24. 			char *k = _strdup(s);
  25. 			InternalAddition(_strrev(k));
  26. 			delete[] k;
  27. 		}
  28.  
  29. 		void Sub(const char * s)
  30. 		{
  31. 			char *k = _strdup(s);
  32. 			InternalSubtract(_strrev(k));
  33. 			delete[] k;
  34. 		}
  35.  
  36. 		void Mul(const char * s)
  37. 		{
  38. 			char *k = _strdup(s);
  39. 			InternalMultiple(_strrev(k));
  40. 			delete[] k;
  41. 		}
  42.  
  43. 		void Div(const char * s)
  44. 		{
  45. 			InternalDivide((char *)s);
  46. 		}
  47.  
  48. 		char* get() const
  49. 		{
  50. 			return m_ptr;
  51. 		}
  52.  
  53. 	private:
  54.  
  55. 		void InternalAddition(char* a1)
  56. 		{
  57. 			size_t srclen = strlen(a1);
  58. 			char* tmp = CheckPtr(srclen);
  59.  
  60. 			if (!m_length || (m_length == 1 && *m_ptr == '0'))
  61. 			{
  62. 				memcpy(tmp, _strrev(a1), srclen + 1);
  63. 				delete[] m_ptr;
  64. 				m_ptr = tmp;
  65. 				m_length = srclen;
  66. 				return;
  67. 			}
  68.  
  69. 			if ( sign )
  70. 			{
  71. 				sign = 1;
  72. 				InternalSubtract(a1);
  73. 				sign = 0;
  74. 				return;
  75. 			}
  76.  
  77. 			int carry = 0;
  78. 			char *ptr = tmp;
  79. 			char *mm_ptr = m_ptr;
  80.  
  81. 			_strrev(m_ptr);
  82.  
  83. 			for ( ; *a1 && *m_ptr; a1++, m_ptr++)
  84. 			{
  85. 				int k = (*a1 & 0xf) + (*m_ptr & 0xf) + carry;
  86. 				carry = k / 10;
  87. 				k %= 10;
  88. 				*ptr++ = k + '0';
  89. 			}
  90.  
  91. 			if ( *a1 )
  92. 			{
  93. 				for ( ; *a1 ; a1++)
  94. 				{
  95. 					int k = (*a1 & 0xf) + carry;
  96. 					carry = k / 10;
  97. 					k %= 10;
  98. 					*ptr++ = k + '0';
  99. 				}
  100. 			}
  101. 			else if ( *m_ptr )
  102. 			{
  103. 				for ( ; *m_ptr ; m_ptr++)
  104. 				{
  105. 					int k = (*m_ptr & 0xf) + carry;
  106. 					carry = k / 10;
  107. 					k %= 10;
  108. 					*ptr++ = k + '0';
  109. 				}
  110. 			}
  111.  
  112. 			if (carry)
  113. 			{
  114. 				*ptr++ = carry + '0';
  115. 			}
  116.  
  117. 			*ptr = 0;
  118. 			_strrev(tmp);
  119. 			delete[] mm_ptr;
  120. 			m_ptr = tmp;
  121. 			m_length = ptr - tmp;
  122. 			Trim();
  123. 		}
  124.  
  125. 		void InternalSubtract(char* a1)
  126. 		{
  127. 			size_t srclen = strlen(a1);
  128. 			char* tmp = CheckPtr(srclen);
  129.  
  130. 			if (!m_length || (m_length == 1 && *m_ptr == '0'))
  131. 			{
  132. 				memcpy(tmp, _strrev(a1), srclen + 1);
  133. 				delete[] m_ptr;
  134. 				m_ptr = tmp;
  135. 				m_length = srclen;
  136. 				sign = true;
  137. 				return;
  138. 			}
  139.  
  140. 			if ( sign )
  141. 			{
  142. 				sign = 0;
  143. 				InternalAddition(a1);
  144. 				sign = 1;
  145. 				return;
  146. 			}
  147.  
  148. 			int carry = 0;
  149. 			char *ptr = tmp;
  150. 			char *mm_ptr = m_ptr;
  151.  
  152. 			_strrev(m_ptr);
  153.  
  154. 			for ( ; *a1 && *m_ptr; a1++, m_ptr++ )
  155. 			{
  156. 				int k = (*m_ptr & 0xf) - (*a1 & 0xf) - carry;
  157. 				carry = k < 0;
  158.  
  159. 				if (k >= 0)
  160. 					*ptr++ = '0' + k;
  161. 				else
  162. 					*ptr++ = '9' + k + 1;
  163. 			}
  164.  
  165. 			if ( *a1 )
  166. 			{
  167. 				carry = 1;
  168. 				for ( ; *a1 ; a1++ )
  169. 				{
  170. 					int k =  (*a1 & 0xf) - carry;
  171. 					carry = k < 0;
  172.  
  173. 					if (k >= 0)
  174. 						*ptr++ = '0' + k;
  175. 					else
  176. 						*ptr++ = '9' + k + 1;
  177. 				}
  178. 				sign = true;
  179. 			}
  180. 			else if ( *m_ptr )
  181. 			{
  182. 				for ( ; *m_ptr ; m_ptr++ )
  183. 				{
  184. 					int n = (*m_ptr & 0xf);
  185. 					int k = n - carry;
  186. 					carry = k < 0;
  187.  
  188. 					if (k >= 0)
  189. 						*ptr++ = '0' + k;
  190. 					else
  191. 						*ptr++ = '9' + k + 1;
  192. 				}
  193. 			}
  194. 			else if ( carry )
  195. 			{
  196. 				*(ptr - 1) = (*--a1 & 0xf) - (*--m_ptr & 0xf) + '0';
  197. 			}
  198.  
  199. 			if ( carry )
  200. 			{
  201. 				sign = true;
  202. 			}
  203.  
  204. 			*ptr = 0;
  205. 			_strrev(tmp);
  206. 			delete[] mm_ptr;
  207. 			m_ptr = tmp;
  208. 			m_length = ptr - tmp;
  209. 			Trim();
  210. 		}
  211.  
  212. 		void InternalMultiple(char* a)
  213. 		{
  214. 			if (!m_length || (m_length == 1 && *m_ptr == '0'))
  215. 				return;
  216.  
  217. 			char* _dup = _strdup(_strrev(m_ptr));
  218. 			size_t len = m_length;
  219.  
  220. 			delete[] m_ptr;
  221. 			m_length = 0;
  222. 			m_ptr = nullptr;
  223.  
  224. 			size_t alen = strlen(a);
  225.  
  226. 			for (int i = 0; i < alen; i++)
  227. 				InternalMultipleCh(_dup, len, a[i], i);
  228.  
  229. 			delete[] _dup;
  230. 			Trim();
  231. 		}
  232.  
  233. 		void InternalMultipleCh(char* sm_ptr, size_t sm_len, char a, int z)
  234. 		{
  235. 			char* ptr = sm_ptr;
  236. 			char* tmp = new char[sm_len + z + 2];
  237. 			char* ttr = tmp + z;
  238. 			int carry = 0;
  239.  
  240. 			for ( ; *ptr; ptr++)
  241. 			{
  242. 				int k = carry + (*ptr & 0xf) * (a & 0xf);
  243. 				*ttr++ = (k % 10) + '0';
  244. 				carry = k / 10;
  245. 			}
  246.  
  247. 			if ( carry )
  248. 				*ttr++ = (carry % 10) + '0';
  249. 			*ttr = 0;
  250.  
  251. 			while ( z-- )
  252. 				tmp[z] = '0';
  253.  
  254. 			InternalAddition(tmp);
  255. 			delete[] tmp;
  256. 		}
  257.  
  258. 		void InternalDivide(char * a)
  259. 		{
  260. 			size_t len = strlen(a);
  261.  
  262. 			if ( len == 1 && *a == '0' )
  263. 				throw("ㅗ");
  264.  
  265. 			if ( m_length < len )
  266. 				ForcePut("0");
  267.  
  268. 			char* buf = new char[m_length];
  269. 			size_t blen = 0;
  270. 			char* ptr = m_ptr;
  271. 			size_t prevlen = m_length;
  272.  
  273. 			for ( size_t posValid = len - 1; posValid < m_length; )
  274. 			{
  275. 				bool skip = false;
  276.  
  277. 				if (InternalCompare(a) < 0)
  278. 					break;
  279.  
  280. 				if ( m_ptr[posValid] >= *a )
  281. 				{
  282. 					char tch = m_ptr[posValid + 1];
  283. 					m_ptr[posValid + 1] = 0;
  284. 					bool k = strcmp(m_ptr, a) >= 0;
  285. 					m_ptr[posValid + 1] = tch;
  286. 					if (k == true)
  287. 						goto S;
  288. 				}
  289.  
  290. 				if ( posValid >= m_length  )
  291. 					break;
  292. 				posValid++;
  293. 				buf[blen++] = 0;
  294. 				skip = true;
  295. 			S:
  296. 				char* lefts = new char[posValid + len];
  297. 				memcpy(lefts, m_ptr, posValid + len - 1);
  298. 				lefts[posValid + len - 1] = 0;
  299.  
  300. 				const char* bt[] = { "2", "3", "4", "5", "6", "7", "8", "9" };
  301. 				int i = 2;
  302. 				for ( ; i < 10; i++)
  303. 				{
  304. 					BigInteger bi;
  305. 					bi.Add(a);
  306. 					bi.Mul(bt[i-2]);
  307. 					if ( bi.InternalCompare(lefts) >= 0 )
  308. 						break;
  309. 				}
  310.  
  311. 				BigInteger result;
  312. 				result.Add(a);
  313. 				if ( i >= 3 )
  314. 					result.Mul(bt[i-3]);
  315. 				char* subt_ex10 = new char[m_length - posValid + skip + len];
  316. 				memcpy(subt_ex10, result.m_ptr, result.m_length);
  317. 				int puts = m_length - posValid - len + 1;
  318. 				if ( puts > 0 )
  319. 				while ( puts-- )
  320. 					subt_ex10[result.m_length + puts] = '0';
  321. 				subt_ex10[m_length - posValid + skip + len - 1] = 0;
  322.  
  323. 				InternalSubtract(_strrev(subt_ex10));
  324.  
  325. 				delete[] lefts;
  326. 				delete[] subt_ex10;
  327.  
  328. 				buf[blen++] = i - 1;
  329.  
  330. 				if ( prevlen > m_length )
  331. 				{
  332. 					posValid = len - 1;
  333. 					prevlen = m_length;
  334. 					buf[blen++] = 0;
  335. 				}
  336. 			}
  337.  
  338. 			size_t bpl = blen;
  339. 			char* tmp = new char[blen + 1];
  340. 			while ( --blen )
  341. 				tmp[blen] = buf[blen] + '0';
  342. 			*tmp = *buf + '0';
  343. 			tmp[bpl] = 0;
  344. 			delete[] m_ptr;
  345. 			delete[] buf;
  346. 			m_length = bpl - 1;
  347. 			m_ptr = tmp;
  348. 		}
  349.  
  350. 		int InternalCompare(char * a)
  351. 		{
  352. 			size_t len = strlen(a);
  353.  
  354. 			if ( len > m_length )
  355. 				return -1;
  356. 			else if ( len < m_length ) 
  357. 				return 1;
  358.  
  359. 			return strcmp(m_ptr, a);
  360. 		}
  361.  
  362. 		char* CheckPtr(size_t len = 0)
  363. 		{
  364. 			len = std::max(len, m_length);
  365.  
  366. 			char* ptr = new char[len + 2];
  367. 			memset(ptr, 0, len + 2);
  368. 			return ptr;
  369. 		}
  370.  
  371. 		void ForcePut(const char* s)
  372. 		{
  373. 			delete[] m_ptr;
  374. 			m_length = strlen(s);
  375. 			m_ptr = _strdup(s);
  376. 		}
  377.  
  378. 		void Trim()
  379. 		{
  380. 			if ( m_length > 1 )
  381. 			{
  382. 				char* starts = m_ptr;
  383. 				char* last = m_ptr + m_length - 1;
  384.  
  385. 				while (*starts == '0' && starts != last)
  386. 					starts++;
  387.  
  388. 				if ( starts != m_ptr )
  389. 				{
  390. 					m_length = m_length - ( starts - m_ptr ) + (starts == last);
  391. 					char* tmp = new char[m_length + 1];
  392. 					memcpy(tmp, starts, m_length + 1);
  393. 					delete[] m_ptr;
  394. 					m_ptr = tmp;
  395. 				}
  396. 			}
  397. 		}
  398.  
  399. 		void Clear()
  400. 		{
  401. 			if (m_ptr != nullptr)
  402. 				delete[] m_ptr;
  403. 			m_length = 0;
  404. 			m_ptr = nullptr;
  405. 		}
  406.  
  407. 	};
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:1:2: error: unknown type name 'class'
  class BigInteger
  ^
prog.c:2:2: error: expected '=', ',', ';', 'asm' or '__attribute__' before '{' token
  {
  ^
stdout
copy 
Standard output is empty
https://ideone.com/xDay3Y
language:
C (gcc 8.3)
created:
10 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!