High-precision program that calculates 2^n

Question

I'm building a program in C that can get powers of 2. The user inputs the value of n, and the program calculates 2^n.

Here's the code.

The problem comes when I input 100

What I am getting:

1,267,650,600,228,229,400,000,000,000,000

What I should get

1,267,650,600,228,229,401,496,703,205,376

It has to be coded entirely in ANSI C. Any ideas on how to increase the precision? The maximum value of N has to be 256 (256 bits, I imagine, which means the maximum output should be 2^256).

What I'm lacking here is precision, and I don't know how to fix that. Any ideas?

Xanthic

see also #3341011 – Bloodletting

'double' type has only that number of significant digits, you can't have more. – Gereld

Bignum on C and C++ has got to be one of the most commonly asked questions that have a "difficult" solution. – Sensualism

Just one comment: I must NOT use external libraries. It has to be ANSI C. I'm practicing for an ACM contest, that's why :( – Xanthic

What Every Computer Scientist Should Know About Floating-Point Arithmetic – Ruhl

As @Sensualism makes reference to, you are looking for a bignum solution. For info on what this is, look at wikipedia: en.wikipedia.org/wiki/Arbitrary-precision_arithmetic – Araarab

even 'long double' type (as on my GCC 44) is only 96-bit type, it has at most 28 significant digits – Gereld

@Sensualism you are wrong about this being an extremely difficult problem. Implementing arbitrary precision addition is not exactly hardest thing in the world. – Ombudsman

Especially since it is only for 256 bits.... – Araarab

@Ombudsman yeah, to be honest, this was a problem in my secondary school programming book – Gereld

Would it be cheating to hardcode the 257 possible outputs into an array and just index on N? – Bemire

@Bemire That's not cheating, that's intelligent. What's not intelligent is all this nonsense about difficulty and [long] double types, which aren't appropriate to this integer problem. – Bacillary

@JimBalter Ok, my fault. I overlooked the simplicity of this specific problem since large multiplication is not needed. (and performance is irrelevant) The "difficult" part I was referring to is the general case with large multiplication/division. A basic implementation of large multiplication isn't too hard, but division is annoying. Achieving sub-quadratic and quasi-linear performance is a big can of worms that I won't open. – Sensualism

possible duplicate of Large doubles/float/numbers – Whitewing

@Sensualism I understand all that about about the general difficulty and annoyance ... see my comments under (and downvote of) dave's answer, which talks about the ease and convenience of binary operations on powers of two (which aren't even relevant here because it's just a matter of placing a single bit in the correct word), while completely ignoring the difficulty of doing MP division, blithely referring, without explanation, to "what a hardware divisor does". – Bacillary

Answer 1

Here is my quick and dirty implementation of hammar's approach., storing the decimal number as a C string with the digits in reverse order.

Run the code on ideone

void doubleDecimal(char * decimal)
{
    char buffer[256] = "";
    char c;
    unsigned char d, carry = 0;
    int i = 0;

    while (c = decimal[i])
    {
        d = 2 * (c - '0') + carry;
        buffer[i] = (d % 10) + '0';
        carry = d / 10;
        i++;
    }

    if (carry > 0)
        buffer[i++] = (carry % 10) + '0';

    buffer[i] = '\0';
    strncpy(decimal, buffer, 256);
}

void reverse(char * str)
{
    int i = 0;
    int j = strlen(str) - 1;

    while (j > i)
    {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;

        i++;
        j--;
    }
}

int main(void)
{
    char decimal[256] = "1";
    int i;

    for (i = 0; i < 100; i++)
        doubleDecimal(decimal);

    reverse(decimal);
    printf("%s", decimal);

    return 0;
}

Output:

1267650600228229401496703205376

Detrition

strncpy is almost always the wrong tool (it is here), and should never ever be suggested to beginners. – Bacillary

@Jim perhaps you could suggest the correct function for copying one string to another? – Detrition

strcpy is fine here ... if you stored more than 256 bytes in buffer you've already got undefined behavior. Generally, if you want safe string copies and you want to use a standard C library routine, snprintf works. Myself, I have my own library that takes care of this deficiency. But strncpy is wrong wrong wrong because a) it NUL-fills pointlessly and this can be detectably costly with large arrays and loops and b) it doesn't NUL-terminate the result. – Bacillary

@Jim thanks, you prompted me to do some research about the behaviour of strncpy. You are correct to say that strcpy is fine for the range of integers we are dealing with (max 2^256). – Detrition

What happened to "give the man a fish". Was it really so good an idea to do the person's homework for him? – Ertha

Answer 2

I think it's easiest if you work in base 10 from the start. This is because while calculating powers of 2 in binary is trivial, the conversion back to base 10 is a lot harder.

If you have an array of base 10 digits¹, you only need to implement base 10 addition with carry to be able to multiply by 2 (by adding the number to itself). Do that n times in a loop and you have your answer.

If you wish to support higher exponents, you can also look into implementing exponentiation by squaring, but that's harder, since you'll need general multiplication, not just by 2 for that.

_{¹ Tip: It's more convenient if you store the digits in reverse order.}

Idiosyncrasy

I'm glad someone gave an intelligent answer. It's amazing how few people can manage to think clearly about problem solving ... they know about bits and can't manage to think past them. – Bacillary

small endian base 10 numbering, I like it! – Rebuff

@annoying_squid: No, either way the entire work is base conversion. – Halloween

By the way, multiplying by 2 at each step is rather inefficient. I would multiply by 536870912 at each step (the largest power of 2 smaller than the largest power of 10 that fits in a 32-bit integer) and work base-1000000000 rather than base-10. – Halloween

Answer 3

double is a (probably) 64bit value. You can't store 256 bits of precision in 64 bits. The reason that you are getting a number that is sort of close is because floating point numbers are stored with varying precision -- not all sequential numbers can be represented, but you can represent very large numbers. Pretty useless in this case. What you want is either to use an arbitrary precision library or, since this is probably homework, you are expected to write your own.

Ombudsman

How about using arrays? The problem is implementing them properly. – Xanthic

@Xanthic yes, you can do it with arrays. That would be "rolling your own" bigint library. – Ombudsman

@MK.Oh c'mon. Eavery schoolkid learned how to add by hand. All that's called for here is repeatedly doubling a number ... do it with a char array of ASCII digits. – Bacillary

@JimBalter that's exactly what bigint library does. – Ombudsman

@Ombudsman Uh, no, it isn't. First, it handles a lot of other operations aside from doubling. Second, no decent bigint library uses char arrays of ASCII digits. – Bacillary

Actually, it shouldn't be ASCII chars, because they're harder to add. It should be bytes holding values from 0-9. That's a base 10 solution, whereas MP libraries normally use base 10^n for the largest such base that fits in an int (or other fast native integer type). – Bacillary

Bytes or ASCII digits should perform about the same. Subtracting a bias of '0' when adding adds something like 0-5% time to the runtime (likely 0 on archs like x86 with compound arithmetic instructions). – Halloween

Answer 4

A typical double, using 64-bit IEEE 754, has about 51 bits precision, IIRC.

Most probably the point of supporting exponents up to 256 is to exceed that precision, and also the precision of a long double or long long, so that you have to do things yourself.

As a homework exercise, then,

• Store decimal digit values in an array + a digit count
• Implement doubling of the value in such array + count
• Start with 1 and double value appropriate number of times.

Ertha

Answer 5

A few things you'll want to think about to solve this:

1. You are only dealing with integers so you should use an integer representation (you will need to roll your own because you can't use long long which is "only" 64 bits long).
2. Powers of 2 you say -how convenient - computers store numbers using powers of 2 (you'll only need to use shift operations and bit fiddling .... no multiplications will be needed).
3. How can you convert a base 2 number to a base 10 number for display purposes (think of division and outputting one number at a time (think about what a hardware divisor does in order to get the bit manipulations correct).

Rebuff

care to elaborate? How do you magically convert binary to decimal? – Ombudsman

magically converting from binary to decimal isn't so difficult (okay we might have to implement some arithmetic operators for our type); it's a first year university assignment. – Rebuff

dave, you're completely missing the point. To convert to decimal requires division and mod 10 of your multiword binary number ... a binary number that is itself pointless because it only holds a single 1 bit. Yes it's not magic, but the conversion is the whole problem. – Bacillary

@JimBalter: how am I missing the point, have a look at step 3 - think about hardware division. It can be done. I wasn't trying to solve the problem for him just giving him a way to get the solution (it's better than using double, but not as good as hammar's). – Rebuff

I explained exactly how you're completely missing the point. "It can be done" -- I just SAID it's not magic, didn't I? "it's better than using double" -- yes, because using double doesn't work at all, but this is the completely wrong approach. – Bacillary

P.S. Take a look at #1686504 ... note the answer. – Bacillary

@Araarab Why are chars better than ints? – Egerton

@Egerton Because you can store an arbitrary number of bits in one null terminated character array which you can reference with a pointer. There are many functions that already work like this and you don't need to keep track of the size of the array. – Araarab

In this specific case, if you don't need to worry about using every bit (there will be some storage "waste") you can even keep the numbers that you store this way directly readable. I.E. the number 1,234,567,890 would be stored as a character array of "1234567890" and your math routines work on individual characters instead of bytes. Now you can multiple two "numbers" together using basic grade school math techniques (especially when multiplying by a dingle digit number like 2). – Araarab

Answer 6

You can't the store 256 bits of precision in 64 bits. Reason that you are getting a number to close is because floating point numbers are stored with varying precision. To all sequential numbers can be represented, but you can represent very large numbers. Pretty useless in this case.

Guggenheim

Answer 7

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//constants
#define MAX_DIGITS 1000

//big integer number struct
struct bigint {
  char Digits[MAX_DIGITS];
};

//assign a value
void assign(struct bigint* Number,int Value) {
  if (Value!=1) {
    printf("Can not assign value other than 1\n");
    exit(0);
  }
  memset(Number,0,sizeof(bigint));
  Number->Digits[0] = Value;
}

//multiply the big integer number with value
void multiply(struct bigint* Number,int Value) {
  int Digit,New_Digit;
  int Carry = 0;

  for (int Index=0; Index<MAX_DIGITS; Index++) {
    Digit     = Number->Digits[Index];
    New_Digit = Digit*Value%10;
    if (New_Digit+Carry<10) {
      New_Digit = New_Digit+Carry;
      Carry     = Digit*Value/10;
    }
    else {
      New_Digit = (New_Digit+Carry)%10;
      Carry     = (Digit*Value/10)+1;
    }

    //set the new digit
    Number->Digits[Index] = New_Digit;
  }//for loop
}

//print out the value of big integer type
void print(struct bigint* Number) {
  int Index = MAX_DIGITS-1;
  while (Number->Digits[Index]==0 && Index>=0)
    Index--;

  //the big integer value is zero
  if (Index==-1) {
    printf("0");
    return;
  }

  while (Index>=0) {
    printf("%u",Number->Digits[Index]);
    Index--;
  }
}

//main programme entry point
int main(int Argc,char** Args) {
  int Power = 100;
  struct bigint Number;

  //assign the initial value
  assign(&Number,1);

  //do the multiplication
  for (int Index=0; Index<Power; Index++)
    multiply(&Number,2);

  //print result
  print(&Number);
  getch();
}

//END-OF-FILE

Gereld