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) ?

Printable View

- Jul 18th 2010, 08:40 AMelfizia2001Large 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 AMundefined
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

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). - Jul 18th 2010, 09:31 AMelfizia2001
- Jul 18th 2010, 09:33 AMundefined
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 AMundefined
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 AMelfizia2001
sorry , i apologize.

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 AMundefined
No problem

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;

}

}

Edit: Fixed a dumb bug. - Jul 18th 2010, 10:17 AMelfizia2001
undefined, thank you.

- Jul 18th 2010, 12:18 PMBacterius
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 PMundefined
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 PMelfizia2001
thank you for your help, the references that you provide are very important. you gave me many ideas.