{"action":"closed","issue":{"url":"https://api.github.com/repos/mmp/pbrt-v2/issues/52","labels_url":"https://api.github.com/repos/mmp/pbrt-v2/issues/52/labels{/name}","comments_url":"https://api.github.com/repos/mmp/pbrt-v2/issues/52/comments","events_url":"https://api.github.com/repos/mmp/pbrt-v2/issues/52/events","html_url":"https://github.com/mmp/pbrt-v2/issues/52","id":127133814,"number":52,"title":"PermutedRadicalInverse() is horribly broken","user":{"login":"mmp","id":102567,"avatar_url":"https://avatars.githubusercontent.com/u/102567?v=3","gravatar_id":"","url":"https://api.github.com/users/mmp","html_url":"https://github.com/mmp","followers_url":"https://api.github.com/users/mmp/followers","following_url":"https://api.github.com/users/mmp/following{/other_user}","gists_url":"https://api.github.com/users/mmp/gists{/gist_id}","starred_url":"https://api.github.com/users/mmp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mmp/subscriptions","organizations_url":"https://api.github.com/users/mmp/orgs","repos_url":"https://api.github.com/users/mmp/repos","events_url":"https://api.github.com/users/mmp/events{/privacy}","received_events_url":"https://api.github.com/users/mmp/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-01-17T23:59:49Z","updated_at":"2016-01-18T00:11:25Z","closed_at":"2016-01-18T00:11:25Z","body":"Per Christensen noted the following. (Text slightly edited.)\r\n\r\nI came across an issue with the PermutedRadicalInverse() function from the 2nd edition.  To explain the issue as simply as possible, assume we’re computing in base 2 and the permutation array p is {1,0} so ones get converted to zeroes and vice versa.  (I know that for the particular case of base 2 there are much more efficient ways of doing digit scrambling using e.g. bit-wise xor, but let’s ignore that for now.)\r\n\r\nHere’s my version of your function — pretty much verbatim straight out of the book:\r\n\r\n```\r\nfloat \r\nPermutedRadicalInverse(unsigned n, const unsigned base, unsigned *perm)\r\n{\r\n    float val = 0.0f;\r\n    float invBase = 1.0f / base, invBi = invBase;\r\n    while (n > 0) {\r\n        unsigned d_i = perm[n%base];\r\n        val += d_i * invBi;\r\n        n *= invBase;\r\n        invBi *= invBase;\r\n    }\r\n    return val;\r\n}\r\n```\r\n\r\nThe results I get for n=0..15 are not what I’d expect:\r\n\r\n```\r\n0 0.000000\r\n1 0.000000\r\n2 0.500000\r\n3 0.000000\r\n4 0.750000\r\n5 0.250000\r\n6 0.500000\r\n7 0.000000\r\n8 0.875000\r\n9 0.375000\r\n10 0.625000\r\n11 0.125000\r\n12 0.750000\r\n13 0.250000\r\n14 0.500000\r\n15 0.000000\r\n```\r\n\r\nThere are several repeats of 0 and 0.5.  It seems to me that the issue is that the loop exits too early — just because n is 0 doesn’t mean we can skip the rest of the digits.  Here is a slightly modified version that loops over all digits to give them a chance to be permuted into non-zero values:\r\n\r\n```\r\nfloat \r\nPermutedRadicalInverseBetter(unsigned n, const unsigned base, unsigned *perm)\r\n{\r\n    float val = 0.0f;\r\n    float invBase = 1.0f / base, invBi = invBase;\r\n    for (unsigned d = 0; d < 32; d++) { // loop over all digits\r\n        unsigned d_i = perm[n%base];\r\n        val += d_i * invBi;\r\n        n *= invBase;\r\n        invBi *= invBase;\r\n    }\r\n    return val;\r\n}\r\n```\r\n\r\nWith this change I get the following values (which seem more reasonable):\r\n\r\n```\r\n0 1.000000\r\n1 0.500000\r\n2 0.750000\r\n3 0.250000\r\n4 0.875000\r\n5 0.375000\r\n6 0.625000\r\n7 0.125000\r\n8 0.937500\r\n9 0.437500\r\n10 0.687500\r\n11 0.187500\r\n12 0.812500\r\n13 0.312500\r\n14 0.562500\r\n15 0.062500\r\n```"}}