fork(1) 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 = NULL;
  14. 		Four *under = NULL;
  15. 		unsigned long value = 0;
  16. 	};
  17. 	Four *most  = NULL;
  18. 	Four *least = NULL;
  19.     void release();
  20.     Four* carry();
  21. 	Carrier();
  22. 	~Carrier();
  23. };
  24.  
  25. class BigInt : public virtual Carrier
  26. {
  27. 	friend class Decimal;
  28. private:
  29. 	static const unsigned long UNIT = 0xFFFF;
  30. 	static const unsigned long SHIFT = 16;
  31. public:
  32. 	BigInt();
  33. 	BigInt(unsigned long value);
  34. 	BigInt& add(const BigInt& value);
  35. //	BigInt& copy(const BitInt& value);
  36. };
  37.  
  38. class Decimal : public virtual Carrier
  39. {
  40. private:
  41. 	static const unsigned long UNIT = 10000;
  42. public:
  43.     Decimal();
  44.     Decimal(unsigned long value);
  45.     Decimal(const Decimal& value);
  46.     Decimal(const Decimal *value);
  47.     Decimal(const BigInt& value);
  48.     Decimal& add(const Decimal& value);
  49.     Decimal& mul(const Decimal& value);
  50.     Decimal& copy(const Decimal& value);
  51.     Decimal& copy(const Decimal *value);
  52.     Decimal& swap(Decimal& value);
  53.     Decimal& operator ++ ();
  54.     Decimal& operator = (const Decimal& value);
  55.     Decimal& operator += (const Decimal& value);
  56.     Decimal& operator *= (const Decimal& value);
  57.     Decimal operator + (const Decimal& value);
  58.     Decimal operator * (const Decimal& value);
  59.     void print() const;
  60.     void println() const;
  61.  
  62. };
  63.  
  64. Carrier::Carrier() { most = least = new Four; }
  65. Carrier::~Carrier() { release(); }
  66. void Carrier::release() {
  67. 	Four *temp;
  68. 	while (most != NULL) {
  69. 		temp = most->under;
  70. 		delete most;
  71. 		most = temp;
  72. 	}
  73. 	most = least = NULL;
  74. }
  75. Carrier::Four* Carrier::carry() {
  76. 	Four *temp = new Four;
  77. 	temp->under = most;
  78. 	most->upper = temp;
  79. 	most = temp;
  80. 	return most;
  81. }
  82.  
  83. BigInt::BigInt() {}
  84. BigInt::BigInt(unsigned long value) {
  85. 	Four *temp = least;
  86. 	while (value > 0) {
  87. 		if (temp == NULL) {
  88. 			temp = carry();
  89. 		}
  90. 		temp->value = value & UNIT;
  91. 		value >>= SHIFT;
  92. 		temp = temp->upper;
  93. 	}
  94. }
  95. BigInt& BigInt::add(const BigInt& value) {
  96. 	unsigned long flow = 0;
  97. 	Four *me = least;
  98. 	Four *he = value.least;
  99. 	while (he != NULL) {
  100. 		if (me == NULL) {
  101. 			me = carry();
  102. 		}
  103. 		me->value += he->value + flow;
  104. 		flow = me->value >> SHIFT;
  105. 		me->value &= UNIT;
  106. 		me = me->upper;
  107. 		he = he->upper;
  108. 	}
  109. 	while (flow > 0) {
  110. 		if (me == NULL) {
  111. 			me = carry();
  112. 		}
  113. 		me->value += flow;
  114. 		flow = me->value >> SHIFT;
  115. 		me->value &= UNIT;
  116. 		me = me->upper;
  117. 	}
  118. 	return *this;
  119. }
  120.  
  121.  
  122. Decimal::Decimal() {}
  123. Decimal::Decimal(unsigned long value) {
  124. 	Four *temp = least;
  125. 	while (value > 0) {
  126. 		if (temp == NULL) {
  127. 			temp = carry();
  128. 		}
  129. 		temp->value = value % UNIT;
  130. 		value /= UNIT;
  131. 		temp = temp->upper;
  132. 	}
  133. }
  134. Decimal::Decimal(const Decimal& value) { copy(value); }
  135. Decimal::Decimal(const Decimal *value) { copy(value); }
  136. Decimal::Decimal(const BigInt& value) {
  137. 	const Decimal temp(BigInt::UNIT + 1);
  138. 	Four *cur = value.most;
  139. 	while (cur != NULL) {
  140. 		mul(temp);
  141. 		add(Decimal(cur->value));
  142. 		cur = cur->under;
  143. 	}
  144. }
  145. Decimal& Decimal::add(const Decimal& value) {
  146. 	unsigned long flow = 0;
  147. 	Four *me = least;
  148. 	Four *he = value.least;
  149. 	while (he != NULL) {
  150. 		if (me == NULL) {
  151. 			me = carry();
  152. 		}
  153. 		me->value += he->value + flow;
  154. 		flow = me->value / UNIT;
  155. 		me->value %= UNIT;
  156. 		me = me->upper;
  157. 		he = he->upper;
  158. 	}
  159. 	while (flow > 0) {
  160. 		if (me == NULL) {
  161. 			me = carry();
  162. 		}
  163. 		me->value += flow;
  164. 		flow = me->value / UNIT;
  165. 		me->value %= UNIT;
  166. 		me = me->upper;
  167. 	}
  168. 	return *this;
  169. }
  170. Decimal& Decimal::mul(const Decimal& value) {
  171. 	Decimal temp;
  172. 	swap(temp);
  173. 	Four *me = least;
  174. 	Four *he = value.least;
  175. 	Four *she, *who;
  176. 	unsigned long flow1, flow2, product;
  177. 	while (he != NULL) {
  178. 		if (me == NULL) {
  179. 			me = carry();
  180. 		}
  181. 		she = temp.least;
  182. 		who = me;
  183. 		flow1 = flow2 = 0;
  184. 		while (she != NULL) {
  185. 			if (who == NULL) {
  186. 				who = carry();
  187. 			}
  188. 			product = he->value * she->value;
  189. 			flow2 = product / UNIT;
  190. 			who->value += product % UNIT;
  191. 			flow2 += who->value / UNIT;
  192. 			who->value %= UNIT;
  193. 			who->value += flow1;
  194. 			flow1 = flow2 + (who->value / UNIT);
  195. 			who->value %= UNIT;
  196. 			who = who->upper;
  197. 			she = she->upper;
  198. 		}
  199. 		while (flow1 > 0) {
  200. 			if (who == NULL) {
  201. 				who = carry();
  202. 			}
  203. 			who->value += flow1;
  204. 			flow1 = who->value / UNIT;
  205. 			who->value %= UNIT;
  206. 			who = who->upper;
  207. 		}
  208. 		me = me->upper;
  209. 		he = he->upper;
  210. 	}
  211. 	return *this;
  212. }
  213. Decimal& Decimal::copy(const Decimal& value) {
  214. 	Four *me = least;
  215. 	Four *he = value.least;
  216. 	while (he != NULL) {
  217. 		if (me == NULL) {
  218. 			me = carry();
  219. 		}
  220. 		me->value = he->value;
  221. 		me = me->upper;
  222. 		he = he->upper;
  223. 	}
  224. 	while (me != NULL) {
  225. 		me->value = 0;
  226. 		me = me->upper;
  227. 	}
  228. 	return *this;
  229. }
  230. Decimal& Decimal::copy(const Decimal *value) { if (value != NULL) { copy(*value); } return *this; }
  231. Decimal& Decimal::swap(Decimal& value) {
  232. 	Four *temp_most = most;
  233. 	Four *temp_least = least;
  234. 	most = value.most;
  235. 	least = value.least;
  236. 	value.most = temp_most;
  237. 	value.least = temp_least;
  238. 	return *this;
  239. }
  240. void Decimal::print() const {
  241. 	Four *temp = most;
  242. 	int f = 0;
  243. 	while (temp != NULL) {
  244. 		if (f == 0) {
  245. 			if (temp->value != 0) {
  246. 				printf("%d", temp->value);
  247. 				f = 1;
  248. 			}
  249. 		} else {
  250. 			printf("%04d", temp->value);
  251. 		}
  252. 		temp = temp->under;
  253. 	}
  254. 	if (f == 0) {
  255. 		putchar('0');
  256. 	}
  257. }
  258. void Decimal::println() const { print(); putchar('\n'); }
  259. Decimal& Decimal::operator ++ () { return add(Decimal(1)); }
  260. Decimal& Decimal::operator += (const Decimal& value) { return add(value); }
  261. Decimal Decimal::operator + (const Decimal& value) { Decimal sum(value); return sum.add(*this); }
  262. Decimal& Decimal::operator *= (const Decimal& value) { return mul(value); }
  263. Decimal Decimal::operator * (const Decimal& value) { Decimal product(value); return product.mul(*this); }
  264. Decimal& Decimal::operator = (const Decimal& value) { return copy(value); }
  265.  
  266.  
  267. int main() {
  268.  
  269. 	BigInt val1(12340);
  270. 	BigInt val2(90060);
  271.  
  272. 	BigInt val(1234567);
  273. 	Decimal dec1(1111111);
  274. 	Decimal dec2(7);
  275. 	Decimal dec3(val1.add(val2));
  276.  
  277. 	dec2 *= dec1;
  278. 	dec2 += dec2;
  279. 	dec2 += dec2;
  280.  
  281. 	dec1.println();
  282. 	dec2.println();
  283. 	dec3.println();
  284.  
  285. 	return 0;
  286. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1111111
31111108
102400
https://ideone.com/7pjF2e
language:
C++ (gcc 8.3)
created:
11 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!