fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4.  
  5. class Carrier;
  6. class BigInt;
  7. class Decimal;
  8.  
  9. class Carrier {
  10. 	friend class Decimal;
  11. protected:
  12. 	struct Four {
  13. 		Four *upper;
  14. 		Four *under;
  15. 		unsigned long value;
  16. 		Four();
  17. 	};
  18. 	Four *most;
  19. 	Four *least;
  20. 	unsigned long count;
  21. 	Carrier();
  22. 	~Carrier();
  23. 	virtual unsigned long calcFlow(const unsigned long& value) const = 0;
  24. 	virtual unsigned long calcUnit(const unsigned long& value) const = 0;
  25. 	void init(unsigned long value);
  26. 	Four* carry();
  27. 	Carrier& copy(const Carrier& carrier);
  28. 	Carrier& copy(const Carrier *carrier);
  29. 	Carrier& swap(Carrier& carrier);
  30. 	Carrier& add(const Carrier& value);
  31. 	Carrier& mul(const Carrier& value, Carrier& temp);
  32. };
  33.  
  34. class BigInt : public Carrier
  35. {
  36. 	friend class Decimal;
  37. private:
  38. 	static const unsigned long UNIT = 0xFFFF;
  39. 	static const unsigned long SHIFT = 16;
  40. 	unsigned long calcFlow(const unsigned long& value) const;
  41. 	unsigned long calcUnit(const unsigned long& value) const;
  42. public:
  43. 	BigInt();
  44. 	BigInt(unsigned long value);
  45. 	BigInt(const BigInt& value);
  46. 	BigInt(const BigInt *value);
  47. 	BigInt operator ++ (int);
  48. 	BigInt& operator ++ ();
  49. 	BigInt& operator += (const BigInt& value);
  50. 	BigInt& operator *= (const BigInt& value);
  51. 	BigInt& operator = (const BigInt& value);
  52. 	BigInt operator + (const BigInt& value) const;
  53. 	BigInt operator * (const BigInt& value) const;
  54. 	unsigned long digits() const;
  55. 	void print() const;
  56. 	void println() const;
  57. };
  58.  
  59. class Decimal : public Carrier
  60. {
  61. private:
  62. 	static const unsigned long UNIT = 10000;
  63. 	unsigned long calcFlow(const unsigned long& value) const;
  64. 	unsigned long calcUnit(const unsigned long& value) const;
  65. public:
  66. 	Decimal();
  67. 	Decimal(unsigned long value);
  68. 	Decimal(const Decimal& value);
  69. 	Decimal(const Decimal *value);
  70. 	Decimal(const BigInt& value);
  71. 	Decimal(const BigInt *value);
  72. 	Decimal operator ++ (int);
  73. 	Decimal& operator ++ ();
  74. 	Decimal& operator += (const Decimal& value);
  75. 	Decimal& operator *= (const Decimal& value);
  76. 	Decimal& operator = (const Decimal& value);
  77. 	Decimal operator + (const Decimal& value) const;
  78. 	Decimal operator * (const Decimal& value) const;
  79. 	unsigned long digits() const;
  80. 	void print() const;
  81. 	void println() const;
  82.  
  83. };
  84.  
  85. BigInt operator + (const unsigned long& lvalue, const BigInt& rvalue);
  86. BigInt operator * (const unsigned long& lvalue, const BigInt& rvalue);
  87. Decimal operator + (const unsigned long& lvalue, const Decimal& rvalue);
  88. Decimal operator * (const unsigned long& lvalue, const Decimal& rvalue);
  89.  
  90.  
  91.  
  92. Carrier::Four::Four() : upper(NULL), under(NULL), value(0) {}
  93. Carrier::Carrier() : count(1) { most = least = new Four; }
  94. Carrier::~Carrier() { 
  95. 	Four *temp;
  96. 	while (most != NULL) {
  97. 		temp = most->under;
  98. 		delete most;
  99. 		most = temp;
  100. 	}
  101. 	//count = 0;
  102. 	//most = least = NULL;
  103. }
  104. void Carrier::init(unsigned long value) {
  105. 	Four *temp = least;
  106. 	while (value > 0) {
  107. 		if (temp == NULL) {
  108. 			temp = carry();
  109. 		}
  110. 		temp->value = calcUnit(value);
  111. 		value = calcFlow(value);
  112. 		temp = temp->upper;
  113. 	}
  114. }
  115. Carrier& Carrier::copy(const Carrier& carrier) {
  116. 	Four *me = least;
  117. 	Four *he = carrier.least;
  118. 	while (he != NULL) {
  119. 		if (me == NULL) {
  120. 			me = carry();
  121. 		}
  122. 		me->value = he->value;
  123. 		me = me->upper;
  124. 		he = he->upper;
  125. 	}
  126. 	while (me != NULL) {
  127. 		me->value = 0;
  128. 		me = me->upper;
  129. 	}
  130. 	return *this;
  131. }
  132. Carrier& Carrier::copy(const Carrier *carrier) { if (carrier != NULL) { copy(*carrier); } return *this; }
  133. Carrier& Carrier::swap(Carrier& carrier) {
  134. 	Four *temp_most  = most;
  135. 	Four *temp_least = least;
  136. 	int   temp_count = count;
  137. 	most  = carrier.most;
  138. 	least = carrier.least;
  139. 	count = carrier.count;
  140. 	carrier.most  = temp_most;
  141. 	carrier.least = temp_least;
  142. 	carrier.count = temp_count;
  143. 	return *this;
  144. }
  145. Carrier::Four* Carrier::carry() {
  146. 	count++;
  147. 	Four *temp = new Four;
  148. 	temp->under = most;
  149. 	most->upper = temp;
  150. 	most = temp;
  151. 	return most;
  152. }
  153. Carrier& Carrier::add(const Carrier& value) {
  154. 	unsigned long flow = 0;
  155. 	Four *me = least;
  156. 	Four *he = value.least;
  157. 	while (he != NULL) {
  158. 		if (me == NULL) {
  159. 			me = carry();
  160. 		}
  161. 		me->value += he->value + flow;
  162. 		flow = calcFlow(me->value);
  163. 		me->value = calcUnit(me->value);
  164. 		me = me->upper;
  165. 		he = he->upper;
  166. 	}
  167. 	while (flow > 0) {
  168. 		if (me == NULL) {
  169. 			me = carry();
  170. 		}
  171. 		me->value += flow;
  172. 		flow = calcFlow(me->value);
  173. 		me->value = calcUnit(me->value);
  174. 		me = me->upper;
  175. 	}
  176. 	return *this;
  177. }
  178. Carrier& Carrier::mul(const Carrier& value, Carrier& temp) {
  179. 	swap(temp);
  180. 	Four *me = least;
  181. 	Four *he = value.least;
  182. 	Four *she, *who;
  183. 	unsigned long flow1, flow2, product;
  184. 	while (he != NULL) {
  185. 		if (me == NULL) {
  186. 			me = carry();
  187. 		}
  188. 		she = temp.least;
  189. 		who = me;
  190. 		flow1 = flow2 = 0;
  191. 		while (she != NULL) {
  192. 			if (who == NULL) {
  193. 				who = carry();
  194. 			}
  195. 			product = he->value * she->value;
  196. 			flow2 = calcFlow(product);
  197. 			who->value += calcUnit(product);
  198. 			flow2 += calcFlow(who->value);
  199. 			who->value = calcUnit(who->value);
  200. 			who->value += flow1;
  201. 			flow1 = flow2 + calcFlow(who->value);
  202. 			who->value = calcUnit(who->value);
  203. 			who = who->upper;
  204. 			she = she->upper;
  205. 		}
  206. 		while (flow1 > 0) {
  207. 			if (who == NULL) {
  208. 				who = carry();
  209. 			}
  210. 			who->value += flow1;
  211. 			flow1 = calcFlow(who->value);
  212. 			who->value = calcUnit(who->value);
  213. 			who = who->upper;
  214. 		}
  215. 		me = me->upper;
  216. 		he = he->upper;
  217. 	}
  218. 	return *this;
  219. }
  220.  
  221. unsigned long BigInt::calcFlow(const unsigned long& value) const { return value >> SHIFT; }
  222. unsigned long BigInt::calcUnit(const unsigned long& value) const { return value & UNIT; }
  223. BigInt::BigInt() {}
  224. BigInt::BigInt(unsigned long value) { init(value); }
  225. BigInt::BigInt(const BigInt& value) { copy(value); }
  226. BigInt::BigInt(const BigInt *value) { copy(value); }
  227. void BigInt::print() const { Decimal temp(*this); temp.print(); }
  228. void BigInt::println() const { Decimal temp(*this); temp.print(); putchar('\n'); }
  229. unsigned long BigInt::digits() const { Decimal temp(*this); return temp.digits(); }
  230. BigInt& BigInt::operator ++ () { add(BigInt(1)); return *this; }
  231. BigInt BigInt::operator ++ (int) { BigInt temp(*this); add(BigInt(1)); return temp; }
  232. BigInt& BigInt::operator += (const BigInt& value) { add(value); return *this; }
  233. BigInt BigInt::operator + (const BigInt& value) const { BigInt sum(value); sum.add(*this); return sum; }
  234. BigInt& BigInt::operator *= (const BigInt& value) { BigInt zero; mul(value, zero); return *this; }
  235. BigInt BigInt::operator * (const BigInt& value) const { BigInt product(value), zero; product.mul(*this, zero); return product; }
  236. BigInt& BigInt::operator = (const BigInt& value) { copy(value); return *this; }
  237. BigInt operator + (const unsigned long& lvalue, const BigInt& rvalue) { return BigInt(lvalue) + rvalue; }
  238. BigInt operator * (const unsigned long& lvalue, const BigInt& rvalue) { return BigInt(lvalue) * rvalue; }
  239.  
  240. unsigned long Decimal::calcFlow(const unsigned long& value) const { return value / UNIT; }
  241. unsigned long Decimal::calcUnit(const unsigned long& value) const { return value % UNIT; }
  242. Decimal::Decimal() {}
  243. Decimal::Decimal(unsigned long value) { init(value); }
  244. Decimal::Decimal(const Decimal& value) { copy(value); }
  245. Decimal::Decimal(const Decimal *value) { copy(*value); }
  246. Decimal::Decimal(const BigInt& value) {
  247. 	const Decimal temp(BigInt::UNIT + 1);
  248. 	Four *cur = value.most;
  249. 	while (cur != NULL) {
  250. 		Decimal zero;
  251. 		mul(temp, zero);
  252. 		add(Decimal(cur->value));
  253. 		cur = cur->under;
  254. 	}
  255. }
  256. Decimal::Decimal(const BigInt *value) { 
  257. 	if (value != NULL) {
  258. 		Decimal temp(*value);
  259. 		swap(temp);
  260. 	} 
  261. }
  262. void Decimal::print() const {
  263. 	Four *temp = most;
  264. 	int f = 0;
  265. 	while (temp != NULL) {
  266. 		if (f == 0) {
  267. 			if (temp->value != 0) {
  268. 				printf("%ld", temp->value);
  269. 				f = 1;
  270. 			}
  271. 		} else {
  272. 			printf("%04ld", temp->value);
  273. 		}
  274. 		temp = temp->under;
  275. 	}
  276. 	if (f == 0) {
  277. 		putchar('0');
  278. 	}
  279. }
  280. void Decimal::println() const { print(); putchar('\n'); }
  281. unsigned long Decimal::digits() const {
  282. 	unsigned long temp_count = count;
  283. 	Four *temp = most;
  284. 	while (temp->value == 0) {
  285. 		temp_count--;
  286. 		if ((temp = temp->under) == NULL) {
  287. 			return 1;
  288. 		}
  289. 	}
  290. 	temp_count *= 4;
  291. 	unsigned long unit = UNIT / 10;
  292. 	while (temp->value < unit) {
  293. 	    temp_count--;
  294. 	    unit /= 10;
  295. 	}
  296. 	return temp_count;
  297. }
  298. Decimal& Decimal::operator ++ () { add(Decimal(1)); return *this; }
  299. Decimal Decimal::operator ++ (int) { Decimal temp(*this); add(Decimal(1)); return temp; }
  300. Decimal& Decimal::operator += (const Decimal& value) { add(value); return *this; }
  301. Decimal Decimal::operator + (const Decimal& value) const { Decimal sum(value); sum.add(*this); return sum; }
  302. Decimal& Decimal::operator *= (const Decimal& value) { Decimal zero; mul(value, zero); return *this; }
  303. Decimal Decimal::operator * (const Decimal& value) const { Decimal product(value), zero; product.mul(*this, zero); return product; }
  304. Decimal& Decimal::operator = (const Decimal& value) { copy(value); return *this; }
  305. Decimal operator + (const unsigned long& lvalue, const Decimal& rvalue) { return Decimal(lvalue) + rvalue; }
  306. Decimal operator * (const unsigned long& lvalue, const Decimal& rvalue) { return Decimal(lvalue) * rvalue; }
  307.  
  308.  
  309.  
  310. int main() {
  311.  
  312.  
  313. 	BigInt val1(111111);
  314. 	BigInt val2(val1 + 800800);
  315. 	BigInt val3(val1 * val2);
  316. 	BigInt val4(val1 + val2);
  317.  
  318. 	val3 *= val1 * val1;
  319. 	val4 += val2 * val2;;
  320.  
  321. 	val1.println();
  322. 	cout << "digits: " << val1.digits() << endl;
  323. 	val2.println();
  324. 	cout << "digits: " << val2.digits() << endl;
  325. 	val3.println();
  326. 	cout << "digits: " << val3.digits() << endl;
  327. 	val4.println();
  328. 	cout << "digits: " << val4.digits() << endl;
  329.  
  330.  
  331. 	Decimal dec1(111111);
  332. 	Decimal dec2(dec1 + 800800);
  333. 	Decimal dec3(dec1 * dec2);
  334. 	Decimal dec4(dec1 + dec2);
  335.  
  336. 	dec3 *= dec1 * dec1;
  337. 	dec4 += dec2 * dec2;
  338.  
  339. 	dec1.println();
  340. 	cout << "digits: " << dec1.digits() << endl;
  341. 	dec2.println();
  342. 	cout << "digits: " << dec2.digits() << endl;
  343. 	dec3.println();
  344. 	cout << "digits: " << dec3.digits() << endl;
  345. 	dec4.println();	
  346. 	cout << "digits: " << dec4.digits() << endl;
  347.  
  348. 	BigInt val5(val4 * val4 * val4);
  349. 	val5 *= val5 * val5 * val5;
  350. 	val5 *= val5 * val5 * val5;
  351. 	Decimal dec5(val5);
  352. 	dec5.println();	
  353. 	cout << "digits: " << dec5.digits() << endl;
  354.  
  355. 	BigInt val6;
  356. 	val6 = 9 * val1;
  357. 	val6.println();
  358.  
  359. 	Decimal dec6;
  360. 	dec6 = 12345 + dec1;
  361. 	dec6++;
  362. 	++dec6;
  363. 	dec6.println();
  364.  
  365. 	return 0;
  366. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
111111
digits: 6
911911
digits: 6
1250902968819939275841
digits: 22
831582694943
digits: 12
111111
digits: 6
911911
digits: 6
1250902968819939275841
digits: 22
831582694943
digits: 12
143041242070337201583611737653920048440131393558333883996983720266656238206069209427317501545992973128069662865455356447001399963826367397673462751863194558289241465303021064650945859693822803497940848182755698465523058331186525895460152608789326184863796377091155575815664321549206397905798562418120490611214131773955955780740095307216799907592649406249810258060532560673118554855540860711866959160696303079057096572600742279719221789133032740046422655190956781860858755425508597646870204433695538711632032006919752500200597515578473102890101958702392891869684175536192001
digits: 573
999999
123458
https://ideone.com/EGANYD
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!