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

Groups > comp.lang.c > #163532

Re: ot: on a base being a power of another

Show all headers | View raw

On 11/20/21 4:08 PM, Meredith Montgomery wrote:
> 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.

Consider two bases, b and b^k, where k is an integer. Let a[i] be the
digits making up the representation of a number in base b. Break those
digits into groups of k digits. Let's look at the nth such group. The
value represented by that group is:

N = a[k*n + k - 1]*b^(k*n+k-1) + ... + a[k*n+1]*b^(k*n+1) + a[2k]*b^(k*n)

= (b^k)*n(a[k*n+k-1]*b^(k-1) + ... + a[k*n+1]*b + a[k*n])

But (b^k)^n is the value of the nth digit of a base b^k representation
of a number. This means that the nth digit of the base b^k
representation of this number must have the value:

a[n*k+k-1]*b^(k-1) + ... + a[n*k+1]*b + a[n*k]

But that's just the value in base b of the number represented by the nth
group of base b digits.

To make that more concrete, consider b=3, k=2, a[k] = {2, 1, 0, 0, 1, 2}
Carry out the calculations shown above for n=0, n=1, and n=2. Hopefully,
that exercise will make it clearer. This shows that 210012 base 3 == 705
base 9, because 7 base 9 == 21 base 3 and 5 base 9 == 12 base 3.

Back to comp.lang.c | Previous | Next — Previous in thread | 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