Large number conversion, ASCII to binary

[fermineutron]

I am trying to write a function which will convert a large ascii
number, say 100 ascii digits, to its binary representation. It seems
that evey algorithm I am trying to think of is backwards. Normaly in
pen and paper ascii to binary conversion one would start by
subtracting largest power of 2 that can be subtracted from the given
number and work from left to right filling memory up with 1s and 0s.
In my case I cant really do that b/c the largest power of 2 which
would fit into a number i am trying to convert is too large even for
64 bit int.

Any help, suggestions, sample code would be greatly apreciated.

ets assume I have an array of char type, evey element of which has a
value equal to the value of next digit in ascii number.

Thanks ahead

 

[Barry Schwarz]

I am trying to write a function which will convert a large ascii
number, say 100 ascii digits, to its binary representation. It seems
that evey algorithm I am trying to think of is backwards. Normaly in
pen and paper ascii to binary conversion one would start by
subtracting largest power of 2 that can be subtracted from the given
number and work from left to right filling memory up with 1s and 0s.
In my case I cant really do that b/c the largest power of 2 which
would fit into a number i am trying to convert is too large even for
64 bit int.

Any help, suggestions, sample code would be greatly apreciated.

ets assume I have an array of char type, evey element of which has a
value equal to the value of next digit in ascii number.

Any of the "big number" libraries should provide the tools you need. I
happen to like the bignum part of clint by Richard Heathfield but that
may be because it's the only one I've studied.


Remove del for email

 

[Ben Bacarisse]

I am trying to write a function which will convert a large ascii
number, say 100 ascii digits, to its binary representation.

Homework? If not, use a bignum library (it will pay eventually). If
it is homework, I'll show you mine if you show me yours...

 

[rahul]

If your problem is regarding some production code, then it's better
not to re-invent the wheel and use some existing library. If it is for
pedagogical purpose, you ought to post your approach.

 

[CBFalconer]

Homework? If not, use a bignum library (it will pay eventually).
If it is homework, I'll show you mine if you show me yours...

All he needs is a mechanism for multiplying some value by 10 and
adding another value to it. The 'other value' need not exceed 10.
Don't drop any digits.

 

[Ben Bacarisse]

All he needs is a mechanism for multiplying some value by 10 and
adding another value to it. The 'other value' need not exceed 10.
Don't drop any digits.

Another way is to have a method to halve a number (easy even when the
number is a digit string) and a test for parity and zero.

 

[CBFalconer]

The OP says he is using a 100 digit number. None of the Standard
integral types of C can hold such a large value. He either needs to
deal with it piece by piece (as bignum routines do) or manipulate
it in it's string form, or use an available bignum library like GMP.

Where did I say to use a standard C integral type? Where did I say
to use a standard C type? The 'struct' keyword allows creation of
your own types.

 

[Bartc]

I am trying to write a function which will convert a large ascii
number, say 100 ascii digits, to its binary representation. It seems
that evey algorithm I am trying to think of is backwards. Normaly in
pen and paper ascii to binary conversion one would start by
subtracting largest power of 2 that can be subtracted from the given
number and work from left to right filling memory up with 1s and 0s.
In my case I cant really do that b/c the largest power of 2 which
would fit into a number i am trying to convert is too large even for
64 bit int.

Any help, suggestions, sample code would be greatly apreciated.

Your 100-digit number would need over 300 binary digits. You need to decide
exactly what data structure to use.

Different numbers will all have different lengths so you also have to decide
whether to have a variable length structure for each number, or have the
same maximum size for all. And you have to decide how to represent negative
values and so on.

Then, you might look at the best ways of converting the text to binary,
which usually involves multiplying by ten then adding the next digit.

But if you use an existing library for this stuff, that will specify what
data structure to use.

 

[fermineutron]

Thanks for all of the replies, this is not a homework problem, let me
assure you of that. The reason why i stayed away from using large int
libraries is b/c I want to manipulate the number as a whole and its
parts mathematically. I know I am not the smartest man in the world,
nether the less I want to try my hand at the classical large number
problem. My approach is as follows:

Given Large number N which is the product of 2 primes.
Let N=(a1*2^n + b1)*(a1*2^n+b2)
here n is the size of b1 and b2 in bits.
Foiling yields:
1) The last 2*n bits of N depending on values of b1 and b2.
2) The last n bits of N depend on ONLY b1 and b2.
The algorithm then becomes:
1) Choose a X0 numbers of 2n bits in length with last n bits equal to
right most n bits of N, such that can be factored.
2) Generate 2 vectors v10, v20, elements of which are the factors of
elements of X0.
3) repeat steps 1 and 2 increasing the length of items in Xj by n bits
at a time. Only include into Xj numbers which have factors with least
significant bits completely defined by numbers from v1j-1 and v2j-1.
Repeat until Xj consists of only 1 number which is N.

Theoretically there is no need to keep track of v2j but having it at
hand might speed up the inner loop.

Any 1 can suggest best approach to implement this algorithm of can
tell me why its the most stupid thing you have ever heard?


Theoretically this algorithm should coverage in P(m) time where m is
length of N in bits. Even though you are potentially increasing the
number of operations by factor of 2 per bit moved left, that is nor
really so b/c with each shift you are imposing new restrictions to the
existing pool of possible factors, reducing its size.

 

[fermineutron]

Now that I posted the algorithm I am kind of afraid, what if someone
smarter than me writes the code to do it and it actually works. Bye
Bye: PGP, SSL etc...

 

[Ben Bacarisse]

Now that I posted the algorithm I am kind of afraid, what if someone
smarter than me writes the code to do it and it actually works. Bye
Bye: PGP, SSL etc...

You will get fame and fortune for inventing it (if it is new and
interesting). For what it is worth, I could not follow what you
wrote. It would help (since you have some trouble with English) if
you wrote the algorithm in maths rather than using words. However...

You don't (yet) have a C question. You should ask in a cryptographic
group (sci.crypt?) or maybe a general group like comp.programing.