03 May 2014

Increment Base64 numbers

In Short-url service, I need to have unique numbers that consist of 4, 5 or 6 digits at most.

If I use the decimal system (base 10), and If I constraint myself with 5 digits, I'll have maximum of 10^5 (= 100000) unique values, but this is less than enough!

So, I need to us some other number system with higher base. What about base 64?

In base 64, we have 64^5 (=1073741824) unique values... ohh this is good.

In the decimal system, I can start with 0 and use the `+` operator to increment this values.. but in base 64 I have to write the `increment` operation myself.

Here's  the method I wrote (in Java8) and the results shows that, the 1,000,000,000 th value is `6lrnA`.

So, after increment billion times, I can have this `6lrnA` value of 5 digits, so It is perfect for such service.

The code:


import java.util.List;
import java.util.stream.Collectors;

public class Base64Incremental {

    static final String allChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    public static void main(String[] args) {
        String s = "A";
        for (int i = 0; i < 1000000000; i++) {
            s = incr(s);

            if (i % 100000000 == 0) {
                System.out.printf("i = %d => s = %s\n", i, s);
            }
        }
        System.out.println(s);
    }

    static String incr(String in) {
        List<Character> chars = in.chars().mapToObj(i -> (char) i).collect(Collectors.toList());
        add(chars, chars.size() - 1);
        return chars.stream().map(c -> String.valueOf(c)).collect(Collectors.joining());
    }

    static void add(List<Character> chars, int i) {
        int index = allChars.indexOf(chars.get(i));

        // if the char value is not highest value in the number system (not 9 as
        // if it was decimal system)
        if (index < allChars.length() - 1) {
            // increment the value by 1
            chars.set(i, allChars.charAt(index + 1));
        } else {
            // else, (the char value is the highest value in the number system,
            // then should place the least value in the number system here (0 in
            // decimal system)
            chars.set(i, allChars.charAt(0));
            // then check, if this char is not the highest order char (the most
            // left char), if so perform the same func again on the next char
            if (i != 0) {
                add(chars, i - 1);
            } else {
                // otherwise, just insert a number on the left to be the
                // highest order with the low value
                chars.add(0, allChars.charAt(0));
            }
        }
    }
}

The result:

i = 0 => s = B
i = 100000000 => s = E8dDB
i = 200000000 => s = K57HB
i = 300000000 => s = Q3ZLB
i = 400000000 => s = W03PB
i = 500000000 => s = cyVTB
i = 600000000 => s = ivzXB
i = 700000000 => s = otRbB
i = 800000000 => s = uqvfB
i = 900000000 => s = 0oNjB
6lrnA


That's All!
Post a Comment