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?

Answer 1

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.}

Answer 2

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

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.

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.

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

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.

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