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

Groups > comp.lang.c > #163614

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

Show all headers | View raw

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

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

You really understood my request.  Thank you.  

I'm having some difficulties carrying out the calculations.  

I suppose when n=0 the group is 12, when n=1 the group is 00 and so on.

Using your example, I get 

  210012_3 = a[5]*3^5 + a[3]*3^3 + a[1]*3^1

But I think a[5] is the fifth digit from right to left, starting at
zero, so a[5] = 2, a[3] = 0, a[1] = 1, so I get 

  210012_3 = 2*3^5 + 0*3^3 + 1*3^1
           = 6*3^4 + 0*3^2 + 3
           = 6*9^2 + 0*3^2 + 3
           = 603_9,

unless I got confused with bases there.  I did multiply 2*3 and I wrote
6 as an answer --- I'm guess I'm working in base ten there.

Anyway, wrong or right, this is precisely the sort of explanation I have
been looking for and it looks like you have it.  I'll continue to
investigate this until I get it.  Thank you!

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