5
\$\begingroup\$

On a whim, I came up with this program to act as a helper class for base changing, if I require it in the future. It was made to support fixed-point and negative inputs, but they are basically a hack. I used conventional mathematics for the algorithm, and I welcome any appreciation or criticism that may come my way.

Note:

Forgive the snake_case naming of some local variables, I know it's not the standard for Java code, but it hurts my eyes less than camelCase.

Algorithmic and code improvements are welcome. This code is tested to work (I tested it against WolframAlpha). You might want to try out 12345 decimal to base 236. It should give 52 73 if the boolean parameter substituteNumerics is false. changeBase(String,int,int,boolean) is the correct entry point. I used the BlueJ IDE to get away without a main method, but you might need one.

Disclaimer:

Look ma, no comments! Please forgive me. I was in a bit of a rush, so there aren't comments, but I hope the code is pretty self-documenting. I might add some documentation comments later, so no need to worry about that.

public class BaseConverter{
    protected static final String negativeBaseErrorMessage="Negative or zero base values are illegal - supplied bases were %d & %d.",

    invalidInputNumberErrorMessage="The supplied number(%s) for base conversion is invalid.";

    private static String lookup="0123456789ABCDEFGHIJKLMNOPQRSTWXYZabcdefghijklmnopqrstwxyz+/=,?!;:\"'^`~|\\@#$%&*_<>(){}";

    private static void updateLookup(int to_base){
        if(to_base>lookup.length()){
            while(lookup.length()<=to_base){
                for(int i=0;i<Short.MAX_VALUE;++i){
                    if((!lookup.contains(""+(char)i))&&
                    (!Character.isISOControl((char)i))&&
                    (!Character.isWhitespace((char)i))&&
                    ((char)i!='.')&&(char)i!='-'){
                        lookup+=(char)i;break;
                    }
                }
            }
        }
    }

    public static long convertToNumber(String inputNumber,int from_base){
        long number=0;
        for(int i=0;i<inputNumber.length();++i){
            number+=lookup.indexOf(inputNumber.charAt(i))*Math.round(Math.pow(from_base,(inputNumber.length()-1)-i));
        }
        return number;
    }

    private static int[] createDigits(long number,int to_base){
        int[]digits;
        long tmp_number=number;
        int num_digits=0;
        while(tmp_number>0){
            tmp_number/=to_base;
            ++num_digits;
        }
        digits=new int[num_digits];
        num_digits=0;
        while(number>0){
            digits[num_digits++]=(int)number%to_base;
            number/=to_base;
        }
        return digits;
    }

    public static String changeBase(String inputNumber,int from_base,int to_base){
        return changeBase(inputNumber,from_base,to_base,true);
    }

    private static boolean isInvalidInputNumber(String inputNumber){
        return inputNumber.startsWith(".")||
               inputNumber.endsWith(".")||
               inputNumber.endsWith("-");
    }

    public static String changeBase(String inputNumber,int from_base,int to_base,boolean substituteNumerics){
        boolean isNegative=false;
        if(inputNumber.startsWith("-")){
            inputNumber=inputNumber.substring(1,inputNumber.length());
            isNegative=true;
        }
        if(isInvalidInputNumber(inputNumber)){
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage,inputNumber));
        }
        if(from_base<=0||to_base<=0){
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage,from_base,to_base));
        }
        updateLookup(to_base);
        if(inputNumber.contains(".")){
            return changeBase(inputNumber.substring(0,inputNumber.indexOf(".")),from_base,to_base,substituteNumerics)+"."+
            changeBase(inputNumber.substring(inputNumber.indexOf(".")+1,inputNumber.length()),from_base,to_base,substituteNumerics);
        }
        String new_number="";
        int[] digits=createDigits(convertToNumber(inputNumber,from_base), to_base);
        if(substituteNumerics){
            for(int i=digits.length-1;i>=0;--i){
                new_number+=lookup.charAt(digits[i]);
            }
        }else{
            for(int i=digits.length-1;i>=0;--i){
                new_number+=digits[i]+" ";
            }
        }
        return (isNegative)?"-"+new_number.trim():new_number.trim();
    }
}

A test class with a main method:

public class BaseConverterTest
{
    public static void main(String[]args){
        if(args.length==3){
            System.out.println(
            BaseConverter.changeBase(args[0],
            Integer.parseInt(args[1]),
            Integer.parseInt(args[2])));
        }else if(args.length==4){
            System.out.println(
            BaseConverter.changeBase(args[0],
            Integer.parseInt(args[1]),
            Integer.parseInt(args[2]),
            Boolean.parseBoolean(args[3])));
        }else{
            throw new IllegalArgumentException("Invalid Command Line Arguments");
        }
    }
}

