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

Groups > comp.lang.c > #163542

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

Show all headers | View raw

On 11/20/2021 10: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.

I think this last part is not in base ten, it becomes in base ten after 
you calculate the result of the expression and write in base ten.

Back to your question, as Ben said it's not very clear what the question 
is because you appear to give the answer already - I'll try to fill some 
gap in the hope it is what you mean.

Your expression shows that the /position/ of the digits represents the 
exponent of the power of the base term that the digit multiplies - in 
short, the digit at position k multiplies the b^k term in your 
expression above.

When you convert between base b and b^n the digit in position k of the 
base b^n representation becomes the "digit" (more properly the 
multiplier) in position n*k of the base b representation. That's the 
root of the grouping.
In the transition the digit in base b^n (whose value spans from 0 to 
b^n-1) must be converted in the corresponding sequence of digits in base 
b (each of which span from 0 to b-1) and you need up to n digits in base 
b to represent a single digit in base b^n - that's your group.
Since the digits are multiplicative coefficients to the powers b^k [*], 
the conversion of each group does not affect the conversion of other 
groups in the additive series above.

([*] More properly the digits of each group are multipliers for the 
powers (b^n)^k in the base b^n representation, and the powers b^(n*k) in 
the base b representation)

Obviously, none of this works when the two bases do not share this 
relation, e.g. between base 2 and base 3.


   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 — Previous 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