2-adic integers are awesome

Over at A Neighborhood of Infinity, Dan Piponi has a post about a little bit of magic that happens when you ask gcc to do a division by 7.

This would have nothing to do with visualization aside from the realization I had in the shower, just the other day, that I believe the right way to pick good numbers for an axis scale is to think about the problem in the p-adic sense. “Small”, in this case, means pretty much exactly “close to a round number”. The usual descriptions of the algorithms (at least as I remember them!) for coming up with a good set of axis markings are pretty nasty; maybe p-adic numbers can help.

Advertisements

2 responses to “2-adic integers are awesome

  1. I think the guy is a little in love with his own meandering path through the math, and slightly wrong anyway.

    First, this is not doing a general divide by 7. Its doing a divide by 7 only when you know that the number is a multiple of 7 (which is the case with this pointer arithmetic). If you look at assembly for “int d(int x) { return x/7; }” you’ll see something more involved (which also involves a multiply with a big number, but then arithmetic shift-rights and a subtraction).

    Second, for the specialized find-the-multiple-of-seven, with 32-bit multiplication, you just need an integer S so that 7 * S = N*2^32 + 1; the N*2^32 goes away with wrap-around. The smallest N for which S is an integer is in this case 5, and (5*2^32 + 1)/7 = 3067833783, and unsigned int 3067833783 is the same as two’s-complement int -1227133513.

    Or maybe I’m missing something glorious here; but I’m guessing there are other more direct paths into p-adic numbers, about which I’m honestly still ignorant. I’ll probably include something about this pointer-arithmetic math that in my class next year; the kids will be into it.

    • carlosscheidegger

      Given the rest of the stuff he tends to write about, I would attribute all misunderstanding of this to myself, so “the guy a little in love with his own meandering path through the math, and slightly wrong anyway” would be yours truly, and that’s probably exactly right.

      In any case, I’m more interested in being wrong with respect to p-adic numbers and axis markings, and I still think p-adic numbers are the way to go in that case.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s