What's an Efficient Inversion of the Convert-to-Arbitrary-Base C# Function?

Question

I need to convert an integer into a base64-character representation. I'm using OxA3's answer on this thread: Quickest way to convert a base 10 number to any base in .NET?

How do I inverse this to get my original integer back, given a string?

Answer 1

Joel Mueller's answer should guide you the base-64 case.

In response to the preliminary code you've provided in your own answer, you can definitely improve its efficiency by changing the code to accomplish what your for loop is doing (effectively an O(N) IndexOf) to use a hash lookup (which should make it O(1)).

I am basing this on the assumption that baseChars is a field that you initialize in your class's constructor. If this is correct, make the following adjustment:

private Dictionary<char, int> baseChars;

// I don't know what your class is called.
public MultipleBaseNumberFormatter(IEnumerable<char> baseCharacters)
{
    // check for baseCharacters != null and Count > 0

    baseChars = baseCharacters
        .Select((c, i) => new { Value = c, Index = i })
        .ToDictionary(x => x.Value, x => x.Index);
}

Then in your StringToInt method:

char next = encodedString[currentChar];

// No enumerating -- we've gone from O(N) to O(1)!
if (!characterIndices.TryGetValue(next, out nextCharIndex))
{
    throw new ArgumentException("Input includes illegal characters.");
}

Answer 2

I have a first-pass of a working version here, albeit I'm not sure how efficient it is.

public static int StringToInt(string encodedString, char[] baseChars)
    {
        int result = 0;
        int sourceBase = baseChars.Length;
        int nextCharIndex = 0;

        for (int currentChar = encodedString.Length - 1; currentChar >= 0; currentChar--)
        {
            char next = encodedString[currentChar];

            // For loop gets us: baseChar.IndexOf(char) => int
            for (nextCharIndex = 0; nextCharIndex < baseChars.Length; nextCharIndex++)
            {
                if (baseChars[nextCharIndex] == next)
                {
                    break;
                }
            }

            // For character N (from the end of the string), we multiply our value
            // by 64^N. eg. if we have "CE" in hex, F = 16 * 13.
            result += (int)Math.Pow(baseChars.Length, encodedString.Length - 1 - currentChar) * nextCharIndex;
        }

        return result;
    }

Answer 3

Here is a version using Linq functionality and .NET Framework 4.0 Zip extension to perform the calculation.

public static int StringToInt(string encodedString, char[] baseChars) {
    int sourceBase = baseChars.Length;

    var dict = baseChars
        .Select((c, i) => new { Value = c, Index = i })
        .ToDictionary(x => x.Value, x => x.Index);

    return encodedString.ToCharArray()
        // Get a list of positional weights in descending order, calcuate value of weighted position
        .Zip(Enumerable.Range(0,encodedString.Length).Reverse(), (f,s) => dict[f] * (int)Math.Pow(sourceBase,s)) 
        .Sum();
}

FYI, calculating the dictionary once outside the function would be more efficient for a large batch of transformations.

Answer 4

Here's a complete solution that converts a base10 number to baseK and back:

public class Program
{
    public static void Main()
    {
        int i = 100;

        Console.WriteLine("Int:               " + i);

        // Default base definition. By moving chars around in this string, we can further prevent
        // users from guessing identifiers.
        var baseDefinition = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        //var baseDefinition = "WBUR17GHO8FLZIA059M4TESD2VCNQKXPJ63Y"; // scrambled to minimize guessability

        // Convert base10 to baseK
        var newId = ConvertToBaseK(i, baseDefinition);
        Console.WriteLine(string.Format("To base{0} (short): {1}", baseDefinition.Length, newId));

        // Convert baseK to base10
        var convertedInt2 = ConvertToBase10(newId, baseDefinition);
        Console.WriteLine(string.Format("Converted back:    {0}", convertedInt2));
    }

    public static string ConvertToBaseK(int val, string baseDef)
    {
        string result = string.Empty;
        int targetBase = baseDef.Length;

        do
        {
            result = baseDef[val % targetBase] + result;
            val = val / targetBase;
        } 
        while (val > 0);

        return result;
    }

    public static int ConvertToBase10(string str, string baseDef)
    {
        double result = 0;
        for (int idx = 0; idx < str.Length; idx++)
        {
            var idxOfChar = baseDef.IndexOf(str[idx]);
            result += idxOfChar * System.Math.Pow(baseDef.Length, (str.Length-1) - idx);
        }

        return (int)result;
    }
}

Answer 5

If base-64 is really what you need rather than "any base" then everything you need is already built in to the framework:

int orig = 1337;
byte[] origBytes = BitConverter.GetBytes(orig);
string encoded = Convert.ToBase64String(origBytes);
byte[] decoded = Convert.FromBase64String(encoded);
int converted = BitConverter.ToInt32(decoded, 0);
System.Diagnostics.Debug.Assert(orig == converted);