PowerOfTwo and recursion



  • "I am trying to write a method in Java that will take an int and return 2^int, as string, in decimal. I am doing this because I need to do stuff with very large powers of two, such as 2^1024, and long can't hold that [...] If I call it more than twice with 1024 I get a Stack Overflow [...] Also, is there a less, er, verbose way of doing what I have done here?"

    public static String powerOfTwo(int exp){
                    if (exp < 0){
                            return "Error, only positive exponents supported";
                    } else if (exp == 0){
                            return "1";
                    } else {
                            String toDouble = powerOfTwo(exp - 1);
                            int carry = 0;
                            String toReturn = "";
                            for (int i = 0; i < toDouble.length(); i++){
                                    char digit = toDouble.charAt(i);
                                    if (carry == 0){
                                            if (digit == "0".charAt(0)){
                                                    toReturn = "0" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "1".charAt(0)){
                                                    toReturn = "2" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "2".charAt(0)){
                                                    toReturn = "4" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "3".charAt(0)){
                                                    toReturn = "6" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "4".charAt(0)){
                                                    toReturn = "8" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "5".charAt(0)){
                                                    toReturn = "0" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "6".charAt(0)){
                                                    toReturn = "2" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "7".charAt(0)){
                                                    toReturn = "4" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "8".charAt(0)){
                                                    toReturn = "6" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "9".charAt(0)){
                                                    toReturn = "8" + toReturn;
                                                    carry = 1;
                                            } else {
                                                    return "Error, nonnumberical string";
                                            }
                                    } else {//carry = 1
                                            if (digit == "0".charAt(0)){
                                                    toReturn = "1" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "1".charAt(0)){
                                                    toReturn = "3" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "2".charAt(0)){
                                                    toReturn = "5" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "3".charAt(0)){
                                                    toReturn = "7" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "4".charAt(0)){
                                                    toReturn = "9" + toReturn;
                                                    carry = 0;
                                            }else if (digit == "5".charAt(0)){
                                                    toReturn = "1" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "6".charAt(0)){
                                                    toReturn = "3" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "7".charAt(0)){
                                                    toReturn = "5" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "8".charAt(0)){
                                                    toReturn = "7" + toReturn;
                                                    carry = 1;
                                            }else if (digit == "9".charAt(0)){
                                                    toReturn = "9" + toReturn;
                                                    carry = 1;
                                            } else {
                                                    return "Error, nonnumberical string";
                                            }
                                    }
                            }
                            //attach final carry
                            if (carry == 1){
                                    toReturn = "1" + toReturn;
                            }
                           
                            return toReturn;
                    }
            }



  •  doesn't java have a standard bignumber library?



  • @gordy said:

     doesn't java have a standard bignumber library?

     

    That wouldn't be enterprisey enough. 



  • At least whoever originally posted that is smart enough to suspect there must be a better way of doing it.



  • @gordy said:

     doesn't java have a standard bignumber library?

    Actually, it has two.



  • Dude, just use a BigNumber initialized to 1 and bit shift left by n, then call toString. So something like this:

    return BIGNUMBER_ONE.shiftLeft(n).toString()

    Also, you really should implement actual error handling instead of returning an error message in the string.



  • But java doesn't provide a NonNumbericalException :-) 



  • @imikedaman said:

    Also, you really should implement actual error handling instead of returning an error message in the string.
     

    Bah, come on. The regex school of exception handling has been passed on by generations of PHP coders, so it can't possibly be wrong.



  • It could be C Pound as well.



  • Good lord, man, don't return error messages in the return value.

    EXCEPTIONS!

    Throw them! They're there for a reason! Something exceptional and unexpected happened! The user passed an Illegal Argument! Maybe you should throw an...

    IllegalArgumentException

    Honestly.



  • @bstorer said:

    @gordy said:

     doesn't java have a standard bignumber library?

    Actually, it has two.

     

     

    the second much better one was checked in by lyle. 



  • @imikedaman said:

    Dude, just use a BigNumber initialized to 1 and bit shift left by n, then call toString. So something like this:

    return BIGNUMBER_ONE.shiftLeft(n).toString()

    Also, you really should implement actual error handling instead of returning an error message in the string.

    Assuming it's Java, that should be BigInteger.ONE.shiftLeft(n).toString()

    ...not that I understand why anyone would want it as a string when Big* classes exist.

    The two Big* classes also have a pow() method for slightly more readable code, although it'll be much slower for large exponents.



  • @fbjon said:

    Assuming it's Java, that should be BigInteger.ONE.shiftLeft(n).toString()

    Ah, thank you. I don't really know Java so I ended up typing stuff into Google to figure out what the correct code would be. Turns out I inadvertently used documentation for a proprietary API instead of the official Java documentation!



  • instead, run it with:
    java -Xss10m myprog

    Not the "right" answer (which is of course BigInteger, or even just using iteration instead of recursion), but a 10 MB stack would let him safely calculate 2^1024.



  • (...)nonnumberical string(...)

    I feel numb after reading this.


Log in to reply