# Large integers to binary format

• Jul 18th 2010, 08:40 AM
elfizia2001
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) ?
• Jul 18th 2010, 09:21 AM
undefined
Quote:

Originally Posted by elfizia2001
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).

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).
• Jul 18th 2010, 09:31 AM
elfizia2001
Quote:

Originally Posted by undefined
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)
• Jul 18th 2010, 09:33 AM
undefined
Quote:

Originally Posted by elfizia2001
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.
• Jul 18th 2010, 09:49 AM
undefined
Quote:

Originally Posted by elfizia2001
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.
• Jul 18th 2010, 09:52 AM
elfizia2001
Quote:

Originally Posted by undefined
No need to use such a big font; I can read.

sorry , i apologize.

Quote:

Originally Posted by undefined
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...
• Jul 18th 2010, 10:01 AM
undefined
Quote:

Originally Posted by elfizia2001
sorry , i apologize.

No problem

Quote:

Originally Posted by elfizia2001
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.
• Jul 18th 2010, 10:17 AM
elfizia2001
undefined, thank you.
• Jul 18th 2010, 12:18 PM
Bacterius
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
• Jul 18th 2010, 01:01 PM
undefined
Quote:

Originally Posted by Bacterius
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.
• Jul 18th 2010, 02:00 PM
elfizia2001
thank you for your help, the references that you provide are very important. you gave me many ideas.