My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O. I still might be confused, but AFAICT,

My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O. I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.