Print first N numbers in BASE62

Question

I would like to print first N numbers in BASE62 encoding. What's wrong in my code?

const char ALPHABET[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(void) {
    int N = 50;
    for (int i = 0; i < N; i++) {
        int base62 = ALPHABET[i % 62];
        printf("Base 62: %s\n", (char*)base62);
    }
}

`base62` is an `int`. You can't just cast it into a `char*` and expect `%s` to print a string! — Spikatrix, Apr 07 '15 at 13:53
I'm not familiar with Base62 encoding and stuff... What's the output you want? — Spikatrix, Apr 07 '15 at 13:56
Generally, I'm looking for fast and simple method to generate all words combinations from alphabet. I thought that base62 is good way to do it.... — Bakus123, Apr 07 '15 at 14:00

Peter G. · Answer 1 · 2015-04-07T14:08:37.570

2

ALPHABET is an array of chars, so you should be fine with using char base 62 ... and printf("Base 62: %c\n", base62);

Casting a normal int to pointer and passing that to printf as in the original code will lead to printf making invalid memory reads (undefined behavior).

edited Apr 07 '15 at 14:08

answered Apr 07 '15 at 14:02

Peter G.

14,786
7
57
75

Not exactly, for example 100 in base10 = 1c in base62. 1c is not a single character... – Bakus123 Apr 07 '15 at 14:07
Do you have any idea what can i do? – Bakus123 Apr 07 '15 at 14:24

score 1 · Accepted Answer · answered Apr 07 '15 at 14:38

You need to print out string representing the number in base62. For N >= 62, you will have a multi-character string. First, you would need to count the number of digits in the base62 representation and then display character-by-character.

For that, you need to something like this-

// Count the number of characters the number will need
int num_digits(int num) {
   int count=0;
   while(num > 0) {
      num /= 62;
      count++;
   }
   if(count == 0)
      count = 1;
   return count;
}

int main() {
   const char ALPHABET[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
   int i, N=100;
   char STR[10];

   for (i = 0; i < N; i++) {
      int num = i;
      int digits = num_digits(num);
      STR[digits] = '\0';

      while(num > 0) {
         char base62 = ALPHABET[num % 62];
         STR[--digits] = base62;
         num /= 62;
      }

      if(i == 0)
         STR[--digits] = ALPHABET[0];
      printf("%s\n", i, STR);
   }
}

Note: `if(count == 0) ...` and `if(i == 0) ...` can eliminated by using a `do` loop. e.g. `do { num /= 62; count++; } while (num > 0);`. } — chux - Reinstate Monica, Apr 07 '15 at 16:40

score 1 · Answer 3 · edited May 23 '17 at 12:28

1

After accept simplification

As Cool Guy commented, printf("Base 62: %s\n", (char*)base62);, will not convert an int into the desired array of characters. Below code breaks down the value, one base-62 character at a time.

void print_base(unsigned n, unsigned base) {
  static const char ALPHABET[] =
      "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  if (n >= base) {
    print_base(n / base, base);
  }
  fputc(ALPHABET[n % base], stdout);
}

#include <stdio.h>
int main(void) {
  print_base(100, 10); // 100
  puts("");
  print_base(100, 16); // 64
  puts("");
  print_base(100, 62); // 1C
  puts("");
  return 0;
}

edited May 23 '17 at 12:28

Community

1
1

answered Apr 07 '15 at 17:21

chux - Reinstate Monica

143,097
13
135
256

Thanks a lot, very good idea. But is possible to do it without recursion? I will be generated very long numbers on GPU and I can't use recursion (It is possible but only with newest graphics card). – Bakus123 Apr 07 '15 at 17:38
1

@sray offers a non recursive method. Whatever I would post would simply be a variation of that. BTW: be careful with negative numbers. – chux - Reinstate Monica Apr 07 '15 at 17:59
Yes I know that @sray answer is good. But I'm wondering whether it would be possible to write a little more efficiently(for example without nested loops)? I will be use it to brute force method and efficiently is very important for me. – Bakus123 Apr 07 '15 at 18:45
2

@Bakus123 There is just a single loop of processing for each number. Whether done iteratively or recursively, it's still the same cycle. In my code, the outer loop is for printing all N numbers. – sray Apr 07 '15 at 18:50
1

@Bakus123 I see no _nested_ loop to print out `N` in sray answer or your post. "efficiently" is vague. Efficiently in speed, code space, complexity or what? – chux - Reinstate Monica Apr 07 '15 at 18:50
You are right, in fact second loop is only for print. Efficiently == speed. I will be generate on my GPU threads, parts of numbers which next will be hashed and compare with input MD5 hash. – Bakus123 Apr 07 '15 at 19:01
If you can use `base 64` or `32` things will likely be much faster. – chux - Reinstate Monica Apr 07 '15 at 19:06

Print first N numbers in BASE62

3 Answers3