Ensure both files are in the same folder!

\$\endgroup\$
  • \$\begingroup\$ Technically, any complex number that does not have an absolute value of either 1 or 0 can be used, but admittedly, we humans have trouble with anything other than positive integer bases. \$\endgroup\$ – Donald.McLean Mar 17 '16 at 9:21
  • \$\begingroup\$ @Donald.McLean I don't think I'll ever require those kinds of bases for whatever reason (I'm not a mathematician by any definition). Thanks for the tidbit, BTW! \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 9:22
5
\$\begingroup\$

Bugs

You've got a few bugs;

System.out.println(BaseConverter.changeBase(""+0x7FFF_FFFF_FFFF_FFFFL, 10, 16, true));

Will give IndexOutOfBoundsException: String index out of range: -1.

System.out.println(BaseConverter.changeBase(""+100000, 10, 70000, true));

Will give an infinite loop.

System.out.println(BaseConverter.changeBase("0", 10, 16, true));

Gives back empty string, (should be "0")

System.out.println(BaseConverter.changeBase("-0", 10, 16, true));

or

System.out.println(BaseConverter.changeBase("--1", 10, 16, true));

Gives back "-". ("-1") works normally. The "-0" case could return 0, or minus zero (that's a thing) if you felt like it. "--1" is obviously parse error.

System.out.println(BaseConverter.changeBase("1-1", 10, 16, false));

Gives back "5 11", which... I have no idea what it means. I guess you're treating this as "91", which ... well, I think this too is parse error.


I think that if you're in a rush, you should make use of automated helpers as much as possible. I get that if you don't have a lot of time, you can write code with 1 pass only, and that's it. It's not a sustainable practice, but if you need something done TODAY, so you can ship it, and then improve the code whilst the release is being "tested" by customers, well, that could be a viable business practice.

However, that (in my opinion) does not excuse you from using something like an auto-formatter and whitespace. Whitespace is free - provided you place all the braces, you can insert spaces and newlines where you like.

So lets haul it through a formatter.

public class BaseConverter {
    protected static final String negativeBaseErrorMessage = "Negative or zero base values are illegal - supplied bases were %d & %d.",

    invalidInputNumberErrorMessage="The supplied number(%s) for base conversion is invalid.";

    private static String lookup = "0123456789ABCDEFGHIJKLMNOPQRSTWXYZabcdefghijklmnopqrstwxyz+/=,?!;:\"'^`~|\\@#$%&*_<>(){}";

    private static void updateLookup(int to_base) {
        if (to_base > lookup.length()) {
            while (lookup.length() <= to_base) {
                for (int i = 0; i < Short.MAX_VALUE; ++i) {
                    if ((!lookup.contains("" + (char) i)) &&
                        (!Character.isISOControl((char) i)) &&
                        (!Character.isWhitespace((char) i)) &&
                        ((char) i != '.') && (char) i != '-') {
                        lookup += (char) i;
                        break;
                    }
                }
            }
        }
    }

    public static long convertToNumber(String inputNumber, int from_base) {
        long number = 0;
        for (int i = 0; i < inputNumber.length(); ++i) {
            number += lookup.indexOf(inputNumber.charAt(i)) * Math.round(Math.pow(from_base, (inputNumber.length() - 1) - i));
        }
        return number;
    }

    private static int[] createDigits(long number, int to_base) {
        int[] digits;
        long tmp_number = number;
        int num_digits = 0;
        while (tmp_number > 0) {
            tmp_number /= to_base;
            ++num_digits;
        }
        digits = new int[num_digits];
        num_digits = 0;
        while (number > 0) {
            digits[num_digits++] = (int) number % to_base;
            number /= to_base;
        }
        return digits;
    }

    public static String changeBase(String inputNumber,int from_base,int to_base){
        return changeBase(inputNumber,from_base,to_base,true);
    }

    private static boolean isInvalidInputNumber(String inputNumber){
        return inputNumber.startsWith(".") ||
               inputNumber.endsWith(".") ||
               inputNumber.endsWith("-");
    }

    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {
        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }
        if (isInvalidInputNumber(inputNumber)) {
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
        }
        if (from_base <= 0 || to_base <= 0) {
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
        }
        updateLookup(to_base);
        if (inputNumber.contains(".")) {
            return changeBase(inputNumber.substring(0, inputNumber.indexOf(".")), from_base, to_base, substituteNumerics) + "." +
                   changeBase(inputNumber.substring(inputNumber.indexOf(".")+1,inputNumber.length()),from_base,to_base,substituteNumerics);
        }
        String new_number = "";
        int[] digits = createDigits(convertToNumber(num, from_base), to_base);
        if (substituteNumerics) {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += lookup.charAt(digits[i]);
            }
        } else {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += digits[i] + " ";
            }
        }
        return (isNegative) ? "-" + new_number.trim() : new_number.trim();
    }
}

