{"action":"created","comment":{"url":"https://api.github.com/repos/indutny/bn.js/pulls/comments/29033115","id":29033115,"diff_hunk":"@@ -885,13 +885,212 @@ BN.prototype._bigMulTo = function _bigMulTo(num, out) {\n \n BN.prototype.mulTo = function mulTo(num, out) {\n   var res;\n-  if (this.length + num.length < 63)\n+  var len = this.length + num.length;\n+  if (len < 63)\n     res = this._smallMulTo(num, out);\n-  else\n+  else if (len < 1024)\n     res = this._bigMulTo(num, out);\n+  else\n+    res = this._bigMulToF(num, out);\n   return res;\n };\n \n+\n+// Private\n+\n+function FFTM(x, y) {\n+  this.x = x;\n+  this.y = y;\n+}\n+\n+FFTM.prototype.makeRBT = function makeRBT(N) {\n+  var t = new Array(N);\n+  var l = (Math.log(N) / Math.log(2)) | 0;\n+  for (var i = 0; i < N; i++) {\n+    t[i] = this.revbin(i, l, N);\n+  }\n+\n+  return t;\n+};\n+\n+FFTM.prototype.revbin = function revbin(x, l, N) {\n+  if (x === 0 || x === N - 1)\n+    return x;\n+\n+  var rb = 0;\n+  for (var i = 0; i < l; i++) {\n+    rb |= (x & 1) << (l - i - 1);\n+    x >>= 1;\n+  }\n+\n+  return rb;\n+};\n+\n+FFTM.prototype.permute = function permute(rbt, rws, iws, rtws, itws, N) {\n+  for (var i = 0; i < N; i++) {\n+    rtws[i] = rws[rbt[i]];\n+    itws[i] = iws[rbt[i]];\n+  }\n+};\n+\n+FFTM.prototype.transform = function transform(rws, iws, rtws, itws, N, rbt) {\n+  this.permute(rbt, rws, iws, rtws, itws, N);\n+\n+  for (var s = 1; s < N; s <<= 1) {\n+    var l = s << 1;\n+\n+    var rtwdf = Math.cos(2 * Math.PI / l);\n+    var itwdf = Math.sin(2 * Math.PI / l);\n+\n+    for (var p = 0; p < N; p += l) {\n+      var rtwdf_ = rtwdf;\n+      var itwdf_ = itwdf;\n+\n+      for (var j = 0; j < s; j++) {\n+        var re = rtws[p + j];\n+        var ie = itws[p + j];\n+\n+        var ro = rtws[p + j + s];\n+        var io = itws[p + j + s];\n+\n+        var rx = rtwdf_ * ro - itwdf_ * io;\n+\n+        io = rtwdf_ * io + itwdf_ * ro;\n+        ro = rx;\n+\n+        rtws[p + j] = re + ro;\n+        itws[p + j] = ie + io;\n+\n+        rtws[p + j + s] = re - ro;","path":"lib/bn.js","position":85,"original_position":82,"commit_id":"e243372d044621b6711ea6304ad70b7d2d99e0cc","original_commit_id":"b3b5d959b6cb9dd2f8fc270fe8a64b9a54151d1c","user":{"login":"indutny","id":238531,"avatar_url":"https://avatars.githubusercontent.com/u/238531?v=3","gravatar_id":"","url":"https://api.github.com/users/indutny","html_url":"https://github.com/indutny","followers_url":"https://api.github.com/users/indutny/followers","following_url":"https://api.github.com/users/indutny/following{/other_user}","gists_url":"https://api.github.com/users/indutny/gists{/gist_id}","starred_url":"https://api.github.com/users/indutny/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/indutny/subscriptions","organizations_url":"https://api.github.com/users/indutny/orgs","repos_url":"https://api.github.com/users/indutny/repos","events_url":"https://api.github.com/users/indutny/events{/privacy}","received_events_url":"https://api.github.com/users/indutny/received_events","type":"User","site_admin":false},"body":"NOTE: order of this two statements is actually reversed","created_at":"2015-04-24T08:44:19Z","updated_at":"2015-04-24T08:44:20Z","html_url":"https://github.com/indutny/bn.js/pull/27#discussion_r29033115","pull_request_url":"https://api.github.com/repos/indutny/bn.js/pulls/27","_links":{"self":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/comments/29033115"},"html":{"href":"https://github.com/indutny/bn.js/pull/27#discussion_r29033115"},"pull_request":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/27"}}},"pull_request":{"url":"https://api.github.com/repos/indutny/bn.js/pulls/27","id":26041878,"html_url":"https://github.com/indutny/bn.js/pull/27","diff_url":"https://github.com/indutny/bn.js/pull/27.diff","patch_url":"https://github.com/indutny/bn.js/pull/27.patch","issue_url":"https://api.github.com/repos/indutny/bn.js/issues/27","number":27,"state":"open","locked":false,"title":"Introduced FFT to multiply jumbo BIs","user":{"login":"alexeykudinkin","id":428277,"avatar_url":"https://avatars.githubusercontent.com/u/428277?v=3","gravatar_id":"","url":"https://api.github.com/users/alexeykudinkin","html_url":"https://github.com/alexeykudinkin","followers_url":"https://api.github.com/users/alexeykudinkin/followers","following_url":"https://api.github.com/users/alexeykudinkin/following{/other_user}","gists_url":"https://api.github.com/users/alexeykudinkin/gists{/gist_id}","starred_url":"https://api.github.com/users/alexeykudinkin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexeykudinkin/subscriptions","organizations_url":"https://api.github.com/users/alexeykudinkin/orgs","repos_url":"https://api.github.com/users/alexeykudinkin/repos","events_url":"https://api.github.com/users/alexeykudinkin/events{/privacy}","received_events_url":"https://api.github.com/users/alexeykudinkin/received_events","type":"User","site_admin":false},"body":"It's around ~20% fast upon (DH groups fixture samples) comparing with default implementation, however staying far behind OpenSSL's native implementation. \r\n\r\nJust for fun.","created_at":"2014-12-15T00:29:37Z","updated_at":"2015-04-24T08:44:19Z","closed_at":null,"merged_at":null,"merge_commit_sha":"411f258b0652754f644bae491c7149259b53ff39","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/indutny/bn.js/pulls/27/commits","review_comments_url":"https://api.github.com/repos/indutny/bn.js/pulls/27/comments","review_comment_url":"https://api.github.com/repos/indutny/bn.js/pulls/comments{/number}","comments_url":"https://api.github.com/repos/indutny/bn.js/issues/27/comments","statuses_url":"https://api.github.com/repos/indutny/bn.js/statuses/e243372d044621b6711ea6304ad70b7d2d99e0cc","head":{"label":"alexeykudinkin:fftX","ref":"fftX","sha":"e243372d044621b6711ea6304ad70b7d2d99e0cc","user":{"login":"alexeykudinkin","id":428277,"avatar_url":"https://avatars.githubusercontent.com/u/428277?v=3","gravatar_id":"","url":"https://api.github.com/users/alexeykudinkin","html_url":"https://github.com/alexeykudinkin","followers_url":"https://api.github.com/users/alexeykudinkin/followers","following_url":"https://api.github.com/users/alexeykudinkin/following{/other_user}","gists_url":"https://api.github.com/users/alexeykudinkin/gists{/gist_id}","starred_url":"https://api.github.com/users/alexeykudinkin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexeykudinkin/subscriptions","organizations_url":"https://api.github.com/users/alexeykudinkin/orgs","repos_url":"https://api.github.com/users/alexeykudinkin/repos","events_url":"https://api.github.com/users/alexeykudinkin/events{/privacy}","received_events_url":"https://api.github.com/users/alexeykudinkin/received_events","type":"User","site_admin":false},"repo":{"id":28012933,"name":"bn.js","full_name":"alexeykudinkin/bn.js","owner":{"login":"alexeykudinkin","id":428277,"avatar_url":"https://avatars.githubusercontent.com/u/428277?v=3","gravatar_id":"","url":"https://api.github.com/users/alexeykudinkin","html_url":"https://github.com/alexeykudinkin","followers_url":"https://api.github.com/users/alexeykudinkin/followers","following_url":"https://api.github.com/users/alexeykudinkin/following{/other_user}","gists_url":"https://api.github.com/users/alexeykudinkin/gists{/gist_id}","starred_url":"https://api.github.com/users/alexeykudinkin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexeykudinkin/subscriptions","organizations_url":"https://api.github.com/users/alexeykudinkin/orgs","repos_url":"https://api.github.com/users/alexeykudinkin/repos","events_url":"https://api.github.com/users/alexeykudinkin/events{/privacy}","received_events_url":"https://api.github.com/users/alexeykudinkin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/alexeykudinkin/bn.js","description":"BigNum in pure javascript","fork":true,"url":"https://api.github.com/repos/alexeykudinkin/bn.js","forks_url":"https://api.github.com/repos/alexeykudinkin/bn.js/forks","keys_url":"https://api.github.com/repos/alexeykudinkin/bn.js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/alexeykudinkin/bn.js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/alexeykudinkin/bn.js/teams","hooks_url":"https://api.github.com/repos/alexeykudinkin/bn.js/hooks","issue_events_url":"https://api.github.com/repos/alexeykudinkin/bn.js/issues/events{/number}","events_url":"https://api.github.com/repos/alexeykudinkin/bn.js/events","assignees_url":"https://api.github.com/repos/alexeykudinkin/bn.js/assignees{/user}","branches_url":"https://api.github.com/repos/alexeykudinkin/bn.js/branches{/branch}","tags_url":"https://api.github.com/repos/alexeykudinkin/bn.js/tags","blobs_url":"https://api.github.com/repos/alexeykudinkin/bn.js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/alexeykudinkin/bn.js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/alexeykudinkin/bn.js/git/refs{/sha}","trees_url":"https://api.github.com/repos/alexeykudinkin/bn.js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/alexeykudinkin/bn.js/statuses/{sha}","languages_url":"https://api.github.com/repos/alexeykudinkin/bn.js/languages","stargazers_url":"https://api.github.com/repos/alexeykudinkin/bn.js/stargazers","contributors_url":"https://api.github.com/repos/alexeykudinkin/bn.js/contributors","subscribers_url":"https://api.github.com/repos/alexeykudinkin/bn.js/subscribers","subscription_url":"https://api.github.com/repos/alexeykudinkin/bn.js/subscription","commits_url":"https://api.github.com/repos/alexeykudinkin/bn.js/commits{/sha}","git_commits_url":"https://api.github.com/repos/alexeykudinkin/bn.js/git/commits{/sha}","comments_url":"https://api.github.com/repos/alexeykudinkin/bn.js/comments{/number}","issue_comment_url":"https://api.github.com/repos/alexeykudinkin/bn.js/issues/comments{/number}","contents_url":"https://api.github.com/repos/alexeykudinkin/bn.js/contents/{+path}","compare_url":"https://api.github.com/repos/alexeykudinkin/bn.js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/alexeykudinkin/bn.js/merges","archive_url":"https://api.github.com/repos/alexeykudinkin/bn.js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/alexeykudinkin/bn.js/downloads","issues_url":"https://api.github.com/repos/alexeykudinkin/bn.js/issues{/number}","pulls_url":"https://api.github.com/repos/alexeykudinkin/bn.js/pulls{/number}","milestones_url":"https://api.github.com/repos/alexeykudinkin/bn.js/milestones{/number}","notifications_url":"https://api.github.com/repos/alexeykudinkin/bn.js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/alexeykudinkin/bn.js/labels{/name}","releases_url":"https://api.github.com/repos/alexeykudinkin/bn.js/releases{/id}","created_at":"2014-12-15T00:06:16Z","updated_at":"2015-02-09T19:07:55Z","pushed_at":"2015-04-23T21:08:28Z","git_url":"git://github.com/alexeykudinkin/bn.js.git","ssh_url":"git@github.com:alexeykudinkin/bn.js.git","clone_url":"https://github.com/alexeykudinkin/bn.js.git","svn_url":"https://github.com/alexeykudinkin/bn.js","homepage":"","size":424,"stargazers_count":0,"watchers_count":0,"language":"JavaScript","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":"indutny:master","ref":"master","sha":"7178cd22cc649077eeebb259952f0897da483397","user":{"login":"indutny","id":238531,"avatar_url":"https://avatars.githubusercontent.com/u/238531?v=3","gravatar_id":"","url":"https://api.github.com/users/indutny","html_url":"https://github.com/indutny","followers_url":"https://api.github.com/users/indutny/followers","following_url":"https://api.github.com/users/indutny/following{/other_user}","gists_url":"https://api.github.com/users/indutny/gists{/gist_id}","starred_url":"https://api.github.com/users/indutny/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/indutny/subscriptions","organizations_url":"https://api.github.com/users/indutny/orgs","repos_url":"https://api.github.com/users/indutny/repos","events_url":"https://api.github.com/users/indutny/events{/privacy}","received_events_url":"https://api.github.com/users/indutny/received_events","type":"User","site_admin":false},"repo":{"id":19176350,"name":"bn.js","full_name":"indutny/bn.js","owner":{"login":"indutny","id":238531,"avatar_url":"https://avatars.githubusercontent.com/u/238531?v=3","gravatar_id":"","url":"https://api.github.com/users/indutny","html_url":"https://github.com/indutny","followers_url":"https://api.github.com/users/indutny/followers","following_url":"https://api.github.com/users/indutny/following{/other_user}","gists_url":"https://api.github.com/users/indutny/gists{/gist_id}","starred_url":"https://api.github.com/users/indutny/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/indutny/subscriptions","organizations_url":"https://api.github.com/users/indutny/orgs","repos_url":"https://api.github.com/users/indutny/repos","events_url":"https://api.github.com/users/indutny/events{/privacy}","received_events_url":"https://api.github.com/users/indutny/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/indutny/bn.js","description":"BigNum in pure javascript","fork":false,"url":"https://api.github.com/repos/indutny/bn.js","forks_url":"https://api.github.com/repos/indutny/bn.js/forks","keys_url":"https://api.github.com/repos/indutny/bn.js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/indutny/bn.js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/indutny/bn.js/teams","hooks_url":"https://api.github.com/repos/indutny/bn.js/hooks","issue_events_url":"https://api.github.com/repos/indutny/bn.js/issues/events{/number}","events_url":"https://api.github.com/repos/indutny/bn.js/events","assignees_url":"https://api.github.com/repos/indutny/bn.js/assignees{/user}","branches_url":"https://api.github.com/repos/indutny/bn.js/branches{/branch}","tags_url":"https://api.github.com/repos/indutny/bn.js/tags","blobs_url":"https://api.github.com/repos/indutny/bn.js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/indutny/bn.js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/indutny/bn.js/git/refs{/sha}","trees_url":"https://api.github.com/repos/indutny/bn.js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/indutny/bn.js/statuses/{sha}","languages_url":"https://api.github.com/repos/indutny/bn.js/languages","stargazers_url":"https://api.github.com/repos/indutny/bn.js/stargazers","contributors_url":"https://api.github.com/repos/indutny/bn.js/contributors","subscribers_url":"https://api.github.com/repos/indutny/bn.js/subscribers","subscription_url":"https://api.github.com/repos/indutny/bn.js/subscription","commits_url":"https://api.github.com/repos/indutny/bn.js/commits{/sha}","git_commits_url":"https://api.github.com/repos/indutny/bn.js/git/commits{/sha}","comments_url":"https://api.github.com/repos/indutny/bn.js/comments{/number}","issue_comment_url":"https://api.github.com/repos/indutny/bn.js/issues/comments{/number}","contents_url":"https://api.github.com/repos/indutny/bn.js/contents/{+path}","compare_url":"https://api.github.com/repos/indutny/bn.js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/indutny/bn.js/merges","archive_url":"https://api.github.com/repos/indutny/bn.js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/indutny/bn.js/downloads","issues_url":"https://api.github.com/repos/indutny/bn.js/issues{/number}","pulls_url":"https://api.github.com/repos/indutny/bn.js/pulls{/number}","milestones_url":"https://api.github.com/repos/indutny/bn.js/milestones{/number}","notifications_url":"https://api.github.com/repos/indutny/bn.js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/indutny/bn.js/labels{/name}","releases_url":"https://api.github.com/repos/indutny/bn.js/releases{/id}","created_at":"2014-04-26T12:02:03Z","updated_at":"2015-04-08T00:18:58Z","pushed_at":"2015-04-23T21:08:29Z","git_url":"git://github.com/indutny/bn.js.git","ssh_url":"git@github.com:indutny/bn.js.git","clone_url":"https://github.com/indutny/bn.js.git","svn_url":"https://github.com/indutny/bn.js","homepage":"","size":1565,"stargazers_count":109,"watchers_count":109,"language":"JavaScript","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":16,"mirror_url":null,"open_issues_count":3,"forks":16,"open_issues":3,"watchers":109,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/27"},"html":{"href":"https://github.com/indutny/bn.js/pull/27"},"issue":{"href":"https://api.github.com/repos/indutny/bn.js/issues/27"},"comments":{"href":"https://api.github.com/repos/indutny/bn.js/issues/27/comments"},"review_comments":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/27/comments"},"review_comment":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/indutny/bn.js/pulls/27/commits"},"statuses":{"href":"https://api.github.com/repos/indutny/bn.js/statuses/e243372d044621b6711ea6304ad70b7d2d99e0cc"}}}}