Thread: how compute base 4?

  1. #1
    Registered User
    Join Date
    Sep 2014
    Posts
    235

    how compute base 4?

    How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t

    x = a3.43 + a2.42 + a1.41 + a0.40 = a3.64 + a2.16 + a1.4 + a0
    Last edited by barracuda; 03-13-2015 at 02:52 PM.

  2. #2
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by barracuda View Post
    How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t

    x = a3.43 + a2.42 + a1.41 + a0.40 = a3.64 + a2.16 + a1.4 + a0
    The most convenient way is to convert the number to binary first.

    for instance :

    Code:
    75 = 01001011
    You wish to convert to base 4 which means that each two bits(in the binary form) represent a single digit in your base 4 representation.

    Code:
    01  00  10  11   //binary 
    
      1   0    2    3   //base 4

  3. #3
    Citizen of Awesometown the_jackass's Avatar
    Join Date
    Oct 2014
    Location
    Awesometown
    Posts
    269
    If both the original number and the result fit into uint32_t then it's quite simple.

    You just repeatedly modulo and divide by 4, until the original number becomes zero. This will get you the digits in reverse order. You only have to reverse the digits after this.

    Code:
    75%4 = 3 (a0)
    75/4=18
    18%4 = 2 (a1)
    18/4=4
    4%2 =  0 (a2)
    4/4=1
    1%4 =  1 (a3)
    "Highbrow philosophical truth: Everybody is an ape in monkeytown" --Oscar Wilde

  4. #4
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by Aslaville View Post
    The most convenient way is to convert the number to binary first.
    No, I disagree. The most convenient way, in my opinion, is to do it right-to-left.

    The rightmost digit of value, in any base, is value modulo base.

    In C99, the result of the modulo operation, value % base, has the same sign as value, so you must first make sure value is nonnegative. If the original value was negative, just prepend a negative sign to the result string (as the final operation).

    Converted to a string, you need a char buffer of at least (size_t)ceil(2.0 + log((double)base)/log(2.0) * CHAR_BIT * (double)sizeof value) chars, including the string-terminating nul char. If the caller supplies the buffer, and the conversion ends up using fewer chars, you can use memmove() to move the string to the origin of the buffer. I normally don't, I just document that my integer-to-string conversion function returns a valid pointer within the specified buffer, not necessarily to the beginning of the buffer.

    (For base 10, I approximate that using 3+39*CHAR_BIT*sizeof value/128. For base 4, I'd use 3+CHAR_BIT*sizeof value/2. These are compile-time constant expressions, and therefore valid to use as the size of a char buffer. These work for bignum libraries, too.)

  5. #5
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by Nominal Animal View Post
    No, I disagree. The most convenient way, in my opinion, is to do it right-to-left.
    I would half-heartedly agree that implementing code for the modulo is much easier.

  6. #6
    Registered User
    Join Date
    Sep 2014
    Posts
    235
    @Aslaville

    Wow, that's awesome! I thought about something like:

    Code:
    char rchar[5];
    int remainder, number, x, c; 
    remainder = number= 75;
    c=-1;
    if ( remainder >= 64 ){
        x = (int) (number/64);
        remainder = number-x;
    }
    else x=0;
    
    c++;
    rchar[c]= ... (x) ...; // digit to char
    
    if ( remainder >= 16 ){
        x = (int) (number/16);
        remainder = number-x;
    }
    else x=0;
    
    c++;
    rchar[c]= ... (x) ...; // digit to char
    
    if ( remainder >= 4 ){
        x = (int) (number/4);
        remainder = number-x;
    }
    else x=0;
    
    c++;
    rchar[c]= ... (x) ...; // digit to char
    
    c++;
    rchar[c]= ... (remainder) ...; // digit to char
    Not tested.
    I don't know how convert digit do char.
    Still division is there (slower). Your calculation should be much simpler.
    How do you convert binary '01' to char '1'?
    Last edited by barracuda; 03-14-2015 at 03:35 AM.

  7. #7
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Add the character '0'

  8. #8
    Registered User
    Join Date
    Sep 2014
    Posts
    235
    This is best and fastest solution:
    Code:
    uint16_t k,kk,kkk,kkkk;
    unsigned char a,b,c,d;
    k=kk=kkk=kkkk = 75;
    a = k & ~(0b11111100);
    b = (kk & ~(0b11110011)) >> 2 ;
    c = (kkk & ~(0b11001111)) >> 4;
    d = (kkkk & ~(0b00111111)) >> 6;
    I doubt you could find fastest solution. No division, no modulo, no loops. It just does what I need, to get 4 digits in base 4 from number 75.


    Edit: This one is faster - 0.044624s !!!

    Code:
    m=4000x4000;
    for (;n<m;n++){
       k = 75;
       a = k & 0b11;
       b = (k & 0b1100) >> 2 ;
       c = (k & 0b110000) >> 4;
       d = (k & 0b11000000) >> 6;
    }
    Last edited by barracuda; 03-14-2015 at 01:58 PM.

  9. #9
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by barracuda View Post
    This is best and fastest solution:
    Code:
    uint16_t k,kk,kkk,kkkk;
    unsigned char a,b,c,d;
    k=kk=kkk=kkkk = 75;
    a = k & ~(0b11111100);
    b = (kk & ~(0b11110011)) >> 2 ;
    c = (kkk & ~(0b11001111)) >> 4;
    d = (kkkk & ~(0b00111111)) >> 6;
    I doubt you could find fastest solution. No division, no modulo, no loops. It just does what I need, to get 4 digits in base 4 from number 75.


    Edit: This one is faster - 0.044624s !!!

    Code:
    m=4000x4000;
    for (;n<m;n++){
       k = 75;
       a = k & 0b11;
       b = (k & 0b1100) >> 2 ;
       c = (k & 0b110000) >> 4;
       d = (k & 0b11000000) >> 6;
    }
    Indeed, you nailed it. Basically if you want the second digit in your base 4 number, save the 3-rd and 4-th bits in the original number

  10. #10
    Registered User talahin's Avatar
    Join Date
    Feb 2015
    Posts
    51
    Make sure you use the -O compiler flag and it will even be faster because the compiler will optimize everything.

    the result of the optimization:
    Code:
        .file    "b4.c"
        .section    .rodata.str1.1,"aMS",@progbits,1
    .LC0:
        .string    "%d = %c %c %c %c base 4"
        .text
        .globl    main
        .type    main, @function
    main:
    .LFB11:
        .cfi_startproc
        movl    $16000000, %eax
    .L2:
        subl    $1, %eax
        jne    .L2
        pushl    %ebp
        .cfi_def_cfa_offset 8
        .cfi_offset 5, -8
        movl    %esp, %ebp
        .cfi_def_cfa_register 5
        andl    $-16, %esp
        subl    $32, %esp
        movl    $51, 20(%esp)
        movl    $50, 16(%esp)
        movl    $48, 12(%esp)
        movl    $49, 8(%esp)
        movl    $75, 4(%esp)
        movl    $.LC0, (%esp)
        call    printf
        movl    $0, %eax
        leave
        .cfi_restore 5
        .cfi_def_cfa 4, 4
        ret
        .cfi_endproc
    .LFE11:
        .size    main, .-main
        .ident    "GCC: (Debian 4.7.2-5) 4.7.2"
        .section    .note.GNU-stack,"",@progbits

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about base 10 to base N convertor lab program
    By ethankins in forum C++ Programming
    Replies: 4
    Last Post: 12-01-2010, 10:42 AM
  2. Calling base class function when base is a template
    By VirtualAce in forum C++ Programming
    Replies: 9
    Last Post: 07-11-2010, 02:26 AM
  3. Replies: 5
    Last Post: 07-25-2008, 04:37 AM
  4. Replies: 9
    Last Post: 10-07-2006, 05:37 AM
  5. How to change number data from base 256 to base 16?
    By ooosawaddee3 in forum C++ Programming
    Replies: 2
    Last Post: 11-05-2002, 12:19 AM