{"action":"created","comment":{"url":"https://api.github.com/repos/dotnet/corefx/pulls/comments/33497724","id":33497724,"diff_hunk":"@@ -0,0 +1,536 @@\n+﻿using System.Diagnostics;\n+using System.Security;\n+\n+namespace System.Numerics\n+{\n+    internal static partial class BigIntegerCalculator\n+    {\n+        // Executes different exponentiation algorithms, which are\n+        // basically based on the classic square-and-multiply method.\n+\n+        // https://en.wikipedia.org/wiki/Exponentiation_by_squaring\n+\n+        public static uint[] Pow(uint value, uint power)\n+        {\n+            // The basic pow method for a 32-bit integer.\n+            // To spare memory allocations we first roughly\n+            // estimate an upper bound for our buffers.\n+\n+            int tempLength = 1;\n+            int resultLength = 1;\n+\n+            PowBound(power, ref tempLength, ref resultLength);\n+\n+            BitsBuffer temp = new BitsBuffer(tempLength, value);\n+            BitsBuffer result = new BitsBuffer(resultLength, 1);\n+\n+            PowCore(power, temp, result);\n+\n+            return result.ToArray();\n+        }\n+\n+        public static uint[] Pow(uint[] value, uint power)\n+        {\n+            Debug.Assert(value != null);\n+\n+            // The basic pow method for a big integer.\n+            // To spare memory allocations we first roughly\n+            // estimate an upper bound for our buffers.\n+\n+            int tempLength = value.Length;\n+            int resultLength = 1;\n+\n+            PowBound(power, ref tempLength, ref resultLength);\n+\n+            BitsBuffer temp = new BitsBuffer(tempLength, value);\n+            BitsBuffer result = new BitsBuffer(resultLength, 1);\n+\n+            PowCore(power, temp, result);\n+\n+            return result.ToArray();\n+        }\n+\n+        private static void PowBound(uint power, ref int tempLength,\n+                                     ref int resultLength)\n+        {\n+            // The basic pow algorithm, but instead of squaring\n+            // and multiplying we just sum up the lengths.\n+\n+            while (power != 0)\n+            {\n+                if ((power & 1) == 1)\n+                    resultLength += tempLength;\n+                tempLength += tempLength;\n+                power = power >> 1;\n+            }\n+        }\n+\n+        private static void PowCore(uint power, BitsBuffer temp,\n+                                    BitsBuffer result)\n+        {\n+            // The basic pow algorithm using square-and-multiply.\n+\n+            while (power != 0)\n+            {\n+                if ((power & 1) == 1)\n+                    result.MultiplySelf(temp);\n+                temp.SquareSelf();\n+                power = power >> 1;\n+            }\n+        }\n+\n+        public static uint[] Pow(uint value, uint power, uint modulus)\n+        {\n+            // The 32-bit modulus pow method for a 32-bit integer\n+            // raised by a 32-bit integer...\n+\n+            uint result = PowCore(power, modulus, value, 1);\n+\n+            return new uint[] { result };\n+        }\n+\n+        public static uint[] Pow(uint[] value, uint power, uint modulus)\n+        {\n+            Debug.Assert(value != null);\n+\n+            // The 32-bit modulus pow method for a big integer\n+            // raised by a 32-bit integer...\n+\n+            uint temp = Remainder(value, modulus)[0];\n+\n+            uint result = PowCore(power, modulus, temp, 1);\n+\n+            return new uint[] { result };\n+        }\n+\n+        public static uint[] Pow(uint value, uint[] power, uint modulus)\n+        {\n+            Debug.Assert(power != null);\n+\n+            // The 32-bit modulus pow method for a 32-bit integer\n+            // raised by a big integer...\n+\n+            uint result = PowCore(power, modulus, value, 1);\n+\n+            return new uint[] { result };\n+        }\n+\n+        public static uint[] Pow(uint[] value, uint[] power, uint modulus)\n+        {\n+            Debug.Assert(value != null);\n+            Debug.Assert(power != null);\n+\n+            // The 32-bit modulus pow method for a big integer\n+            // raised by a big integer...\n+\n+            uint temp = Remainder(value, modulus)[0];\n+\n+            uint result = PowCore(power, modulus, temp, 1);\n+\n+            return new uint[] { result };\n+        }\n+\n+        private static uint PowCore(uint[] power, uint modulus,\n+                                    ulong temp, ulong result)\n+        {\n+            // The 32-bit modulus pow algorithm for all but\n+            // the last power limb using square-and-multiply.\n+\n+            for (int i = 0; i < power.Length - 1; i++)\n+            {\n+                uint p = power[i];\n+                for (int j = 0; j < 32; j++)\n+                {\n+                    if ((p & 1) == 1)\n+                        result = (result * temp) % modulus;\n+                    temp = (temp * temp) % modulus;\n+                    p = p >> 1;\n+                }\n+            }\n+\n+            return PowCore(power[power.Length - 1], modulus, temp, result);\n+        }\n+\n+        private static uint PowCore(uint power, uint modulus,\n+                                    ulong temp, ulong result)\n+        {\n+            // The 32-bit modulus pow algorithm for the last or\n+            // the only power limb using square-and-multiply.\n+\n+            while (power != 0)\n+            {\n+                if ((power & 1) == 1)\n+                    result = (result * temp) % modulus;\n+                temp = (temp * temp) % modulus;\n+                power = power >> 1;\n+            }\n+\n+            return (uint)(result % modulus);\n+        }\n+\n+        public static uint[] Pow(uint value, uint power, uint[] modulus)\n+        {\n+            Debug.Assert(modulus != null);\n+\n+            // The big modulus pow method for a 32-bit integer\n+            // raised by a 32-bit integer...\n+\n+            BitsBuffer temp = new BitsBuffer(modulus.Length * 2, value);\n+            BitsBuffer result = new BitsBuffer(modulus.Length * 2, 1);\n+            FastReducer reducer = new FastReducer(modulus);","path":"src/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowMod.cs","position":180,"original_position":180,"commit_id":"48f82690c32d238500c704a7d4f9c85e9eb901b6","original_commit_id":"48f82690c32d238500c704a7d4f9c85e9eb901b6","user":{"login":"axelheer","id":3988385,"avatar_url":"https://avatars.githubusercontent.com/u/3988385?v=3","gravatar_id":"","url":"https://api.github.com/users/axelheer","html_url":"https://github.com/axelheer","followers_url":"https://api.github.com/users/axelheer/followers","following_url":"https://api.github.com/users/axelheer/following{/other_user}","gists_url":"https://api.github.com/users/axelheer/gists{/gist_id}","starred_url":"https://api.github.com/users/axelheer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/axelheer/subscriptions","organizations_url":"https://api.github.com/users/axelheer/orgs","repos_url":"https://api.github.com/users/axelheer/repos","events_url":"https://api.github.com/users/axelheer/events{/privacy}","received_events_url":"https://api.github.com/users/axelheer/received_events","type":"User","site_admin":false},"body":"Actually, I invested a bit more in reducing allocations, since I've learned from our previous work that these are damn crucial (my original implementation just used the big-integer structure, thus relocated with every operation...). But let's have a look at the numbers:\r\n\r\n- The current implementation needs 4 \"builders\" (`regRes`, `regVal`, `regMod`, `regTmp`), the algorithm needs its values. I don't know any way how to use less than those 2 buffers.\r\n- One \"buffer\" allocates 2 arrays, one for the current value and one for the next, and switches between them. So the 2 is a constant value, no matter how many calculations are needed (the bigger the numbers, the more calculations). For 32-bit integers we are even buffer-free.\r\n- The \"reducer\" creates some overhead though, but the Barrett reduction needs it's μ, q and ˜q. As with the buffer the 3 is at least constant.\r\n\r\nSo, how can we squeeze this further?\r\n\r\n- As suggested, turning buffer and reducer into structures shouldn't be any problem. I've no idea why I've chosen classes anyway.\r\n- As already suspected at the beginning, the Barrett reduction may be not that efficient for smaller numbers (I'll investigate this further!). If that's the case, we can define a threshold for using an ordinary remainder, so we have this overhead only for the really big ones.\r\n\r\nSounds ok?","created_at":"2015-06-29T18:46:37Z","updated_at":"2015-06-29T18:46:37Z","html_url":"https://github.com/dotnet/corefx/pull/2182#discussion_r33497724","pull_request_url":"https://api.github.com/repos/dotnet/corefx/pulls/2182","_links":{"self":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/comments/33497724"},"html":{"href":"https://github.com/dotnet/corefx/pull/2182#discussion_r33497724"},"pull_request":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/2182"}}},"pull_request":{"url":"https://api.github.com/repos/dotnet/corefx/pulls/2182","id":38707273,"html_url":"https://github.com/dotnet/corefx/pull/2182","diff_url":"https://github.com/dotnet/corefx/pull/2182.diff","patch_url":"https://github.com/dotnet/corefx/pull/2182.patch","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/2182","number":2182,"state":"open","locked":false,"title":"Improve performance of BigInteger.Pow/ModPow","user":{"login":"axelheer","id":3988385,"avatar_url":"https://avatars.githubusercontent.com/u/3988385?v=3","gravatar_id":"","url":"https://api.github.com/users/axelheer","html_url":"https://github.com/axelheer","followers_url":"https://api.github.com/users/axelheer/followers","following_url":"https://api.github.com/users/axelheer/following{/other_user}","gists_url":"https://api.github.com/users/axelheer/gists{/gist_id}","starred_url":"https://api.github.com/users/axelheer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/axelheer/subscriptions","organizations_url":"https://api.github.com/users/axelheer/orgs","repos_url":"https://api.github.com/users/axelheer/repos","events_url":"https://api.github.com/users/axelheer/events{/privacy}","received_events_url":"https://api.github.com/users/axelheer/received_events","type":"User","site_admin":false},"body":"To introduce further performance tweaks, the exponentiation algorithms are ported to `BigIntegerCalculator`. Furthermore the newly introduced `FastReducer` triggers a bad corner case within the division algorithm, which gets fixed too.\r\n\r\nA basic performance comparison based on [this code](https://gist.github.com/axelheer/3b701c91271b7c762586) unveils the following results:\r\n\r\n# ModPow\r\n\r\n| # of bits | # of vals | before ms | after ms |\r\n|----------:|----------:|----------:|---------:|\r\n|        16 |   100,000 |        64 |       23 |\r\n|        64 |    10,000 |       145 |      202 |\r\n|       256 |     1,000 |       298 |      181 |\r\n|     1,024 |       100 |     1,344 |      637 |\r\n|     4,096 |        10 |     7,778 |    2,548 |\r\n|    16,384 |         1 |    48,292 |    9,595 |\r\n\r\n#1307","created_at":"2015-06-27T09:56:25Z","updated_at":"2015-06-29T18:46:37Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ffce5b184bb23459ea3cb13dd2c45293f7061c8a","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/dotnet/corefx/pulls/2182/commits","review_comments_url":"https://api.github.com/repos/dotnet/corefx/pulls/2182/comments","review_comment_url":"https://api.github.com/repos/dotnet/corefx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/2182/comments","statuses_url":"https://api.github.com/repos/dotnet/corefx/statuses/48f82690c32d238500c704a7d4f9c85e9eb901b6","head":{"label":"axelheer:biginteger-performance","ref":"biginteger-performance","sha":"48f82690c32d238500c704a7d4f9c85e9eb901b6","user":{"login":"axelheer","id":3988385,"avatar_url":"https://avatars.githubusercontent.com/u/3988385?v=3","gravatar_id":"","url":"https://api.github.com/users/axelheer","html_url":"https://github.com/axelheer","followers_url":"https://api.github.com/users/axelheer/followers","following_url":"https://api.github.com/users/axelheer/following{/other_user}","gists_url":"https://api.github.com/users/axelheer/gists{/gist_id}","starred_url":"https://api.github.com/users/axelheer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/axelheer/subscriptions","organizations_url":"https://api.github.com/users/axelheer/orgs","repos_url":"https://api.github.com/users/axelheer/repos","events_url":"https://api.github.com/users/axelheer/events{/privacy}","received_events_url":"https://api.github.com/users/axelheer/received_events","type":"User","site_admin":false},"repo":{"id":34116891,"name":"corefx","full_name":"axelheer/corefx","owner":{"login":"axelheer","id":3988385,"avatar_url":"https://avatars.githubusercontent.com/u/3988385?v=3","gravatar_id":"","url":"https://api.github.com/users/axelheer","html_url":"https://github.com/axelheer","followers_url":"https://api.github.com/users/axelheer/followers","following_url":"https://api.github.com/users/axelheer/following{/other_user}","gists_url":"https://api.github.com/users/axelheer/gists{/gist_id}","starred_url":"https://api.github.com/users/axelheer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/axelheer/subscriptions","organizations_url":"https://api.github.com/users/axelheer/orgs","repos_url":"https://api.github.com/users/axelheer/repos","events_url":"https://api.github.com/users/axelheer/events{/privacy}","received_events_url":"https://api.github.com/users/axelheer/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/axelheer/corefx","description":"This repo contains the .NET Core foundational libraries, called CoreFX. It includes classes for collections, file systems, console, XML, async and many others.","fork":true,"url":"https://api.github.com/repos/axelheer/corefx","forks_url":"https://api.github.com/repos/axelheer/corefx/forks","keys_url":"https://api.github.com/repos/axelheer/corefx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/axelheer/corefx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/axelheer/corefx/teams","hooks_url":"https://api.github.com/repos/axelheer/corefx/hooks","issue_events_url":"https://api.github.com/repos/axelheer/corefx/issues/events{/number}","events_url":"https://api.github.com/repos/axelheer/corefx/events","assignees_url":"https://api.github.com/repos/axelheer/corefx/assignees{/user}","branches_url":"https://api.github.com/repos/axelheer/corefx/branches{/branch}","tags_url":"https://api.github.com/repos/axelheer/corefx/tags","blobs_url":"https://api.github.com/repos/axelheer/corefx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/axelheer/corefx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/axelheer/corefx/git/refs{/sha}","trees_url":"https://api.github.com/repos/axelheer/corefx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/axelheer/corefx/statuses/{sha}","languages_url":"https://api.github.com/repos/axelheer/corefx/languages","stargazers_url":"https://api.github.com/repos/axelheer/corefx/stargazers","contributors_url":"https://api.github.com/repos/axelheer/corefx/contributors","subscribers_url":"https://api.github.com/repos/axelheer/corefx/subscribers","subscription_url":"https://api.github.com/repos/axelheer/corefx/subscription","commits_url":"https://api.github.com/repos/axelheer/corefx/commits{/sha}","git_commits_url":"https://api.github.com/repos/axelheer/corefx/git/commits{/sha}","comments_url":"https://api.github.com/repos/axelheer/corefx/comments{/number}","issue_comment_url":"https://api.github.com/repos/axelheer/corefx/issues/comments{/number}","contents_url":"https://api.github.com/repos/axelheer/corefx/contents/{+path}","compare_url":"https://api.github.com/repos/axelheer/corefx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/axelheer/corefx/merges","archive_url":"https://api.github.com/repos/axelheer/corefx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/axelheer/corefx/downloads","issues_url":"https://api.github.com/repos/axelheer/corefx/issues{/number}","pulls_url":"https://api.github.com/repos/axelheer/corefx/pulls{/number}","milestones_url":"https://api.github.com/repos/axelheer/corefx/milestones{/number}","notifications_url":"https://api.github.com/repos/axelheer/corefx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/axelheer/corefx/labels{/name}","releases_url":"https://api.github.com/repos/axelheer/corefx/releases{/id}","created_at":"2015-04-17T13:03:03Z","updated_at":"2015-04-30T09:05:49Z","pushed_at":"2015-06-27T09:54:08Z","git_url":"git://github.com/axelheer/corefx.git","ssh_url":"git@github.com:axelheer/corefx.git","clone_url":"https://github.com/axelheer/corefx.git","svn_url":"https://github.com/axelheer/corefx","homepage":"","size":22291,"stargazers_count":0,"watchers_count":0,"language":"C#","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"dotnet:master","ref":"master","sha":"45f21225e88a9959c93293c87a4348b333e572dd","user":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"repo":{"id":26295345,"name":"corefx","full_name":"dotnet/corefx","owner":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/dotnet/corefx","description":"This repo contains the .NET Core foundational libraries, called CoreFX. It includes classes for collections, file systems, console, XML, async and many others.","fork":false,"url":"https://api.github.com/repos/dotnet/corefx","forks_url":"https://api.github.com/repos/dotnet/corefx/forks","keys_url":"https://api.github.com/repos/dotnet/corefx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/dotnet/corefx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/dotnet/corefx/teams","hooks_url":"https://api.github.com/repos/dotnet/corefx/hooks","issue_events_url":"https://api.github.com/repos/dotnet/corefx/issues/events{/number}","events_url":"https://api.github.com/repos/dotnet/corefx/events","assignees_url":"https://api.github.com/repos/dotnet/corefx/assignees{/user}","branches_url":"https://api.github.com/repos/dotnet/corefx/branches{/branch}","tags_url":"https://api.github.com/repos/dotnet/corefx/tags","blobs_url":"https://api.github.com/repos/dotnet/corefx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/dotnet/corefx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/dotnet/corefx/git/refs{/sha}","trees_url":"https://api.github.com/repos/dotnet/corefx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/dotnet/corefx/statuses/{sha}","languages_url":"https://api.github.com/repos/dotnet/corefx/languages","stargazers_url":"https://api.github.com/repos/dotnet/corefx/stargazers","contributors_url":"https://api.github.com/repos/dotnet/corefx/contributors","subscribers_url":"https://api.github.com/repos/dotnet/corefx/subscribers","subscription_url":"https://api.github.com/repos/dotnet/corefx/subscription","commits_url":"https://api.github.com/repos/dotnet/corefx/commits{/sha}","git_commits_url":"https://api.github.com/repos/dotnet/corefx/git/commits{/sha}","comments_url":"https://api.github.com/repos/dotnet/corefx/comments{/number}","issue_comment_url":"https://api.github.com/repos/dotnet/corefx/issues/comments{/number}","contents_url":"https://api.github.com/repos/dotnet/corefx/contents/{+path}","compare_url":"https://api.github.com/repos/dotnet/corefx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/dotnet/corefx/merges","archive_url":"https://api.github.com/repos/dotnet/corefx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/dotnet/corefx/downloads","issues_url":"https://api.github.com/repos/dotnet/corefx/issues{/number}","pulls_url":"https://api.github.com/repos/dotnet/corefx/pulls{/number}","milestones_url":"https://api.github.com/repos/dotnet/corefx/milestones{/number}","notifications_url":"https://api.github.com/repos/dotnet/corefx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/dotnet/corefx/labels{/name}","releases_url":"https://api.github.com/repos/dotnet/corefx/releases{/id}","created_at":"2014-11-06T23:42:48Z","updated_at":"2015-06-29T16:46:33Z","pushed_at":"2015-06-29T18:46:00Z","git_url":"git://github.com/dotnet/corefx.git","ssh_url":"git@github.com:dotnet/corefx.git","clone_url":"https://github.com/dotnet/corefx.git","svn_url":"https://github.com/dotnet/corefx","homepage":"http://dotnet.github.io/core/","size":49585,"stargazers_count":7975,"watchers_count":7975,"language":"C#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1639,"mirror_url":null,"open_issues_count":442,"forks":1639,"open_issues":442,"watchers":7975,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/2182"},"html":{"href":"https://github.com/dotnet/corefx/pull/2182"},"issue":{"href":"https://api.github.com/repos/dotnet/corefx/issues/2182"},"comments":{"href":"https://api.github.com/repos/dotnet/corefx/issues/2182/comments"},"review_comments":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/2182/comments"},"review_comment":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/dotnet/corefx/pulls/2182/commits"},"statuses":{"href":"https://api.github.com/repos/dotnet/corefx/statuses/48f82690c32d238500c704a7d4f9c85e9eb901b6"}}}}