To me, it reads quite a lot better; and that's just by pressing auto-format button on the IDE.

Next, since we're assuming you have no time, just insert whitespace. Whenever you start doing a different thing, add a new blank line.

public class BaseConverter {
    protected static final String negativeBaseErrorMessage = "Negative or zero base values are illegal - supplied bases were %d & %d.",

    invalidInputNumberErrorMessage="The supplied number(%s) for base conversion is invalid.";

    private static String lookup = "0123456789ABCDEFGHIJKLMNOPQRSTWXYZabcdefghijklmnopqrstwxyz+/=,?!;:\"'^`~|\\@#$%&*_<>(){}";

    private static void updateLookup(int to_base) {
        if (to_base > lookup.length()) {
            while (lookup.length() <= to_base) {
                for (int i = 0; i < Short.MAX_VALUE; ++i) {
                    if ((!lookup.contains("" + (char) i)) &&
                        (!Character.isISOControl((char) i)) &&
                        (!Character.isWhitespace((char) i)) &&
                        ((char) i != '.') && (char) i != '-') {
                        lookup += (char) i;
                        break;
                    }
                }
            }
        }
    }

    public static long convertToNumber(String inputNumber, int from_base) {
        long number = 0;
        for (int i = 0; i < inputNumber.length(); ++i) {
            number += lookup.indexOf(inputNumber.charAt(i)) * Math.round(Math.pow(from_base, (inputNumber.length() - 1) - i));
        }
        return number;
    }

    private static int[] createDigits(long number, int to_base) {
        int[] digits;
        long tmp_number = number;
        int num_digits = 0;
        while (tmp_number > 0) {
            tmp_number /= to_base;
            ++num_digits;
        }
        digits = new int[num_digits];

        num_digits = 0;
        while (number > 0) {
            digits[num_digits++] = (int) number % to_base;
            number /= to_base;
        }
        return digits;
    }

    public static String changeBase(String inputNumber,int from_base,int to_base){
        return changeBase(inputNumber,from_base,to_base,true);
    }

    private static boolean isInvalidInputNumber(String inputNumber){
        return inputNumber.startsWith(".") ||
               inputNumber.endsWith(".") ||
               inputNumber.endsWith("-");
    }

    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {
        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }

        if (isInvalidInputNumber(inputNumber)) {
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
        }

        if (from_base <= 0 || to_base <= 0) {
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
        }

        updateLookup(to_base);
        if (inputNumber.contains(".")) {
            return changeBase(inputNumber.substring(0, inputNumber.indexOf(".")), from_base, to_base, substituteNumerics) + "." +
                   changeBase(inputNumber.substring(inputNumber.indexOf(".")+1,inputNumber.length()),from_base,to_base,substituteNumerics);
        }

        String new_number = "";
        int[] digits = createDigits(convertToNumber(num, from_base), to_base);
        if (substituteNumerics) {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += lookup.charAt(digits[i]);
            }
        } else {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += digits[i] + " ";
            }
        }

        return (isNegative) ? "-" + new_number.trim() : new_number.trim();
    }
}

I just added new lines, see? The purpose of these new lines is to show that there are different parts to your code, so that if you come back to it later, it will read better. When you don't have time, goal is to both get the product out; but also make sure you can still clean it up later. Keep it salvageable.


Now, it's the next week, and you gotta clean this up.

Let's start by extracting code to functions, because that bottom function has multiple line breaks, and it's doing too much.

    private static int[] createDigits(long number, int to_base) {
        int[] digits;
        long tmp_number = number;
        int num_digits = 0;
        while (tmp_number > 0) {
            tmp_number /= to_base;
            ++num_digits;
        }
        digits = new int[num_digits];

        num_digits = 0;
        while (number > 0) {
            digits[num_digits++] = (int) number % to_base;
            number /= to_base;
        }
        return digits;
    }

This function is special because I had trouble placing the line break, but really, you're doing two things: determining how long the array should be, and then filling the array.

So lets extract the first part into a function...

private static int findLengthOfRepresentation(long number, int in_base){
    int[] digits;
    long tmp_number = number;
    int num_digits = 0;
    while (tmp_number > 0) {
        tmp_number /= in_base;
        ++num_digits;
    }

    return num_digits;
}

Simple copy-paste...

There's a few useless things in there, though. We don't need the digits array, and we don't need to use tmp_number. Let's strip them out:

