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