3 ms·
> Base conversion with arbitrary (and even mixed) base can be done in entirely linear time. Are you saying Bitcoin uses an O(N^2) implementation because they a
by sedatk 6y ago
> Base conversion with arbitrary (and even mixed) base can be done in entirely linear time.
Are you saying Bitcoin uses an O(N^2) implementation because they are naive?
You need to propagate carry to the rest of the digits. I wonder how it’s possible for Base58 to be implemented in linear time. Do you have any sources I can read?
- nullc 6y agoBitcoin doesn't use base-58 in any performance relevant way, it's only used for user interfacy sort of stuff. Probably the most straight forward way to make fast base conversion is the way that most range coders in compression (which are effectively just fancy mixed-radix base converters) do it-- first store temporary digits of a larger size so that the there won't be any inter-digit carries, then make a second pass through to propagate the carries and generate the output. IIRC the approach in bitcoin core is related-- but it processes the carries eagerly rather than deferring them (which makes it asymptotically quadratic (the worst case), but the average case is fast).