Results 1 to 11 of 11

Math Help - Large integers to binary format

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    9

    Large integers to binary format

    hello,

    i don't know if this question is suitable here,

    my question is : is there an algorithm to convert a large number in base 10 (large number means 5000 digits for example) to base 2 (ie, binary) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elfizia2001 View Post
    hello,

    i don't know if this question is suitable here,

    my question is : is there an algorithm to convert a large number in base 10 (large number means 5000 digits for example) to base 2 (ie, binary) ?
    Yes, I use this algorithm, pseudocode

    Code:
    set n <- <your number>
    set S <- <empty string>
    while (n > 0)
        set S <- (n % 2) + S
        set n <- floor(n / 2)
    end while
    % operator is "mod" giving the remainder (common residue).

    The string addition means concatenation.

    It's just bit-shifting explicitly.

    Note that this algorithm works for any base going to any base (change the twos to whatever base you want to change into, and make sure numbers above 9 are rendered properly when you do % for bases >10).
    Last edited by undefined; July 18th 2010 at 10:31 AM. Reason: further details
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9
    Quote Originally Posted by undefined View Post
    Code:
    set n <- <your number>
    set S <- <empty string>
    while (n > 0)
        set S <- (n % 2) + S
        set n <- floor(n / 2)
    end while
    % operator is "mod" giving the remainder (common residue).

    It's just bit-shifting explicitly.
    but when you want to implement this algorithm in computer program like c for example, you will not be able to get the binary of large numbers like 2^512 for example. remember that computer registers are as far as i know 64 bits)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elfizia2001 View Post
    but when you want to implement this algorithm in computer program like c for example, you will not be able to get the binary of large numbers like 2^512 for example.
    How do you store such numbers? As strings? Write a function to divide these large numbers by 2. (Just code the algorithm used to do long division with paper and pencil taught in grade school.) Finding n % 2 is easy, just look at the least significant digit and say whether it's even or odd.

    No need to use such a big font; I can read.

    By the way, 2^512 in binary is a 1 followed by 512 zeroes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elfizia2001 View Post
    remember that computer registers are as far as i know 64 bits)
    You added this line afterwards. Perhaps you're concerned about storage of the large binary numbers? If you don't want to store your binary number as a string, you can use some sort of boolean array. I'm a bit spoiled by Java so I don't know about efficient ways to manipulate memory at the bit level, besides the standard << and >> operators, and &, etc.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2010
    Posts
    9
    Quote Originally Posted by undefined View Post
    No need to use such a big font; I can read.
    sorry , i apologize.

    Quote Originally Posted by undefined View Post
    By the way, 2^512 in binary is a 1 followed by 512 zeroes.
    i know that, but what i mean is the conversion of numbers with many digits, lets say 1000 digits for example, i gave 2^512 as an example just to show that computers can not manipulate it using basic operations like addition,multiplication,division...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elfizia2001 View Post
    sorry , i apologize.
    No problem

    Quote Originally Posted by elfizia2001 View Post
    i know that, but what i mean is the conversion of numbers with many digits, lets say 1000 digits for example, i gave 2^512 as an example just to show that computers can not manipulate it using basic operations like addition,multiplication,division...
    Here's an example of the grade school long division algorithm in Java.

    Code:
    public class LongDivis {
        public static void main(String[] args) {
            String bignum = "1239759239710009257124301243823";
            String quotient = longDivis(bignum, 7);
            System.out.println(quotient);
        }
        
        static String longDivis(String num, int divisor) {
            // does *integer division*, ie, discard remainder
            // assume string is of an integer (add a check if you want)
            int i, curr, remainder = 0, nextdig;
            String ret = "";
            for(i = 0; i < num.length(); i++) {
                curr = Integer.parseInt(num.substring(i, i+1));
                curr += 10 * remainder;
                nextdig = curr / divisor;
                if (ret.length() > 0 || nextdig != 0) ret += nextdig;
                remainder = curr % divisor;
            }
            return ret;
        }
    }
    Note that doing integer division is the same as doing regular division and taking the floor of the result.

    Edit: Fixed a dumb bug.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2010
    Posts
    9
    undefined, thank you.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    You can't directly manipulate huge numbers in a computer, true. This is why you build up your own instruction set. Have a look at this wikipedia link :

    Arbitrary-precision arithmetic - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bacterius View Post
    You can't directly manipulate huge numbers in a computer, true. This is why you build up your own instruction set. Have a look at this wikipedia link :

    Arbitrary-precision arithmetic - Wikipedia, the free encyclopedia
    I thought of mentioning this; I decided to just give the bare bones necessary to make my algorithm work.. I'm spoiled by Java's BigInteger and have heard that the free bignum libraries available for C/C++ can take a good amount of work setting up and getting used to. GMP is the main one I know of; I also remember hearing of one that's easier to set up and good for most things, unfortunately I can't find the reference.

    EDIT: Found the reference, here. The recommendation for a simpler alternative to GMP is NTL.
    Last edited by undefined; July 18th 2010 at 03:02 PM. Reason: removed a redundant word
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jul 2010
    Posts
    9
    thank you for your help, the references that you provide are very important. you gave me many ideas.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 26th 2010, 04:33 PM
  2. Number Format
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: September 28th 2009, 04:37 PM
  3. format
    Posted in the Calculus Forum
    Replies: 2
    Last Post: December 14th 2008, 02:17 PM
  4. Assignment Format
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: August 15th 2007, 04:08 PM

Search Tags


/mathhelpforum @mathhelpforum