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
% operator is "mod" giving the remainder (common residue).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).
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.
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.
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...
No problem
Here's an example of the grade school long division algorithm in Java.
Note that doing integer division is the same as doing regular division and taking the floor of the result.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.
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.