private static int findLengthOfRepresentation(long number, int in_base){
    int num_digits = 0;
    while (number > 0) {
        number /= in_base;
        ++num_digits;
    }

    return num_digits;
}

There, looks good.

Now, normally I'd convert the other half into a separate function as well, but then we have to go deal with the part where the array size might not be large enough, and that'd be a bother.

private static int[] createDigits(long number, int to_base) {
    int[] digits = new int[findLengthOfRepresentation(number, to_base)];

    int num_digits = 0;
    while (number > 0) {
        digits[num_digits++] = (int) number % to_base;
        number /= to_base;
    }
    return digits;
}

So this is what we'd get if we cleaned up the createDigits function.

Next up, changeBase.

    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {
        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }

        if (isInvalidInputNumber(inputNumber)) {
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
        }

        if (from_base <= 0 || to_base <= 0) {
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
        }

That's the first part.

But you know what? If we were to assume that you'd wrap your code in functions, it doesn't make complete sense!

    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {

        //checkNegative
        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }

        //throwIfInvalidInputNumber
        if (isInvalidInputNumber(inputNumber)) {
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
        }

        //throwIfInvalidBase
        if (from_base <= 0 || to_base <= 0) {
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
        }

Why would you first check the sign, and then perform parameter validation? It's a waste of cycles. If you reorder the code, you can migrate your checks to a separate function:

    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {
        validateChangeBaseArguments(from_base, to_base, inputNumber);

        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }

        updateLookup(to_base);
        if (inputNumber.contains(".")) {
            return changeBase(inputNumber.substring(0, inputNumber.indexOf(".")), from_base, to_base, substituteNumerics) + "." +
                   changeBase(inputNumber.substring(inputNumber.indexOf(".")+1,inputNumber.length()),from_base,to_base,substituteNumerics);
        }

        String new_number = "";
        int[] digits = createDigits(convertToNumber(num, from_base), to_base);
        if (substituteNumerics) {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += lookup.charAt(digits[i]);
            }
        } else {
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += digits[i] + " ";
            }
        }

        return (isNegative) ? "-" + new_number.trim() : new_number.trim();
    }

And in doing so, all the code in the function is code that's actually related to the thing it's supposed to do.


Performance

private static void updateLookup(int to_base) {
    if (to_base > lookup.length()) {
        while (lookup.length() <= to_base) {
            for (int i = 0; i < Short.MAX_VALUE; ++i) {
                if ((!lookup.contains("" + (char) i)) &&
                    (!Character.isISOControl((char) i)) &&
                    (!Character.isWhitespace((char) i)) &&
                    ((char) i != '.') && (char) i != '-') {
                    lookup += (char) i;
                    break;
                }
            }
        }
    }
}

That's REALLY bad for performance. If you have to make 4000 characters, you'd iterate through the first 1000 characters at least 3000 times. Not only that, you'd also use lookup.contains, meaning you'd be making ((1000*1000)/2)+(1000/2) or 500500 character comparisons in order to insert the 1001th character. That's REALLY, REALLY, REALLY slow.

You'd be better off doing the following:

  • figure out how much characters to add
  • don't use a while loop

So basically:

private static void updateLookup(int to_base) {
    int charactersToAdd = lookup.length() - to_base;
    if (charactersToAdd > 0) {
        for (int i = 0; i < Short.MAX_VALUE; ++i) {
            if ((!lookup.contains("" + (char) i)) &&
                (!Character.isISOControl((char) i)) &&
                (!Character.isWhitespace((char) i)) &&
                ((char) i != '.') && (char) i != '-') {
                lookup += (char) i;
                charactersToAdd--;
                if(charactersToAdd == 0){
                    break;
                }
            }
        }
    }
}

You'll have to figure out how to solve the infinite loop that exists here on your own, though.

\$\endgroup\$
  • \$\begingroup\$ My code was updated shortly before you posted your answer, maybe you would like to change some stuff? \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 9:46
  • \$\begingroup\$ @TamoghnaChowdhury I know, and usually you'd get your question edit rollbacked for this, but you were first, so I'll be changing my answer \$\endgroup\$ – Pimgd Mar 17 '16 at 9:47
  • \$\begingroup\$ Well, I did use BlueJ's auto-formatter, which is ridiculously barebones to speak of. I didn't want to fire up IDEA for <100 SLOC. After which SE's code formatting messed it up after the paste, and I had to go in and indent all the lines manually. What a pain! \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 9:50
  • \$\begingroup\$ Also something more ridiculous, check my profile. I'm still technically a kid, so all that shipping software to consumers stuff doesn't apply to me yet (I'm also studying medicine, so...). \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 9:52
  • \$\begingroup\$ Oh so you do have algorithmic improvements on hand? I'm anxious :P \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.