The beauty of mixed-radix bases | Hacker News Reader

The beauty of mixed-radix bases

firefly.nu

104 pointsbkudria13 comments

I've found factoradic very useful for counting and enumerating permutations.

https://en.wikipedia.org/wiki/Factorial_number_system

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

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.

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.

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

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.

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

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

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

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.

It also means you don't have to do math to figure out how many flights of stairs you will be climbing!

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

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.

Reply on news.ycombinator.com