Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #163529

ot: on a base being a power of another

Show all headers | View raw

This is totally not C related, but I think you guys master the subject,
so perhaps it isn't so off-topic.

It's of course very useful to know how to convert numerals from one base
to another when we deal with C programming.  I can convert from any base
to any base.  What I'm trying to understand now is why it is so easy to
go from, say, base two to base eight or base sixteen or, say, base three
to base nine.

To go from base two to base sixteen, you take four digits in base two
and map them to base sixteen --- from right to left.  (We can, say,
left-pad the last group of digits if they don't have four digits.)  I
notice that 2^4 = 16 and it is the exponent here that dictates how many
digits I grab each time --- from right to left.

So if I need to convert base nine to base three, I'll take each digit
(from right to left) and replace it with its corresponding base three
digits, making to sure to always write them as two digits because 
3^2 = 9.

For clarity, let me show an example.  Suppose I want to convert 111111
from base three to base nine.  (There are three groups of 11 in
there.)  Here's a conversion table.

--8<---------------cut here---------------start------------->8---
| base 3 | base 9 |
|--------+--------|
|      0 |      0 |
|      1 |      1 |
|      2 |      2 |
|     10 |      3 |
|     11 |      4 |
|     12 |      5 |
|     20 |      6 |
|     21 |      7 |
|     22 |      8 |
|    100 |     10 |

Table 1.  A correspondence between base three and base nine.
--8<---------------cut here---------------end--------------->8---

I take the first two digits from the right and find its matching in
base nine --- 11 in base three goes to 4 in base nine.  So the last
digit must be 4.  Repeating the same for the other two couples, we get

  111111_3 = 444_9.

Why does this work?  I don't know.  Here's what I see.  First, the
number of distinct numbers that we can write in any base grows
exponentially relative to the number of digits.  Also, if a base is a
power of another --- as nine is of three --- then the increase in the
number of digits matches between the two: we can see in Table 1 that
10_9 happens to be land along 100_3.  That's no coincidence, although
I don't have very good words to describe this at the moment.

Let me share, too, what I consider to be my definition of what it
means to write a number in a certain base.

--8<---------------cut here---------------start------------->8---
Definition.  To express a number N in a certain base b, we need to
find the coefficients a0, a1, ..., ak such that

  N = ak b^k + a(k-1) b^(k-1) + ... + a0 b^0.
--8<---------------cut here---------------end--------------->8---

For example, if we have 123_3, then we really have

  1*3^2 + 2*3^1 + 3*3^0

in base ten.  From an expansion such as this one, I'm trying to show
that it's pretty easy to write it in base nine --- showing that this
works because it would be easy to get powers of nine since we have
powers of three.  But I have not succeeded so far.

So I think the problem I'm giving myself is to take an expansion like
that in a certain base b and rewrite it using a new base b^m --- that
is b^m is a power of b.  But I haven't found much clarity so far.

Can you solve this problem or point me somewhere?  I actually don't
know any good book that deals this much with bases.  The math books I
have are either too advanced or too basic.  Thank you so much.

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

ot: on a base being a power of another Meredith Montgomery <mmontgomery@levado.to> - 2021-11-20 18:08 -0300
  Re: ot: on a base being a power of another Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-11-20 22:22 +0000
  Re: ot: on a base being a power of another Bart <bc@freeuk.com> - 2021-11-20 22:27 +0000
  Re: ot: on a base being a power of another James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-11-20 18:08 -0500
    Re: ot: on a base being a power of another Meredith Montgomery <mmontgomery@levado.to> - 2021-11-23 15:43 -0300
      Re: ot: on a base being a power of another Bart <bc@freeuk.com> - 2021-11-23 19:57 +0000
      Re: ot: on a base being a power of another "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2021-11-23 16:53 -0800
        Re: ot: on a base being a power of another Meredith Montgomery <mmontgomery@levado.to> - 2021-11-24 11:14 -0300
  Re: ot: on a base being a power of another Manfred <noname@add.invalid> - 2021-11-21 05:41 +0100

csiph-web