One of the new features in .NET 4.0 is the BigInteger class. This was suppose to be part of 3.5 framework, but after the CTP it was gone. Now it’s back. This big integer is a really large integer representation. However, I was not able to find the precision documented anywhere.<\/p>\n
The class is available in the System.Numerics namespace and provides overloaded operators, parsing methods and other utility features for bit integer numbers.<\/p>\n
Not very long ago, on codexpert.ro<\/a> we launched a contest for finding the biggest pair of amicable numbers<\/a>. One of the members (crystyce) that submited a solution found this big pair (2724918040393706557785752240819405848576, 2724918040396184856306258038787235905536) with a C++ implementation<\/a> using a 3rd party BigInt class. I decided to put that in C# 4.0 and use BigInteger. Maybe you can find things to optimize in the below code, but that’s not the point here. I’m showing you this code just to get a feeling of BitInteger.<\/p>\n As you can see, it was very fast finding the same big pair. Well it was at least on my 2 core machine.<\/p>\n The only thing I don't understand about the implementation is the presence of some helper functions in the BigInteger class.<\/p>\n That belongs to System.Math<\/b>, or maybe to a System.Numerics.Math<\/b> class. They are all helper functions, not specific to the implementation of the big integer; and the implementation does not depend on the existing of these functions. So they are clearly utility functions. They should go somewhere else. I have submitted this as feedback to Microsoft Connect. If you agree with it, vote for it here<\/a>. Of course, if you have arguments for the current implementation, you can vote against it too.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" One of the new features in .NET 4.0 is the BigInteger class. This was suppose to be part of 3.5 framework, but after the CTP it was gone. Now it’s back. This big integer is a really large integer representation. However, I was not able to find the precision documented anywhere. The class is available … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[11,20],"tags":[451,97,98,89],"class_list":["post-211","post","type-post","status-publish","format-standard","hentry","category-csharp","category-ctps-betas","tag-c","tag-integer","tag-numerics","tag-vs2010"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\r\nusing System.Numerics;\r\n\r\nnamespace cs_test\r\n{\r\n static class Amicable\r\n {\r\n public static BigInteger Pow2(BigInteger exp)\r\n {\r\n BigInteger res = 1;\r\n\r\n for (BigInteger i = 0; i < exp; i++)\r\n res *= 2;\r\n\r\n return res;\r\n }\r\n\r\n public static BigInteger ExpMod(BigInteger value, BigInteger exp, BigInteger mod)\r\n {\r\n BigInteger ullResult = 1;\r\n BigInteger ullValue = value;\r\n\r\n while (exp > 0)\r\n {\r\n if (exp % 2 != 0)\r\n { \/\/ odd\r\n ullResult *= ullValue;\r\n ullResult %= mod;\r\n }\r\n\r\n ullValue *= ullValue;\r\n ullValue %= mod;\r\n exp \/= 2;\r\n }\r\n\r\n return (ullResult);\r\n }\r\n\r\n static public bool IsMillerRabinPrime(BigInteger prime)\r\n {\r\n \/\/ randomWitness = witness that the \"prime\" is NOT composite\r\n \/\/ 1 < randomWitness < prime-1\r\n long totalWitness = 15;\r\n BigInteger [] randomWitness = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51001, 351011};\r\n BigInteger primeMinusOne = prime - 1;\r\n BigInteger oddMultiplier;\r\n long bitLength;\r\n long i, j;\r\n BigInteger result;\r\n \/\/ find oddMultiplier, defined as \"prime - 1 = (2^B) * M\"\r\n \/\/ get bitLength (B) and find the oddMultiplier (M)\r\n\r\n \/\/ init value multiplier\r\n oddMultiplier = primeMinusOne;\r\n\r\n bitLength = 0; \/\/ reset\r\n while(oddMultiplier % 2 == 0)\r\n {\r\n oddMultiplier \/= 2;\r\n bitLength++;\r\n }\r\n for(i = 0; i < totalWitness; i++)\r\n {\r\n if (randomWitness[i] == prime)\r\n return true;\r\n\r\n \/\/ init value of result = (randomWitness ^ oddMultiplier) mod prime\r\n result = ExpMod(randomWitness[i], oddMultiplier, prime);\r\n\r\n \/\/ is y = 1 ?\r\n if(result == 1)\r\n continue; \/\/ maybe prime\r\n\r\n \/\/ is y = prime-1 ?\r\n if(result == primeMinusOne)\r\n continue; \/\/ maybe prime\r\n\r\n \/\/ loop to get AT LEAST one \"result = primeMinusOne\"\r\n for(j = 1; j <= bitLength; j++)\r\n {\r\n \/\/ square of result\r\n result = ExpMod(result, 2, prime);\r\n\r\n \/\/ is result = primeMinusOne ?\r\n if(result == primeMinusOne)\r\n break; \/\/ maybe prime\r\n }\r\n\r\n if(result != primeMinusOne)\r\n return false; \/\/ COMPOSITE\r\n }\r\n\r\n \/\/ it may be pseudoprime\/prime\r\n return true;\r\n }\r\n\r\n }\r\n\r\n class Program\r\n {\r\n const int STARTM = 1;\r\n const int STOPM = 100;\r\n const int STOPN = 30;\r\n\r\n static void Main(string[] args)\r\n {\r\n DateTime start = DateTime.Now;\r\n\r\n for (BigInteger m = STARTM ; m <= STOPM ; m++)\r\n {\r\n for (BigInteger n = m+1 ; n <= m+STOPN ; n++)\r\n {\r\n BigInteger p = Amicable.Pow2(n) + Amicable.Pow2(m) - 1;\r\n if (!Amicable.IsMillerRabinPrime(p)) continue;\r\n \r\n BigInteger q = Amicable.Pow2(2 * n - m) + Amicable.Pow2(n) - 1;\r\n if (!Amicable.IsMillerRabinPrime(q)) continue;\r\n\r\n BigInteger r = Amicable.Pow2(3 * n - m) + \r\n Amicable.Pow2(n + m) + \r\n Amicable.Pow2(2 * n + 1) - 1;\r\n if (!Amicable.IsMillerRabinPrime(r)) continue;\r\n\r\n BigInteger f1 = Amicable.Pow2(n) * p * q;\r\n BigInteger f2 = Amicable.Pow2(n) * r;\r\n\r\n DateTime end = DateTime.Now;\r\n Console.WriteLine(\r\n \"{2} ... {0}, {1}\", \r\n f1, \r\n f2, \r\n (end - start).Milliseconds \/ 1000.0);\r\n }\r\n }\r\n }\r\n }\r\n}\r\n<\/pre>\n\r\n0.017 ... 220, 284\r\n0.021 ... 2172649216, 2181168896\r\n0.028 ... 17296, 18416\r\n0.040 ... 9363584, 9437056\r\n0.138 ... 2.7249180403937065577857522408E+39, 2.7249180403961848563062580388E+39\r\n<\/pre>\n
\r\npublic static BigInteger Abs(BigInteger value);\r\npublic static BigInteger Add(BigInteger left, BigInteger right);\r\npublic static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right);\r\npublic static BigInteger Divide(BigInteger dividend, BigInteger divisor);\r\npublic static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder);\r\npublic static double Log(BigInteger value);\r\npublic static double Log(BigInteger value, double baseValue);\r\npublic static double Log10(BigInteger value);\r\npublic static BigInteger Max(BigInteger left, BigInteger right);\r\npublic static BigInteger Min(BigInteger left, BigInteger right);\r\npublic static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus);\r\npublic static BigInteger Multiply(BigInteger left, BigInteger right);\r\npublic static BigInteger Negate(BigInteger value);\r\npublic static BigInteger Pow(BigInteger value, int exponent);\r\npublic static BigInteger Remainder(BigInteger dividend, BigInteger divisor);\r\npublic static BigInteger Subtract(BigInteger left, BigInteger right);\r\n<\/pre>\n