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

Groups > comp.lang.c > #163529 > unrolled thread

ot: on a base being a power of another

Back to article view | Back to comp.lang.c

Contents

  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

#163529 — ot: on a base being a power of another

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.

[toc] | [next] | [standalone]

#163530

Meredith Montgomery <mmontgomery@levado.to> writes:

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

Yes, it really is off-topic!  Since you are thinking about algorithms,
comp.programming is probably the closest fit.  I've set followup-To.
Maybe a good thread there will revive that group.

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

When the two bases are positive integer powers of some common number,
the conversion is simply a matter of grouping digits.  You clearly get
this as you go on to give explicit examples, so I am not sure why you are
asking why it's easy.

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

> Why does this work?  I don't know.

I don't know what sort of answer that question needs.  It seems obvious
to me that groups of k > 1 base b digits are just the digits in base b^k.

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

You probably intended to say more, though this definition is interesting
in it's own right.  For example, using b=10, N=20 can be written with

  a0 = 20
  a0 = 0, a1 = 2
  a0 = -10, a1 = 3

and so on.  Also, your definition permits b to be something other than a
positive integer.  Base e, anyone?  Base -2?

And permitting (as you do by default) the digits to be rational or even
irrational numbers is also interesting!

> Can you solve this problem or point me somewhere?

I'm not sure what the problem is.  You started by saying you can convert
between any two bases, but maybe you meant "one can convert" and you
don't know a general algorithm to do it.  Is that the problem you are
asking about?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#163531

On 20/11/2021 21:08, 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.
> 

The base-3 to base-9 works because every two base-3 digits, '11', have 
value 4, and correspond to one base-9 digit.

It general it's not so simple.

What are you looking for? Try playing with the C routines below:

  strtoval(S, base) => N

        Converts text representing a number in a given base, to a
        64-bit binary value

  valtostr(N, base)

        Converts a binary number N to a text representation in given base

See main() for example.

----------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef uint64_t u64;

char digits[]="0123456789ABCDEF";

int getdigit(int c) {
     if (c>='0' && c<='9') return c-'0';
     if (c>='A' && c<='F') return c-'A'+10;
     if (c>='a' && c<='f') return c-'a'+10;
     return 0;
}

u64 strtoval(char* s, int base) {
     u64 value=0;
     while (*s) {
         value=value*base+getdigit(*s);
         ++s;
     }
     return value;
}

char* valtostr(u64 value, int base) {
     char s[100];
     static char t[100];
     char* p = s;
     char* q = t;

     if (value==0) return "0";

     do {
         *p = digits[value%base];
         ++p;
         value /= base;
     } while (value);

     do {
         *q++=*--p;
     } while (p>s);
     *q=0;

     return t;
}

int main(void) {
     u64 x;

     x=strtoval("1111111111111111",3);

     puts(valtostr(x,3));
     puts(valtostr(x,9));
     puts(valtostr(x,10));
}

[toc] | [prev] | [next] | [standalone]

#163532

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.

[toc] | [prev] | [next] | [standalone]

#163614

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!

[toc] | [prev] | [next] | [standalone]

#163619

On 23/11/2021 18:43, Meredith Montgomery wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:

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

210012 in base 3 is 572 decimal, which is 705 in base 9.

You can do the 210012 to base 10 conversion like this:

       5   4   3   2   1   0      Units column
     243  81  27   9   3   1      3**units column

       2   1   0   0   1   2

Sum 243*2 + 81*1 + 3*1 + 1*2 to get 572.

I still don't know what it is you're trying to do, but a direct 
conversion to base 9 can be done with:

      3      2     1       0        Units column
    729     81     9       1        9**units colun

      -      7     0       5
         2*3+1     -   1*3+2        The 2, 1, 1 ,2 digits from above

[toc] | [prev] | [next] | [standalone]

#163630

On Tuesday, November 23, 2021 at 1:46:14 PM UTC-5, Meredith Montgomery wrote:
...
> Using your example, I get 
> 
> 210012_3 = a[5]*3^5 + a[3]*3^3 + a[1]*3^1 

That should be 210012_3 =
2×3^5+ 1×3^4 + 0×3^3 + 0×3^2 +1*3^+ +2×3^0 =
(2×3 + 1)×3^4 + (0×3 + 0)×3^2 + (1×3 + 2)×3^0 =
21_3 × 3^4 + 00_3 × 3^2 + 12_3 × 3^0 =
7×9^2 + 0×9^1 + 5×9^0 =
705_9

I hope that helps you understand why conversion between a given
base and an integer power of that base is much simpler than other
Kinds of base conversions.

[toc] | [prev] | [next] | [standalone]

#163646

"james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> writes:

> On Tuesday, November 23, 2021 at 1:46:14 PM UTC-5, Meredith Montgomery wrote:
> ...
>> Using your example, I get 
>> 
>> 210012_3 = a[5]*3^5 + a[3]*3^3 + a[1]*3^1 
>
> That should be 210012_3 =
> 2×3^5+ 1×3^4 + 0×3^3 + 0×3^2 +1*3^+ +2×3^0 =
> (2×3 + 1)×3^4 + (0×3 + 0)×3^2 + (1×3 + 2)×3^0 =
> 21_3 × 3^4 + 00_3 × 3^2 + 12_3 × 3^0 =
> 7×9^2 + 0×9^1 + 5×9^0 =
> 705_9
>
> I hope that helps you understand why conversion between a given
> base and an integer power of that base is much simpler than other
> Kinds of base conversions.

Oh, it does.  Funny --- this is what I thought it was from the start,
but I totally got confused with my calculations and never collected the
terms properly like you just did.  That's really what I was looking for
and that explains it clearly.  Thank you so much!

[toc] | [prev] | [next] | [standalone]

#163542

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web