1

I am trying to convert decimal Nos. into binary. The code works pretty fine (Windows 7 , 32 bit MS-VS2010): 

int main()
{

    int k, n;  
    int binary[100];
    printf("Enter the value in  decimal \n ");
    scanf("%d", &k);
    n = (log(k * 1.0) / log(2 * 1.0)) + 1  ; //total no. of binary bits in this decimal 

    for (int i = n; i > 0; i--)
        {
        binary[i] = k % 2;
        k /= 2;
        }

 return 0; 

}

But the limitation is that it works for Int size values only i.e. 32 bit. I want to modify this code so that it works for 2048 bits (decimal numbers containing 617 digits actually). I am not allowed to use any library.

Can someone give me some pointers how to proceed to tackle this?

Can someone give an example code snippet say for 64 bits ? Then I can use this to extend to higher values.

Update

1-As per suggestions I am trying to use strings. But I am not able to understand how to convert an String into large Int (I cant use stoi() as thsi will convert to 32 bit int , right? ).

2- Secondly I have to find:

log(222121212213212313133123413131313131311313154515441315413451315641314563154134156313461316413415635154613415645156451434)

Is the library function log capable of finding this ? Then what is the solution?

user3891236
  • 607
  • 1
  • 9
  • 23
  • 5
    Read the number as a string instead of an `int`. Then process the digits in the string. – huysentruitw Dec 18 '14 at 13:24
  • @legends2k I am not allowed to use any library. – user3891236 Dec 18 '14 at 13:24
  • 2
    You don't need a library, just take the input string and convert. – 2501 Dec 18 '14 at 13:25
  • @legends2k Thanks for the suggestions. But why you said "academic purpose"? – user3891236 Dec 18 '14 at 13:26
  • 3
    If you're learning, there's no point in using libraries as there's not much you'll learn. You'll just get the end result directly and things will seem like magic, you wouldn't know how it happened. However, for production code, instead of reinventing the wheel, maintaining the bugs that ensue, using a time-tested library, if that's an option, is the way to go. Even then, you should choose a library and use it with some knowledge on what it does. – legends2k Dec 18 '14 at 13:28
  • @WouterHuysentruit How would I process string with log? That string will be 500digits, that too string. I cant use atoi(s); rigth ? – user3891236 Dec 18 '14 at 13:52
  • 1
    [Here are some excellent pointers](http://xkcd.com/138/). – bitmask Dec 18 '14 at 14:24
  • @legends2k Need a little more push to proceed. Kindly see my update – user3891236 Dec 18 '14 at 14:33
  • 1
    You're already using libc and libm if you have `printf`, `scanf`, and `log`, so what are your actual restrictions, just the stdlib? – Ryan Haining Dec 18 '14 at 16:19
  • My impression is that you have to implement some arithmetics yourself. What precision should your numbers have (how many digits before and after the comma)? What arithmetical operations should you perform? (Aside from the log). What precision should the logarithm result have? Did you get any clue about how to implement the logarithm? BTW The books from Donald E Knuth contain valuable information here. But the algorithms have errors, so do yourself a favour and check the errata, if you want to apply them. – mvw Dec 18 '14 at 16:20
  • That mentioning of bits makes me wonder if you were asked to perform base 2 arithmetics, a la the usual IEEE floating point routines only with larger bit fields. – mvw Dec 18 '14 at 16:24

3 Answers3

1

Since you told that you just need some pointers and not the actual answer, here goes:

I am not able to understand how to convert an String into large Int

That's because you can't. If you want to convert a number that huge to a numerical type, in the first place you need such a type that can hold numbers that big. The language doesn't provide you anything more than long long which is usually 128-bits long (i.e. if you can use C99, or just long which is usually lesser than a long long). Since your tutor told you not to use any external library, it's a clear sign that s/he wants you to code the solution using what's available only in the language and perhaps additionally the standard library.

Is the library function log capable of finding this

No, you can't use stoi or log since all of these expect arguments of some arithmetic type, while none of those built-in types are that big to hold numbers this huge. So you've to work completely with strings (i.e. either static or dynamic char buffers).

I understand that you want to use log to deduce the number of digits the binary output would need; but there's another option, which is to not know the number of digits before hand and allocate them dynamically with some upper bound so that you needn't re-allocate them further.

Lets take an example.

  1. Allocate 3 char buffers in, out (length of input) and bin (length of input * 4).
  2. Copy input to in
  3. While in is not "0" or "1" do else goto 12
  4. For each element ch in in do else goto 10
  5. Convert ch to integer i
  6. If is_odd = 1 then i += 10
  7. quot = i / 2
  8. Append quot to out
  9. is_odd = quot % 2; goto 4
  10. If is_odd = 1 append '1' else '0' to bin
  11. Copy out to in, reset out and goto 3
  12. Append in to bin
  13. Print bin in reverse

When you integer divide a number by 2, the quotient would always be less than or equal to the number of digits of the dividend. So you could allocate in and out with the same size as the input and use it for all iterations. For the bin buffer, the knowledge that each decimal digit wouldn't take more than 4 bits (9 takes a nibble, 1001) would help. So if the input is 10 digits, then 10*4 = 40 bytes would be the upper limit needed for bin buffer and 10 bytes would be needed for the in and out buffers.

This is a vague write-up of an algorithm, I hope it conveys the idea. I feel writing code is more easier than writing algorithms properly.

legends2k
  • 31,634
  • 25
  • 118
  • 222
0

I'm afraid there are no standard types in C that will allow you to store such a big value with 20148 bits... You can try to read the string from console (not converting into int), and then parse the string into "010101...." on your own.

The approach would be like that:
You should go for "dividing" the string by 2 in each step (for each division by 2 you need to divide all digits of the string by 2, and handle special cases like 11 / 2 => 5), and for each step if the value cannot be divided by 2, then you then you can put "1" as another binary digit, otherwise you put "0". This way you gather the digits '0', '1', '0', '1', etc. one by one. Then finally you need to reverse the order of digits. A similar approach implemented in C# you can find here: Decimal to binary conversion in c #

Community
  • 1
  • 1
msporek
  • 1,187
  • 8
  • 21
0

Regarding the update:

Grinding it through WolframAlpha gives:

log(222121212213212313133123413131313131311313154515441315413451315641314563154134156313461316413415635154613415645156451434)

is roughly

274.8056791141317511022806994521207149274321589939103691837589..

Test:

Putting it into exp gives:

2.2212121221321231313312341313131313131131315451544131541.. × 10^119

This raises the question about the precision you need.

Note: I assumed you mean the natural logarithm (base e).

mvw
  • 5,075
  • 1
  • 28
  • 34
  • Basically that log is for finding total no. of bits in a decimal no. that we enter. And this is log base 10. I want to do it in my C program, but log cant handle such big numbers. – user3891236 Dec 19 '14 at 06:06