Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Base58

en.wikipedia.org

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Base58

#31

Post by eesmith »

lifthrasiir wrote: post #29
eesmith wrote: post #15

Earlier quoted context omitted.

"Base36 and base58 are the only common exceptions" Isn't Ascii85/Base85 at least as common as those? Quoting the Wikipedia entry for it, "Its main modern uses are in Adobe's PostScript and Portable Document Format file formats, as well as in the patch encoding for binary files used by Git" Python includes it as part of the standard library. Using the example from the WP entry: >>> s = r""" Cj@.4Gp$d7F!,L7@ @3BB/F*&OC…

I have explicitly mentioned this: > [...] some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). Base 85 does not use bigint, it is just a clever approximation of optimal encoding with 85 symbols.

I think I was confused between "baseX" as the specific program name and 'base X' as the base of the specific numbering system.

Re: Base58

#33

Post by decentralised »

athenot wrote: post #11
decentralised wrote: post #4

Why base-58 instead of standard base-64 encoding? - Don't want 0OIl characters that look the same in some fonts and could be used to create visually identical looking data. - A string with non-alphanumeric characters is not as easily accepted as input. - E-mail usually won't line-break if there's no punctuation to break at. - Double-clicking selects the whole string as one word if it's all alphanumeric. https://githu…

This is a similar encoding as airline reservation numbers, except it also has lowercase characters. But the requirements are very similar. It's amazing how much confusion is removed by suppressing ambiguities between number 0 vs. letter O and number 1 vs. letter I. For reservation numbers, doing away with case makes it easier to speak the number over the phone.

It's amazing how user experience can be affected from this deep in the stack.

Re: Base58

#34

Post by ur-whale »

ChrisLomont wrote: post #24
ur-whale wrote: post #21

Earlier quoted context omitted.

There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler…

>Many compilers even expand the code inline to generate fix size divides into mult and shift.

This is what I meant when I said:

>even when the compiler gets smart about it because it's a constant.

Re: Base58

#35

Post by ChrisLomont »

ur-whale wrote: post #34
ChrisLomont wrote: post #24

Earlier quoted context omitted.

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler…

>Many compilers even expand the code inline to generate fix size divides into mult and shift. This is what I meant when I said: >even when the compiler gets smart about it because it's a constant.

You also claimed it's dog slow, and earlier you claimed it requires a big num lib. All of these are wrong. Many compiler/architecture combinations can reduce the divmod to one asm instruction, that on some architectures is very quick. If it is slower than shift/mult trick, that compiler can choose to do that.

Go look at some decent implementations and the assembly they generate. Don't spread unfounded or unchecked claims.

Re: Base58

#36

Post by nkurz »

ChrisLomont wrote: post #35
ur-whale wrote: post #34

Earlier quoted context omitted.

>Many compilers even expand the code inline to generate fix size divides into mult and shift. This is what I meant when I said: >even when the compiler gets smart about it because it's a constant.

You also claimed it's dog slow, and earlier you claimed it requires a big num lib. All of these are wrong. Many compiler/architecture combinations can reduce the divmod to one asm instruction, that on some architectures is very quick. If it is slower than shift/mult trick, that compiler can choose to do that. Go look at some decent implementations and the assembly they generate. Don't spread unfounded or unchecked cl…

It's OK for different people have different impressions about the speed of dogs. On x64 for 64-bit registers, built-in assembly DIV is about 10 times slower than MUL, and 10 times faster than a lookup from RAM. Whether this makes it fast or slow depends on what you are trying to do.

I'm interested in your comment that "some architectures" have a fast divmod. Do you actually know of one where it's faster than a shift and a multiplication? Or the same? We're finishing up a paper where this would be very relevant information.

Re: Base58

#37

Post by ChrisLomont »

nkurz wrote: post #36
ChrisLomont wrote: post #35

Earlier quoted context omitted.

You also claimed it's dog slow, and earlier you claimed it requires a big num lib. All of these are wrong. Many compiler/architecture combinations can reduce the divmod to one asm instruction, that on some architectures is very quick. If it is slower than shift/mult trick, that compiler can choose to do that. Go look at some decent implementations and the assembly they generate. Don't spread unfounded or unchecked cl…

It's OK for different people have different impressions about the speed of dogs. On x64 for 64-bit registers, built-in assembly DIV is about 10 times slower than MUL, and 10 times faster than a lookup from RAM. Whether this makes it fast or slow depends on what you are trying to do. I'm interested in your comment that "some architectures" have a fast divmod. Do you actually know of one where it's faster than a shift…

Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add.

I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod, but numbers of many forms do. I’d not be surprised if state of the art has it reduced to a few non-mem access branchless no division instructions on most architectures.

Maybe later I’ll poke at 58 and see what I can design. I’ve made quite a few such algorithms over the years.

[1] https://www.agner.org/optimize/instruction_tables.pdf

Re: Base58

#38

Post by nkurz »

ChrisLomont wrote: post #37
nkurz wrote: post #36

Earlier quoted context omitted.

It's OK for different people have different impressions about the speed of dogs. On x64 for 64-bit registers, built-in assembly DIV is about 10 times slower than MUL, and 10 times faster than a lookup from RAM. Whether this makes it fast or slow depends on what you are trying to do. I'm interested in your comment that "some architectures" have a fast divmod. Do you actually know of one where it's faster than a shift…

Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add. I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod…

I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it).

I'm might be exposing my ignorance, but what's 58 in this context? Is this an ARM Cortex series, or something else?

Re: Base58

#39

Post by a1369209993 »

nkurz wrote: post #38
ChrisLomont wrote: post #37

Earlier quoted context omitted.

Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add. I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod…

I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing…

58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)

Re: Base58

#40

Post by nkurz »

a1369209993 wrote: post #39
nkurz wrote: post #38

Earlier quoted context omitted.

I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing…

58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)

I feel silly, but thank you for the polite explanation of what is now obvious.
Post reply on HN