How does Base32 (or any Base2^n) work exactly?

Post by sedatk » Mon, Dec 18, 2023, 10:50 PM UTC

sa46 wrote: post #37

sedatk wrote: post #29

Earlier quoted context omitted.

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.

Seems 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

Post by charlieyu1 » Tue, Dec 19, 2023, 4:00 PM UTC

sedatk wrote: post #42

charlieyu1 wrote: post #39

Earlier quoted context omitted.

I 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.

Haven't seen that, but how do you work with carry for numbers that are 256^8 < x < 58^11 ?

Post by ljm » Wed, Dec 20, 2023, 12:07 AM UTC

thaumasiotes wrote: post #36

Am4TIfIsER0ppos wrote: post #31

Earlier quoted context omitted.

You can make the word fuck with it. That upsets children on the internet.

If that's what you're trying to avoid, it will be a lot more effective to remove F.