3 ms·
A rough sketch of a proof might note that, if the input has n digits, then the output will have roughly n digits (n * log_newbase(oldbase)); and the lowest digi
by waterhouse 15y ago
A rough sketch of a proof might note that, if the input has n digits, then the output will have roughly n digits (n * log_newbase(oldbase)); and the lowest digit of the output depends on all n digits of the input, the next lowest digit depends on maybe the higher n-1 digits of the input, and so on.
Or you could construct the output by computing the effects of the input digits one by one, and in that case, the highest input digit will affect all n(ish) digits of the output, the next highest will affect roughly n-1 digits, etc.
The algorithm could be thoroughly parallelized, but I'm pretty confident that the work done has to be O(n^2).
- andrewcooke 15y agoi just came here to say something similar. one way (perhaps the only way) an efficient streaming approach is possible is if it can be "chunked"; if there's some number of input digits that can be represented as a whole number of output digits. that's possible when going between base 2 and 16, for example, but not when one base has a factor that isn't present in the other.