API tools faq
paste
Advertisement
AlFas

Minecraft integers

AlFas
Jan 21st, 2018
90
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 37.71 KB | None | 0 0
raw download clone embed print report
  1.  
  2. /// <summary>Represents an arbitrarily large integer.</summary>
  3. public class LargeInteger
  4. {
  5. public List<byte> Bytes { get; set; }
  6. public bool Sign { get; set; } // True if number is positive
  7. public int Length { get { return Bytes.Count; } }
  8.  
  9. #region Constructors
  10. public LargeInteger()
  11. {
  12. Bytes = new List<byte>(1);
  13. }
  14. public LargeInteger(byte b)
  15. {
  16. Bytes = new List<byte>(1);
  17. Bytes.AddRange(BitConverter.GetBytes(b));
  18. Sign = true;
  19. }
  20. public LargeInteger(short s)
  21. {
  22. Bytes = new List<byte>(1);
  23. Bytes.AddRange(BitConverter.GetBytes((long)s));
  24. Sign = s >= 0;
  25. }
  26. public LargeInteger(int i)
  27. {
  28. Bytes = new List<byte>(1);
  29. Bytes.AddRange(BitConverter.GetBytes(i));
  30. Sign = i >= 0;
  31. }
  32. public LargeInteger(long l)
  33. {
  34. Bytes = new List<byte>(1);
  35. Bytes.AddRange(BitConverter.GetBytes(l));
  36. Sign = l >= 0;
  37. }
  38. public LargeInteger(sbyte b)
  39. {
  40. Bytes = new List<byte>(1);
  41. Bytes.AddRange(BitConverter.GetBytes(b));
  42. Sign = b >= 0;
  43. }
  44. public LargeInteger(ushort s)
  45. {
  46. Bytes = new List<byte>(1);
  47. Bytes.AddRange(BitConverter.GetBytes(s));
  48. Sign = true;
  49. }
  50. public LargeInteger(uint i)
  51. {
  52. Bytes = new List<byte>(1);
  53. Bytes.AddRange(BitConverter.GetBytes(i));
  54. Sign = true;
  55. }
  56. public LargeInteger(ulong l)
  57. {
  58. Bytes = new List<byte>(1);
  59. Bytes.AddRange(BitConverter.GetBytes(l));
  60. Sign = true;
  61. }
  62. public LargeInteger(float f)
  63. {
  64. Bytes = new List<byte>(1);
  65. Bytes.AddRange(BitConverter.GetBytes((long)f));
  66. Sign = f >= 0;
  67. }
  68. public LargeInteger(double d)
  69. {
  70. Bytes = new List<byte>(1);
  71. Bytes.AddRange(BitConverter.GetBytes((long)d));
  72. Sign = d >= 0;
  73. }
  74. public LargeInteger(decimal d)
  75. {
  76. LargeInteger n = Parse(d.ToString());
  77. Bytes = n.Bytes;
  78. Sign = n.Sign;
  79. }
  80. public LargeInteger(byte[] b)
  81. {
  82. Bytes = new List<byte>(b.Length);
  83. Bytes.AddRange(b);
  84. Sign = true;
  85. }
  86. #endregion
  87. #region Implicit Conversions
  88. public static implicit operator LargeInteger(byte a)
  89. {
  90. LargeInteger result = new LargeInteger(a);
  91. result = RemoveUnnecessaryBytes(result);
  92. return result;
  93. }
  94. public static implicit operator LargeInteger(short a)
  95. {
  96. LargeInteger result = new LargeInteger(a);
  97. result = RemoveUnnecessaryBytes(result);
  98. return result;
  99. }
  100. public static implicit operator LargeInteger(int a)
  101. {
  102. LargeInteger result = new LargeInteger(a);
  103. result = RemoveUnnecessaryBytes(result);
  104. return result;
  105. }
  106. public static implicit operator LargeInteger(long a)
  107. {
  108. LargeInteger result = new LargeInteger(a);
  109. result = RemoveUnnecessaryBytes(result);
  110. return result;
  111. }
  112. public static implicit operator LargeInteger(sbyte a)
  113. {
  114. LargeInteger result = new LargeInteger(a);
  115. result = RemoveUnnecessaryBytes(result);
  116. return result;
  117. }
  118. public static implicit operator LargeInteger(ushort a)
  119. {
  120. LargeInteger result = new LargeInteger(a);
  121. result = RemoveUnnecessaryBytes(result);
  122. return result;
  123. }
  124. public static implicit operator LargeInteger(uint a)
  125. {
  126. LargeInteger result = new LargeInteger(a);
  127. result = RemoveUnnecessaryBytes(result);
  128. return result;
  129. }
  130. public static implicit operator LargeInteger(ulong a)
  131. {
  132. LargeInteger result = new LargeInteger(a);
  133. result = RemoveUnnecessaryBytes(result);
  134. return result;
  135. }
  136. #endregion
  137. #region Explicit Conversions
  138. public static explicit operator LargeInteger(float a) => new LargeInteger(a);
  139. public static explicit operator LargeInteger(double a) => new LargeInteger(a);
  140. public static explicit operator LargeInteger(decimal a) => new LargeInteger(a);
  141. #endregion
  142. #region Type Casts
  143. public static explicit operator byte(LargeInteger a)
  144. {
  145. if (a.Sign)
  146. {
  147. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(byte))
  148. a.Bytes.RemoveAt(a.Length - 1);
  149. if (a.Length == sizeof(byte)) return a.Bytes[0];
  150. else throw new OverflowException("The LargeInteger was too big.");
  151. }
  152. else throw new InvalidCastException("Cannot convert a negative number to an unsigned type.");
  153. }
  154. public static explicit operator short(LargeInteger a)
  155. {
  156. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(short))
  157. a.Bytes.RemoveAt(a.Length - 1);
  158. if (a.Length < sizeof(short))
  159. a.Bytes.AddRange(new byte[sizeof(short) - a.Length]);
  160. if (a.Length == sizeof(short)) return (short)(BitConverter.ToInt16(a.Bytes.ToArray(), 0) * (a.Sign ? 1 : -1));
  161. else throw new OverflowException("The LargeInteger was too big.");
  162. }
  163. public static explicit operator int(LargeInteger a)
  164. {
  165. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(int))
  166. a.Bytes.RemoveAt(a.Length - 1);
  167. if (a.Length < sizeof(int))
  168. a.Bytes.AddRange(new byte[sizeof(int) - a.Length]);
  169. if (a.Length == sizeof(int)) return BitConverter.ToInt32(a.Bytes.ToArray(), 0) * (a.Sign ? 1 : -1);
  170. else throw new OverflowException("The LargeInteger was too big.");
  171. }
  172. public static explicit operator long(LargeInteger a)
  173. {
  174. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(long))
  175. a.Bytes.RemoveAt(a.Length - 1);
  176. if (a.Length < sizeof(long))
  177. a.Bytes.AddRange(new byte[sizeof(long) - a.Length]);
  178. if (a.Length == sizeof(long)) return BitConverter.ToInt64(a.Bytes.ToArray(), 0) * (a.Sign ? 1 : -1);
  179. else throw new OverflowException("The LargeInteger was too big.");
  180. }
  181. public static explicit operator sbyte(LargeInteger a)
  182. {
  183. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(sbyte))
  184. a.Bytes.RemoveAt(a.Length - 1);
  185. if (a.Length == sizeof(sbyte)) return a.Sign ? (sbyte)a.Bytes[0] : (sbyte)(-a.Bytes[0]);
  186. else throw new OverflowException("The LargeInteger was too big.");
  187. }
  188. public static explicit operator ushort(LargeInteger a)
  189. {
  190. if (a.Sign)
  191. {
  192. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(ushort))
  193. a.Bytes.RemoveAt(a.Length - 1);
  194. if (a.Length < sizeof(ushort))
  195. a.Bytes.AddRange(new byte[sizeof(ushort) - a.Length]);
  196. if (a.Length == sizeof(ushort)) return BitConverter.ToUInt16(a.Bytes.ToArray(), 0);
  197. else throw new OverflowException("The LargeInteger was too big.");
  198. }
  199. else throw new InvalidCastException("Cannot convert a negative number to an unsigned type.");
  200. }
  201. public static explicit operator uint(LargeInteger a)
  202. {
  203. if (a.Sign)
  204. {
  205. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(uint))
  206. a.Bytes.RemoveAt(a.Length - 1);
  207. if (a.Length < sizeof(uint))
  208. a.Bytes.AddRange(new byte[sizeof(uint) - a.Length]);
  209. if (a.Length == sizeof(uint)) return BitConverter.ToUInt32(a.Bytes.ToArray(), 0);
  210. else throw new OverflowException("The LargeInteger was too big.");
  211. }
  212. else throw new InvalidCastException("Cannot convert a negative number to an unsigned type.");
  213. }
  214. public static explicit operator ulong(LargeInteger a)
  215. {
  216. if (a.Sign)
  217. {
  218. while (a.Bytes[a.Length - 1] == 0 && a.Length > sizeof(ulong))
  219. a.Bytes.RemoveAt(a.Length - 1);
  220. if (a.Length < sizeof(ulong))
  221. a.Bytes.AddRange(new byte[sizeof(ulong) - a.Length]);
  222. if (a.Length == sizeof(ulong)) return BitConverter.ToUInt64(a.Bytes.ToArray(), 0);
  223. else throw new OverflowException("The LargeInteger was too big.");
  224. }
  225. else throw new InvalidCastException("Cannot convert a negative number to an unsigned type.");
  226. }
  227. // Add more casts
  228. #endregion
  229. #region Operators
  230. public static LargeInteger operator +(LargeInteger left, LargeInteger right)
  231. {
  232. LargeInteger result = new LargeInteger();
  233. result.Bytes.AddRange(new byte[Math.Max(left.Length, right.Length)]); // Add as many bytes as needed for both the integers
  234. if (!left.Sign && !right.Sign)
  235. result.Sign = false;
  236. else if (left.Sign && right.Sign)
  237. result.Sign = true;
  238. else if (!left.Sign && right.Sign)
  239. {
  240. if (left.Length > right.Length)
  241. result.Sign = false;
  242. else if (left.Length < right.Length)
  243. result.Sign = true;
  244. else if (left.Length == right.Length)
  245. for (int i = 0; i < left.Length; i++)
  246. if (left.Bytes[i] != right.Bytes[i])
  247. {
  248. result.Sign = left.Bytes[left.Length - 1] < right.Bytes[right.Length - 1];
  249. break;
  250. }
  251. }
  252. else if (left.Sign && !right.Sign)
  253. {
  254. if (left.Length > right.Length)
  255. result.Sign = true;
  256. else if (left.Length < right.Length)
  257. result.Sign = false;
  258. else if (left.Length == right.Length)
  259. for (int i = 0; i < left.Length; i++)
  260. if (left.Bytes[i] != right.Bytes[i])
  261. {
  262. result.Sign = left.Bytes[left.Length - 1] > right.Bytes[right.Length - 1];
  263. break;
  264. }
  265. }
  266. for (int i = 0; i < result.Length; i++) // Insert the result per bytes
  267. {
  268. int sum = 0;
  269. if (i < left.Length && i < right.Length) // Add both numbers in the sum if the byte positions are in the bounds of both numbers' byte list
  270. {
  271. if (left.Sign && right.Sign) // If both numbers are positive
  272. sum = left.Bytes[i] + right.Bytes[i];
  273. else if (!left.Sign && right.Sign) // If the left number is negative and the other is positive
  274. sum = right.Bytes[i] - left.Bytes[i];
  275. else if (left.Sign && !right.Sign) // If the right number is negative and the other is positive
  276. sum = left.Bytes[i] - right.Bytes[i];
  277. else if (!left.Sign && !right.Sign) // If both numbers are negative
  278. sum = -left.Bytes[i] - right.Bytes[i];
  279. }
  280. else if (i < left.Length && i >= right.Length) // Only add the left number in the byte position if the byte index is out of range of the right number's byte list
  281. sum = left.Bytes[i] * (left.Sign ? 1 : -1);
  282. else if (i >= left.Length && i < right.Length) // Only add the right number in the byte position if the byte index is out of range of the left number's byte list
  283. sum = right.Bytes[i] * (right.Sign ? 1 : -1);
  284. if (sum >= 256 - result.Bytes[i] && sum > 0) // If the sum is positive and bigger than the max value of a byte
  285. {
  286. sum -= 256;
  287. int j = i + 1;
  288. do
  289. {
  290. result.Bytes[j]++;
  291. j++;
  292. }
  293. while (result.Bytes[j] == 0 && j < result.Length);
  294. if (result.Bytes[result.Length - 1] == 0 && j == result.Length) // If there is a need for a new byte in the list
  295. result.Bytes.Add(1);
  296. }
  297. else if (Math.Abs(sum) >= 256 - result.Bytes[i] && sum < 0) // If the sum is negative and its absolute value is bigger than the max value of a byte
  298. {
  299. sum = Math.Abs(sum);
  300. int j = i + 1;
  301. do
  302. {
  303. result.Bytes[j]++;
  304. j++;
  305. }
  306. while (result.Bytes[j] == 0 && j < result.Length);
  307. if (result.Bytes[result.Length - 1] == 0 && j == result.Length) // If there is a need for a new byte in the list
  308. result.Bytes.Add(1);
  309. }
  310. result.Bytes[i] += (byte)Math.Abs(sum);
  311. }
  312. return result;
  313. }
  314. public static LargeInteger operator -(LargeInteger left, LargeInteger right) => Clone(left) + (-Clone(right));
  315. public static LargeInteger operator *(LargeInteger left, LargeInteger right)
  316. {
  317. if (left == 0 || right == 0)
  318. return 0;
  319. else if (left == 1)
  320. return right;
  321. else if (right == 1)
  322. return left;
  323. else if (left == -1)
  324. return -right;
  325. else if (right == -1)
  326. return -left;
  327. else
  328. {
  329. LargeInteger result = 0;
  330. result.Sign = left.Sign == right.Sign;
  331. left = AbsoluteValue(left);
  332. right = AbsoluteValue(right);
  333.  
  334. while (right > 0)
  335. {
  336. LargeInteger temp = (right >> 1) << 1;
  337. if (temp != right) result += left;
  338. if ((left.Bytes[left.Length - 1] & 0x80) == 1)
  339. left.Bytes.Add(0);
  340. left <<= 1;
  341. right >>= 1;
  342. }
  343. return result;
  344. }
  345. }
  346. /*
  347. Copyright notice
  348.  
  349. Use of this program, for any purpose, is granted the author,
  350. Ian Kaplan, as long as this copyright notice is included in
  351. the source code or any source code derived from this program.
  352. The user assumes all responsibility for using this code.
  353.  
  354. Ian Kaplan, October 1996
  355. */
  356. // The division and modulus operations are using copyrighted code form the owner as stated in the previously pasted claim by Ian Kaplan
  357. // This is a transcription in C# from the source as written in C++, however copyright applies for the algorithm expressed as code
  358. // Motherfucker this wrongly positioned ~ operator killed me
  359. public static LargeInteger operator /(LargeInteger left, LargeInteger right)
  360. {
  361. if (right != 0)
  362. {
  363. LargeInteger absoluteLeft = AbsoluteValue(left);
  364. LargeInteger absoluteRight = AbsoluteValue(right);
  365. if (absoluteLeft == absoluteRight)
  366. return left.Sign == right.Sign ? 1 : -1;
  367. else if (absoluteRight == 1)
  368. return left * (left.Sign == right.Sign ? 1 : -1);
  369. else if (absoluteLeft < absoluteRight)
  370. return 0;
  371. else
  372. {
  373. LargeInteger result = 0;
  374. result.Sign = left.Sign == right.Sign;
  375. LargeInteger numBits = absoluteLeft.Length * 8;
  376. LargeInteger t, q, bit, d = 0;
  377. LargeInteger remainder = 0;
  378. while (remainder < absoluteRight)
  379. {
  380. bit = (absoluteLeft & (1 << (absoluteLeft.Length * 8 - 1))) >> (absoluteLeft.Length * 8 - 1);
  381. remainder = (remainder << 1) | bit;
  382. d = absoluteLeft;
  383. absoluteLeft <<= 1;
  384. numBits--;
  385. }
  386.  
  387. /* The loop, above, always goes one iteration too far.
  388. To avoid inserting an "if" statement inside the loop
  389. the last iteration is simply reversed. */
  390.  
  391. absoluteLeft = d;
  392. remainder = remainder >> 1;
  393. numBits++;
  394.  
  395. for (LargeInteger i = 0; i < numBits; i++)
  396. {
  397. bit = (absoluteLeft & (1 << (absoluteLeft.Length * 8 - 1))) >> (absoluteLeft.Length * 8 - 1);
  398. remainder = (remainder << 1) | bit;
  399. t = remainder - absoluteRight;
  400. q = ~(t & (1 << (t.Length * 8 - 1))) >> (t.Length * 8 - 1);
  401. absoluteLeft <<= 1;
  402. result = (result << 1) | q;
  403. if (q != 0)
  404. remainder = t;
  405. }
  406. return result;
  407. }
  408. }
  409. else throw new DivideByZeroException("Cannot divide by zero.");
  410. }
  411. public static LargeInteger operator %(LargeInteger left, LargeInteger right)
  412. {
  413. if (right != 0)
  414. {
  415. LargeInteger absoluteLeft = AbsoluteValue(left);
  416. LargeInteger absoluteRight = AbsoluteValue(right);
  417. if (absoluteLeft == absoluteRight || absoluteRight == 1)
  418. return 0;
  419. else if (absoluteLeft < absoluteRight)
  420. return Clone(left);
  421. else
  422. {
  423. LargeInteger numBits = left.Length * 8; // numBits = the number of bits of the dividend
  424. LargeInteger t, q, bit, d = 0; // t = temporary value, q = quotient, bit = last bit being checked, d = temporary dividend value for reversing previous operation
  425. LargeInteger remainder = 0;
  426. while (remainder < absoluteRight)
  427. {
  428. bit = (absoluteLeft & (1 << (absoluteLeft.Length * 8 - 1))) >> (absoluteLeft.Length * 8 - 1);
  429. remainder = (remainder << 1) | bit;
  430. d = absoluteLeft;
  431. absoluteLeft <<= 1;
  432. numBits--;
  433. }
  434.  
  435. /* The loop, above, always goes one iteration too far.
  436. To avoid inserting an "if" statement inside the loop
  437. the last iteration is simply reversed. */
  438.  
  439. absoluteLeft = d;
  440. remainder = remainder >> 1;
  441. numBits++;
  442.  
  443. for (LargeInteger i = 0; i < numBits; i++)
  444. {
  445. bit = (absoluteLeft & (1 << (absoluteLeft.Length * 8 - 1))) >> (absoluteLeft.Length * 8 - 1);
  446. remainder = (remainder << 1) | bit;
  447. t = remainder - absoluteRight;
  448. q = ~(t & (1 << (t.Length * 8 - 1))) >> (t.Length * 8 - 1);
  449. absoluteLeft <<= 1;
  450. if (q != 0)
  451. remainder = t;
  452. }
  453. return remainder;
  454. }
  455. }
  456. else throw new DivideByZeroException("Cannot divide by zero.");
  457. }
  458. public static LargeInteger operator ++(LargeInteger l) => l + 1;
  459. public static LargeInteger operator --(LargeInteger l) => l - 1;
  460. public static LargeInteger operator >>(LargeInteger left, int right)
  461. {
  462. if (left != 0)
  463. {
  464. LargeInteger result = Clone(left);
  465. int shifts = right % 8;
  466. int fullShifts = right / 8;
  467. if (fullShifts > 0)
  468. {
  469. for (int i = 0; i < result.Length - fullShifts; i++)
  470. result.Bytes[i] = result.Bytes[i + fullShifts];
  471. result.Bytes.RemoveRange(result.Length - fullShifts, fullShifts);
  472. }
  473. if (shifts > 0)
  474. {
  475. for (int i = 0; i < result.Length - 1; i++)
  476. result.Bytes[i] = (byte)((result.Bytes[i] >> shifts) + (result.Bytes[i + 1] << (8 - shifts)));
  477. result.Bytes[result.Length - 1] = (byte)(result.Bytes[result.Length - 1] >> shifts);
  478. }
  479. return result;
  480. }
  481. else return 0;
  482. }
  483. public static LargeInteger operator <<(LargeInteger left, int right)
  484. {
  485. if (left != 0)
  486. {
  487. LargeInteger result = Clone(left);
  488. int shifts = right % 8;
  489. int fullShifts = right / 8;
  490. for (int i = 0; i < fullShifts; i++)
  491. result.Bytes.Add(result.Bytes[i - fullShifts]);
  492. if (fullShifts > 0)
  493. {
  494. for (int i = result.Length - fullShifts; i > fullShifts; i--)
  495. result.Bytes[i] = result.Bytes[i - fullShifts];
  496. result.Bytes[fullShifts] = 0;
  497. fullShifts++;
  498. }
  499. if (shifts > 0)
  500. {
  501. for (int i = result.Length - 1; i > fullShifts; i--)
  502. result.Bytes[i] = (byte)((result.Bytes[i - 1] << shifts) | (result.Bytes[i] >> (8 - shifts)));
  503. result.Bytes[fullShifts] = (byte)(result.Bytes[fullShifts] << shifts);
  504. }
  505. return result;
  506. }
  507. else return 0;
  508. }
  509. public static LargeInteger operator -(LargeInteger l)
  510. {
  511. l.Sign = !l.Sign;
  512. return l;
  513. }
  514. public static LargeInteger operator &(LargeInteger left, LargeInteger right)
  515. {
  516. int minLength = Math.Min(left.Length, right.Length);
  517. byte[] bytes = new byte[minLength];
  518. for (int i = 0; i < minLength; i++)
  519. bytes[i] = (byte)(left.Bytes[i] & right.Bytes[i]);
  520. LargeInteger result = new LargeInteger(bytes);
  521. result.Sign = left.Sign & right.Sign;
  522. return result;
  523. }
  524. public static LargeInteger operator |(LargeInteger left, LargeInteger right)
  525. {
  526. int minLength = Math.Min(left.Length, right.Length);
  527. int maxLength = Math.Max(left.Length, right.Length);
  528. byte[] bytes = new byte[maxLength];
  529. for (int i = 0; i < minLength; i++)
  530. bytes[i] = (byte)(left.Bytes[i] | right.Bytes[i]);
  531. if (left.Length > right.Length)
  532. for (int i = minLength; i < maxLength; i++)
  533. bytes[i] = left.Bytes[i];
  534. else
  535. for (int i = minLength; i < maxLength; i++)
  536. bytes[i] = right.Bytes[i];
  537. LargeInteger result = new LargeInteger(bytes);
  538. result.Sign = left.Sign | right.Sign;
  539. return result;
  540. }
  541. public static LargeInteger operator ^(LargeInteger left, LargeInteger right)
  542. {
  543. int minLength = Math.Min(left.Length, right.Length);
  544. int maxLength = Math.Max(left.Length, right.Length);
  545. byte[] bytes = new byte[maxLength];
  546. for (int i = 0; i < minLength; i++)
  547. bytes[i] = (byte)(left.Bytes[i] ^ right.Bytes[i]);
  548. if (left.Length > right.Length)
  549. for (int i = minLength; i < maxLength; i++)
  550. bytes[i] = left.Bytes[i];
  551. else
  552. for (int i = minLength; i < maxLength; i++)
  553. bytes[i] = right.Bytes[i];
  554. LargeInteger result = new LargeInteger(bytes);
  555. result.Sign = left.Sign ^ right.Sign;
  556. return result;
  557. }
  558. public static LargeInteger operator ~(LargeInteger l)
  559. {
  560. LargeInteger result = Clone(l);
  561. for (int i = 0; i < l.Length; i++)
  562. result.Bytes[i] = (byte)~result.Bytes[i];
  563. return result;
  564. }
  565. public static bool operator >(LargeInteger left, LargeInteger right)
  566. {
  567. if (left.Sign && right.Sign)
  568. {
  569. if (left.Length > right.Length)
  570. return true;
  571. else if (left.Length < right.Length)
  572. return false;
  573. else
  574. for (int i = left.Length - 1; i >= 0; i--)
  575. if (left.Bytes[left.Length - 1] > right.Bytes[left.Length - 1])
  576. return true;
  577. return false;
  578. }
  579. else if (!left.Sign && !right.Sign)
  580. {
  581. if (left.Length < right.Length)
  582. return true;
  583. else if (left.Length > right.Length)
  584. return false;
  585. else
  586. for (int i = left.Length - 1; i >= 0; i--)
  587. if (left.Bytes[left.Length - 1] < right.Bytes[left.Length - 1])
  588. return true;
  589. return false;
  590. }
  591. else return left.Sign;
  592. }
  593. public static bool operator <(LargeInteger left, LargeInteger right)
  594. {
  595. if (left.Sign && right.Sign)
  596. {
  597. if (left.Length < right.Length)
  598. return true;
  599. else if (left.Length > right.Length)
  600. return false;
  601. else
  602. for (int i = left.Length - 1; i >= 0; i--)
  603. if (left.Bytes[left.Length - 1] < right.Bytes[left.Length - 1])
  604. return true;
  605. return false;
  606. }
  607. else if (!left.Sign && !right.Sign)
  608. {
  609. if (left.Length > right.Length)
  610. return true;
  611. else if (left.Length < right.Length)
  612. return false;
  613. else
  614. for (int i = left.Length - 1; i >= 0; i--)
  615. if (left.Bytes[left.Length - 1] > right.Bytes[left.Length - 1])
  616. return true;
  617. return false;
  618. }
  619. else return right.Sign;
  620. }
  621. public static bool operator >=(LargeInteger left, LargeInteger right) => left > right || left == right;
  622. public static bool operator <=(LargeInteger left, LargeInteger right) => left < right || left == right;
  623. public static bool operator ==(LargeInteger left, LargeInteger right)
  624. {
  625. if (left.Length != right.Length)
  626. return false;
  627. else if (left.Length == right.Length)
  628. for (int i = 0; i < left.Length; i++)
  629. if (left.Bytes[i] != right.Bytes[i])
  630. return false;
  631. return true;
  632. }
  633. public static bool operator !=(LargeInteger left, LargeInteger right)
  634. {
  635. if (left.Length != right.Length)
  636. return true;
  637. else if (left.Length == right.Length)
  638. for (int i = 0; i < left.Length; i++)
  639. if (left.Bytes[i] != right.Bytes[i])
  640. return true;
  641. return false;
  642. }
  643. #endregion
  644. #region Operations
  645. public static bool IsPrime(LargeInteger l)
  646. {
  647. bool result = false;
  648. LargeInteger sqrt = SquareRoot(l);
  649. for (int i = 2; i <= sqrt; i++)
  650. if (l % i == 0)
  651. break;
  652. else result = i == sqrt;
  653. return result;
  654. }
  655. public static bool TryParse(string str, out LargeInteger result)
  656. {
  657. result = 0;
  658. try { result = Parse(str); }
  659. catch { return false; }
  660. return true;
  661. }
  662. public static int GetDecimalDigitCount(LargeInteger l)
  663. {
  664. l = RemoveUnnecessaryBytes(l);
  665. int digCount = (l.Length - 1) * 2 + 1;
  666. for (int i = digCount; i < l.Length * 3; i++)
  667. if (l % Power(10, i) > 0)
  668. digCount = i;
  669. return digCount;
  670. }
  671. public static LargeInteger AbsoluteValue(LargeInteger l) => Clone(l >= 0 ? l : -l);
  672. public static LargeInteger Clone(LargeInteger l)
  673. {
  674. LargeInteger result = new LargeInteger();
  675. result.Sign = l.Sign;
  676. for (int i = 0; i < l.Length; i++)
  677. result.Bytes.Add(l.Bytes[i]);
  678. return result;
  679. }
  680. public static LargeInteger Factorial(LargeInteger n)
  681. {
  682. if (n == 0) return 1;
  683. else if (n > 0)
  684. {
  685. LargeInteger result = 1;
  686. for (LargeInteger i = 2; i <= n; i++)
  687. result *= i;
  688. return result;
  689. }
  690. else throw new ArithmeticException("Negative numbers cannot be factorized.");
  691. }
  692. public static LargeInteger GreatestCommonDivisor(LargeInteger a, LargeInteger b)
  693. {
  694. LargeInteger max = Max(a, b);
  695. LargeInteger GCD = 1;
  696. for (LargeInteger i = 1; i < max / 2; i++)
  697. if (a % i == 0 && b % i == 0)
  698. GCD = i;
  699. return GCD;
  700. }
  701. public static LargeInteger Invert(LargeInteger l) => 1 / l;
  702. public static LargeInteger LeastCommonMultiple(LargeInteger a, LargeInteger b) => a * b / GreatestCommonDivisor(a, b);
  703. public static LargeInteger Max(params LargeInteger[] n)
  704. {
  705. LargeInteger max = n[0];
  706. for (int i = 1; i < n.Length; i++)
  707. if (max < n[i])
  708. max = n[i];
  709. return max;
  710. }
  711. public static LargeInteger Min(params LargeInteger[] n)
  712. {
  713. LargeInteger min = n[0];
  714. for (int i = 1; i < n.Length; i++)
  715. if (min > n[i])
  716. min = n[i];
  717. return min;
  718. }
  719. public static LargeInteger Parse(string str)
  720. {
  721. LargeInteger result = 0;
  722. if (str[0] != 45) // If it's not a number character
  723. {
  724. str = str.Remove(0, 1);
  725. result.Sign = false;
  726. }
  727. if (str.Length > 0)
  728. {
  729. for (int i = 0; i < str.Length; i++)
  730. if (str[i] < 48 || str[i] > 57) // If it's not a number character
  731. throw new FormatException("The string is not a valid integral value.");
  732. for (int i = str.Length - 1; i >= 0; i--)
  733. result += str[i] * Power(10, i - str.Length + 1);
  734. }
  735. else throw new FormatException("The string represents no integral value.");
  736. return result;
  737. }
  738. public static LargeInteger Power(LargeInteger b, LargeInteger power)
  739. {
  740. if (b > 0)
  741. {
  742. if (power == 0)
  743. return 1;
  744. else if (power.Sign)
  745. {
  746. LargeInteger brainPower = AbsoluteValue(power);
  747. LargeInteger result = b;
  748. for (LargeInteger i = 2; i <= brainPower; i++)
  749. result *= b;
  750. return result;
  751. }
  752. else
  753. return 0;
  754. }
  755. else if (b != 0) return 1;
  756. else throw new ArithmeticException("Cannot perform the operation 0^0.");
  757. }
  758. public static LargeInteger Random(int length)
  759. {
  760. LargeInteger result = new LargeInteger();
  761. Random shit = new Random();
  762. result.Bytes = new List<byte>(length);
  763. for (int i = 0; i < length - 1; i++)
  764. result.Bytes[i] = (byte)shit.Next(0, 255);
  765. result.Bytes[length - 1] = (byte)shit.Next(1, 255);
  766. return result;
  767. }
  768. public static LargeInteger Random(int minLength, int maxLength)
  769. {
  770. LargeInteger result = new LargeInteger();
  771. Random shit = new Random();
  772. int length = shit.Next(minLength, maxLength);
  773. result.Bytes = new List<byte>(length);
  774. for (int i = 0; i < length - 1; i++)
  775. result.Bytes[i] = (byte)shit.Next(0, 255);
  776. result.Bytes[length - 1] = (byte)shit.Next(1, 255);
  777. return result;
  778. }
  779. public static LargeInteger Random(LargeInteger min, LargeInteger max)
  780. {
  781. if (min != max)
  782. {
  783. LargeInteger result = new LargeInteger();
  784. min = RemoveUnnecessaryBytes(min); // Clean the useless zeroes
  785. max = RemoveUnnecessaryBytes(max);
  786. Random shit = new Random();
  787. bool matchesMin = false;
  788. bool matchesMax = false;
  789. int length = shit.Next(min.Length, max.Length);
  790. result.Bytes = new List<byte>(length);
  791. if (length == min.Length)
  792. {
  793. result.Bytes[length - 1] = (byte)shit.Next(min.Bytes[length - 1], 255);
  794. matchesMin = result.Bytes[length - 1] == min.Bytes[length - 1];
  795. }
  796. else if (length == max.Length)
  797. {
  798. result.Bytes[length - 1] = (byte)shit.Next(1, max.Bytes[length - 1]);
  799. matchesMax = result.Bytes[length - 1] == max.Bytes[length - 1];
  800. }
  801. for (int i = length - 2; i >= 0; i--)
  802. {
  803. if (matchesMin)
  804. {
  805. result.Bytes[i] = (byte)shit.Next(min.Bytes[i], 255);
  806. matchesMin = result.Bytes[i] == min.Bytes[i];
  807. }
  808. else if (matchesMax)
  809. {
  810. result.Bytes[i] = (byte)shit.Next(min.Bytes[i], 255);
  811. matchesMin = result.Bytes[i] == min.Bytes[i];
  812. }
  813. else
  814. result.Bytes[i] = (byte)shit.Next(0, 255);
  815. }
  816. return result;
  817. }
  818. else return min;
  819. }
  820. private static LargeInteger RemoveUnnecessaryBytes(LargeInteger l)
  821. {
  822. int i = l.Length;
  823. while (i > 1 && l.Bytes[i - 1] == 0)
  824. i--;
  825. if (i < l.Length)
  826. l.Bytes.RemoveRange(i, l.Length - i);
  827. return l;
  828. }
  829. public static LargeInteger Root(LargeInteger b, LargeInteger rootClass)
  830. {
  831. int digCount = GetDecimalDigitCount(b);
  832. int maxSqrtCount = digCount / 2 + 1;
  833. int minSqrtCount = Math.Max((digCount / 2 - 1), 1);
  834. LargeInteger start = Power(10, (minSqrtCount - 1));
  835. LargeInteger end = Power(10, maxSqrtCount) - 1;
  836. LargeInteger middle = (start + end) / 2;
  837. LargeInteger power = 0;
  838. LargeInteger lastPower = 0;
  839. while ((power = Power(middle, rootClass)) != b && power != lastPower)
  840. {
  841. if (power < b)
  842. middle = (end + middle) / 2;
  843. else
  844. middle = (start + middle) / 2;
  845. lastPower = power;
  846. }
  847. return middle;
  848. }
  849. public static LargeInteger SquareRoot(LargeInteger l)
  850. {
  851. int digCount = GetDecimalDigitCount(l);
  852. int maxSqrtCount = digCount / 2 + 1;
  853. int minSqrtCount = Math.Max((digCount / 2 - 1), 1);
  854. LargeInteger start = Power(10, (minSqrtCount - 1));
  855. LargeInteger end = Power(10, maxSqrtCount) - 1;
  856. LargeInteger middle = (start + end) / 2;
  857. LargeInteger sq = 0;
  858. LargeInteger lastSq = 0;
  859. while ((sq = Power(middle, 2)) != l && sq != lastSq)
  860. {
  861. if (sq < l)
  862. middle = (end + middle) / 2;
  863. else
  864. middle = (start + middle) / 2;
  865. lastSq = sq;
  866. }
  867. return middle;
  868. }
  869. #endregion
  870. #region Overrides
  871. public override string ToString()
  872. {
  873. if (this != 0)
  874. {
  875. StringBuilder result = new StringBuilder();
  876. LargeInteger currentIntPart = Clone(this);
  877. for (; currentIntPart > 0; currentIntPart /= 10)
  878. result.Insert(0, (char)((currentIntPart % 10) + 48));
  879. if (!Sign) result.Insert(0, "-");
  880. return result.ToString();
  881. }
  882. else return "0";
  883. }
  884. #endregion
  885. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!