Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there is a constant time algorithm: append the right number of zeros to the representation of $x$.
Is this the only case where there's such a simple algorithm? If $n$ is not a power of $b$, what is the complexity of this problem? I'm not asking for the running-time of any particular algorithm, I'm asking for theoretical bounds on how fast any algorithm can solve the problem.
I think it's reasonable to consider reading, erasing and writing digits as taking zero time, and focus on the number of single digit additions/multiplications that need to be perfomed.
More generally, are there known results on the complexity of adding and multiplying in base $b$ (or just base $2$) representations?