4 ms·

why is base62 quadratic?

dfox 15y ago
Naive implementation certainly is, as it involves one multiplication (of number whose size depends linearly depends on number of previously processed bytes) for each input byte and one division for each output byte. But on the other hand I have this feeling, that more effective implementation is possible (and actually used by modern compression algorithms like RAR and LZMA).
- andrewcooke 15y ago
  but couldn't you have a stream algorithm with modular arithmetic? [edit: i thought i had a good demonstration of this. actually, two. but both were wrong. so it does seem to be non-trivial...] [edit 2: open stack overflow question: http://stackoverflow.com/questions/3545931/efficient-algorithm-for-conversion-between-numeral-system http://stackoverflow.com/questions/3545931/efficient-algorit... ]
  - DenisM 15y ago
    If we could, we wouldn't call it base62, as base62 normally means converting the entire "bigint" (all bytes of input data as one big number) into base-62 representation. At least that's how baseXX has been used to far (I searched the web before doing this), and I am in favor of sticking to that naming convention. Agreed? Now, whether we could come up with such streaming algorithm I'm not sure. I tried solving this problem, and this is what I came up with. Maybe I haven't tried hard enough to go the other route... I guess you could simply slice the incoming stream into a set of chunks, each small enough to make bigin base62 conversion fast (which is square of the size of the chunk), and yet large enough to obscure the occasional loss of space at the chunk boundaries... I guess that would be an option...
    - deleted 15y ago
      [deleted]
    - deleted 15y ago
      [deleted]
- DenisM 15y ago
  I'm pretty sure it's impossible to do in anything less than square time, but I don't have the prof with me.
  - 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 ago
      i 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.
- deleted 15y ago
  [deleted]

dfox 15y ago

Naive implementation certainly is, as it involves one multiplication (of number whose size depends linearly depends on number of previously processed bytes) for each input byte and one division for each output byte. But on the other hand I have this feeling, that more effective implementation is possible (and actually used by modern compression algorithms like RAR and LZMA).

andrewcooke 15y ago
but couldn't you have a stream algorithm with modular arithmetic? [edit: i thought i had a good demonstration of this. actually, two. but both were wrong. so it does seem to be non-trivial...] [edit 2: open stack overflow question: http://stackoverflow.com/questions/3545931/efficient-algorithm-for-conversion-between-numeral-system http://stackoverflow.com/questions/3545931/efficient-algorit... ]
- DenisM 15y ago
  If we could, we wouldn't call it base62, as base62 normally means converting the entire "bigint" (all bytes of input data as one big number) into base-62 representation. At least that's how baseXX has been used to far (I searched the web before doing this), and I am in favor of sticking to that naming convention. Agreed? Now, whether we could come up with such streaming algorithm I'm not sure. I tried solving this problem, and this is what I came up with. Maybe I haven't tried hard enough to go the other route... I guess you could simply slice the incoming stream into a set of chunks, each small enough to make bigin base62 conversion fast (which is square of the size of the chunk), and yet large enough to obscure the occasional loss of space at the chunk boundaries... I guess that would be an option...
  - deleted 15y ago
    [deleted]
  - deleted 15y ago
    [deleted]
DenisM 15y ago
I'm pretty sure it's impossible to do in anything less than square time, but I don't have the prof with me.
- 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 ago
    i 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.
deleted 15y ago
[deleted]