5 ms·

The beauty of mixed-radix bases

104 points by bkudria 10y ago

krallja 10y ago
I'm very impressed by the comparison between 0-indexing and radixes.
- averagewall 10y ago
  Calculating these multidimensional indexes seems to be the major or even the only reason I've ever come across for having 0-based arrays. But it's a pretty big reason.
  - eru 10y ago
    Hmm, I don't know directly about arrays. But for indexing into a linked list 0-based just seems to make the mest sense---if you interpret the index as "how many pointer do I have to chase?". And giving arrays the same treatment then seems reasonable for consistency? I always saw 0-based indices as offsets. Ie like their C interpretation, where a[i] is defined to be the same as * (a+i), not the less natural *(a+i+1). But I can see some points for 1 based indexing, too. (Anecdote from university: the math faculty had a building that started numbering the ground floor as -1. Perhaps just to one up (or is that one down?) the computer scientists who always feel smug about counting from 0.)
    - FireFly 10y ago
      That anecdote reminds me of the classic solution to the zero-versus-one-indexing fights in the Lua community: clearly the solution is to compromise! :) http://lua-users.org/lists/lua-l/2006-05/msg00281.html http://lua-users.org/lists/lua-l/2006-05/msg00281.html
  - Double_Cast 10y ago
    "multidimensional indexes" sounds like something obscure and rarely used. But plain-old Decimals are a special case of this, and people use Decimals every day.
- renox 10y ago
  Even in the real world starting at 0 makes is more logical: in France the ground floor is 0 which works well with underground floors but in the US it's a bit weird to go from 1 to -1 directly.
  - wickawic 10y ago
    It also means you don't have to do math to figure out how many flights of stairs you will be climbing!
spc476 10y ago
Another application I see is instruction encoding. On the MIPS, for instance, a 32-bit instruction is broken down into 6, 5, 5, 5, 5 and 6 bits (or 64 32 32 32 32 64 per the article); the Motorola 68000 had a breakdown of 4, 3, 3, 3 and 3 bits (16 8 8 8 8).
- wallacoloo 10y ago
  This seems a bit dubious to me. I don't think a variable symbol width equates to mixed radix. Nobody calls UTF-8 mixed radix even though some symbols require 8 bits and others 16. You aren't treating these values as algebraic numbers. While you can perform some types of arithmetic on (x, y) vectors in a mixed-radix form (addition, scaling, etc) and same for HH:MM:SS, it makes no sense to add the binary/mixed radix representation of two MIPS instructions. But maybe the definition isn't this picky. They certainly feel like different concepts to me though.
  - transfire 10y ago
    Ah I see. I was confused b/c the end result looked like another matrix, but it was actually two results of mixed radius. Thanks.
kybernetikos 10y ago
I've found factoradic very useful for counting and enumerating permutations. https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system
transfire 10y ago
I didn't understand the final example. What was the point? What was the result showing?
- FireFly 10y ago
  The REPL transcript at the end shows the `Idot` verb in action, by applying it to an array of shape `2 3 4` (that is, imagine two "layers" of matrices, each containing 3 rows, each row being a vector of 4 elements). The `I.` operation finds the indices of 1's in a vector, but the `Idot` shows the indices of 1's in a higher-rank matrix (in this case rank 3, i.e. a three-dimensional array). Compare the locations of the 1's in `array` (the output with 0's and 1's) with the final output (`0 1 1` is the index of the first 1, `1 1 2` is the index of the second 1). Does that help? I mainly wanted to show how the base conversion <=> array index relationship could be used in practice.

104 points by bkudria 10y ago

krallja 10y ago

I'm very impressed by the comparison between 0-indexing and radixes.

averagewall 10y ago
Calculating these multidimensional indexes seems to be the major or even the only reason I've ever come across for having 0-based arrays. But it's a pretty big reason.
- eru 10y ago
  Hmm, I don't know directly about arrays. But for indexing into a linked list 0-based just seems to make the mest sense---if you interpret the index as "how many pointer do I have to chase?". And giving arrays the same treatment then seems reasonable for consistency? I always saw 0-based indices as offsets. Ie like their C interpretation, where a[i] is defined to be the same as * (a+i), not the less natural *(a+i+1). But I can see some points for 1 based indexing, too. (Anecdote from university: the math faculty had a building that started numbering the ground floor as -1. Perhaps just to one up (or is that one down?) the computer scientists who always feel smug about counting from 0.)
  - FireFly 10y ago
    That anecdote reminds me of the classic solution to the zero-versus-one-indexing fights in the Lua community: clearly the solution is to compromise! :) http://lua-users.org/lists/lua-l/2006-05/msg00281.html http://lua-users.org/lists/lua-l/2006-05/msg00281.html
- Double_Cast 10y ago
  "multidimensional indexes" sounds like something obscure and rarely used. But plain-old Decimals are a special case of this, and people use Decimals every day.
renox 10y ago
Even in the real world starting at 0 makes is more logical: in France the ground floor is 0 which works well with underground floors but in the US it's a bit weird to go from 1 to -1 directly.
- wickawic 10y ago
  It also means you don't have to do math to figure out how many flights of stairs you will be climbing!

spc476 10y ago

Another application I see is instruction encoding. On the MIPS, for instance, a 32-bit instruction is broken down into 6, 5, 5, 5, 5 and 6 bits (or 64 32 32 32 32 64 per the article); the Motorola 68000 had a breakdown of 4, 3, 3, 3 and 3 bits (16 8 8 8 8).

wallacoloo 10y ago
This seems a bit dubious to me. I don't think a variable symbol width equates to mixed radix. Nobody calls UTF-8 mixed radix even though some symbols require 8 bits and others 16. You aren't treating these values as algebraic numbers. While you can perform some types of arithmetic on (x, y) vectors in a mixed-radix form (addition, scaling, etc) and same for HH:MM:SS, it makes no sense to add the binary/mixed radix representation of two MIPS instructions. But maybe the definition isn't this picky. They certainly feel like different concepts to me though.
- transfire 10y ago
  Ah I see. I was confused b/c the end result looked like another matrix, but it was actually two results of mixed radius. Thanks.

kybernetikos 10y ago

I've found factoradic very useful for counting and enumerating permutations. https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system

transfire 10y ago

I didn't understand the final example. What was the point? What was the result showing?

FireFly 10y ago
The REPL transcript at the end shows the `Idot` verb in action, by applying it to an array of shape `2 3 4` (that is, imagine two "layers" of matrices, each containing 3 rows, each row being a vector of 4 elements). The `I.` operation finds the indices of 1's in a vector, but the `Idot` shows the indices of 1's in a higher-rank matrix (in this case rank 3, i.e. a three-dimensional array). Compare the locations of the 1's in `array` (the output with 0's and 1's) with the final output (`0 1 1` is the index of the first 1, `1 1 2` is the index of the second 1). Does that help? I mainly wanted to show how the base conversion <=> array index relationship could be used in practice.