3 ms·
Unlike Base64 or Base32, Base58 has approximately O(N^2) complexity because it requires iterative division and multiplication operations on big integers. You ca
by sedatk 3y ago
Unlike Base64 or Base32, Base58 has approximately O(N^2) complexity because it requires iterative division and multiplication operations on big integers. You can't encode a gigabyte of data with Base58 in a reasonable time, but you certainly can with Base64 or Base32.
- sa46 3y agoSeems like a compiler should be able to convert division to shifts and subtractions. > u8 divmod 58 can be reduced to a u8->u16 multiply, a right shift, and three conditional subtractions; that's not great, but on a modern CPU it's a afterthought compared to the quadratic loop over the input size. Same topic from 2018: https://news.ycombinator.com/item?id=18409344 https://news.ycombinator.com/item?id=18409344
- sedatk 3y agoI don't understand that comment. How do you handle carry?
- charlieyu1 3y agoI thought base58 runs on 8 byte blocks because 58^11 is slightly larger than 256^8. Then I checked the spec and this is actually not a standard requirement.
- sedatk 3y agoHaven't seen that, but how do you work with carry for numbers that are 256^8 < x < 58^11 ?
- charlieyu1 3y agoIf we cut off at 8 byte blocks every number would be < 256^8. Encountering x > 256^8 would simplify be invalid.
- sedatk 3y agoIn that case, there would be padding left in every encoded block. The size overhead would weaken the case for Base58 especially if you consider using it for arbitrarily long data.