I had the same problem and my mistake was treating n as always a power of 2, thus doing some extra work in the last step. Revise your code for that. Hope this helps.