{"action":"created","issue":{"url":"https://api.github.com/repos/torch/torch7/issues/434","labels_url":"https://api.github.com/repos/torch/torch7/issues/434/labels{/name}","comments_url":"https://api.github.com/repos/torch/torch7/issues/434/comments","events_url":"https://api.github.com/repos/torch/torch7/issues/434/events","html_url":"https://github.com/torch/torch7/pull/434","id":113563643,"number":434,"title":"Use proper precision for accumulators in multinomial","user":{"login":"albanD","id":6359743,"avatar_url":"https://avatars.githubusercontent.com/u/6359743?v=3","gravatar_id":"","url":"https://api.github.com/users/albanD","html_url":"https://github.com/albanD","followers_url":"https://api.github.com/users/albanD/followers","following_url":"https://api.github.com/users/albanD/following{/other_user}","gists_url":"https://api.github.com/users/albanD/gists{/gist_id}","starred_url":"https://api.github.com/users/albanD/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/albanD/subscriptions","organizations_url":"https://api.github.com/users/albanD/orgs","repos_url":"https://api.github.com/users/albanD/repos","events_url":"https://api.github.com/users/albanD/events{/privacy}","received_events_url":"https://api.github.com/users/albanD/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-10-27T11:37:07Z","updated_at":"2015-11-10T17:31:48Z","closed_at":"2015-10-27T16:59:19Z","pull_request":{"url":"https://api.github.com/repos/torch/torch7/pulls/434","html_url":"https://github.com/torch/torch7/pull/434","diff_url":"https://github.com/torch/torch7/pull/434.diff","patch_url":"https://github.com/torch/torch7/pull/434.patch"},"body":"This fixes #418 by setting the accumulators to the proper type as suggested by @andresy \r\n\r\nThe following code is now working as expected with `FloatTensor`s\r\n\r\n```lua\r\ndo\r\np = torch.FloatTensor(100000):fill(1)\r\np:narrow(1, 50000 + 1, 50000):fill(1e-3)\r\np:div(p:sum())\r\nN = 1001000\r\n\r\nn = 0\r\nc = torch.LongTensor(p:nElement()):zero()\r\nc_ptr = c:data() - 1\r\ntmp = torch.LongTensor()\r\nfor i = 1, 100 do\r\np.multinomial(tmp, p, N, true);\r\nn = n + N\r\ntmp:apply(function(i) c_ptr[i] = c_ptr[i] + 1 end)\r\nend\r\n\r\nactual = c:narrow(1, 50001, 50000):sum()\r\nexpected = n*p:narrow(1, 50001, 50000):sum()\r\nprint(actual, expected)\r\nend\r\n```"},"comment":{"url":"https://api.github.com/repos/torch/torch7/issues/comments/155500453","html_url":"https://github.com/torch/torch7/pull/434#issuecomment-155500453","issue_url":"https://api.github.com/repos/torch/torch7/issues/434","id":155500453,"user":{"login":"nkoumchatzky","id":6900572,"avatar_url":"https://avatars.githubusercontent.com/u/6900572?v=3","gravatar_id":"","url":"https://api.github.com/users/nkoumchatzky","html_url":"https://github.com/nkoumchatzky","followers_url":"https://api.github.com/users/nkoumchatzky/followers","following_url":"https://api.github.com/users/nkoumchatzky/following{/other_user}","gists_url":"https://api.github.com/users/nkoumchatzky/gists{/gist_id}","starred_url":"https://api.github.com/users/nkoumchatzky/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nkoumchatzky/subscriptions","organizations_url":"https://api.github.com/users/nkoumchatzky/orgs","repos_url":"https://api.github.com/users/nkoumchatzky/repos","events_url":"https://api.github.com/users/nkoumchatzky/events{/privacy}","received_events_url":"https://api.github.com/users/nkoumchatzky/received_events","type":"User","site_admin":false},"created_at":"2015-11-10T17:31:48Z","updated_at":"2015-11-10T17:31:48Z","body":"Hey gents! I believe that patch is buggy.\r\nIf the sum of probs is a double but the cumulative distribution array is a float array, then you can end up with the last element of the cumulative distribution being < 1 after dividing each of these elements by the sum (double to float conversion followed by float by double division). Here's a simple C main that simulates why this patch can break torch.multinomial in some cases:\r\n```C\r\n#include <stdio.h>\r\n\r\nint main()\r\n{\r\n    printf(\"TEST MULTINOMIAL\\n\");\r\n    double maxUniform32 = 4294967295L * (1.0/4294967296.0);\r\n    // Take a number bigger than the largest float32 consecutive integer and\r\n    // assume it's the multinomial accreal sum of unnormalized probabilities.\r\n    double sum = 50777218; \r\n    // Cast it to float as is the case when copying sum to the last value cum_dist (last value of the Tensor)\r\n    float fsample = 50777218; \r\n    // Print rounded float (the new last element) -- should be 50777216.000000000000000\r\n    printf(\"fsample: %15.15f\\n\",fsample);\r\n    // Divide rounded float by exact sum\r\n    fsample /= sum;\r\n    printf(\"accreal sum of probs: %15.15f\\n\",sum);\r\n    printf(\"Last element of the cumulative distribution array: %15.15f\\n\",fsample);\r\n    printf(\"Maximum uniform sample in Torch (32 bits): %15.15f\\n\",maxUniform32);\r\n    printf(\"Test if last element of cumulative dist array is lower than a possible uniform sample...\\n\");\r\n    if(maxUniform32 > fsample)\r\n    {\r\n        printf(\"ERROR: The binary search will yield an out of bounds index!!!!!!!!!\");\r\n    }\r\n    return 0;\r\n}\r\n```\r\n\r\nSo either we can change cum_dist to a double tensor, either we can revert it. The former seems to suit everyone!"}}