how to find 2 to the power of n . n ranges from 0 to 200

Question

Assume my system as 32 bit machine. Considering this if I use long int for n>63 I will get my value as 0. How to solve it?

Answer 1

Just wait around for a 256-bit compiler, then use int :-)

No, seriously, since you just want to start with 1 and keep doubling, your best bet is to get a big integer library like GNU MP.

---

You would do that with a piece of code like (untested):

#include <stdio.h>
#include "gmp.h"

int main (void) {
    int i;
    mpz_t num;

    mpz_init_set_ui (num, 1);
    for (i = 0; i <= 200; i++) {
        printf ("2^%d = ", i);
        mpz_out_str (NULL, 10, num);
        printf ("\n");
        mpz_mul_ui (num, num, 2);
    }

    return 0;
}

---

You could code up your own data structure of an array of longs with only two operations, double and print but I think it would be far easier to just use GMP.

If you do want to roll your own, have a look at this. It's a variation/simplification of some big integer libraries I've developed in the past:

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

// Use 16-bit integer for maximum portability. You could adjust
//   these values for larger (or smaller) data types. SZ is the
//   number of segments in a number, ROLLOVER is the maximum
//   value of a segment plus one (need to be less than the
//   maximum value of your datatype divided by two. WIDTH is
//   the width for printing (number of "0" characters in
//   ROLLOVER).

#define SZ 20
#define ROLLOVER 10000
#define WIDTH 4
typedef struct {
    int data[SZ];
} tNum;

 

// Create a number based on an integer. It allocates the segments
//   then initialises all to zero except the last - that one is
//   set to the passed-in integer.

static tNum *tNumCreate (int val) {
    int i;

    tNum *num = malloc (sizeof (tNum));
    if (num == NULL) {
        printf ("MEMORY ERROR\n");
        exit (1);
    }

    for (i = 0; i < SZ - 1; i++) {
        num->data[i] = 0;
    }
    num->data[SZ-1] = val;
}

// Destroy the number. Simple free operation.

static void tNumDestroy (tNum *num) {
    free (num);
}

 

// Print the number. Ignores segments until the first non-zero
//   one then prints it normally. All following segments are
//   padded with zeros on the left to ensure number is correct.
//   If no segments were printed, the number is zero so we just
//   output "0". Then, no matter what, we output newline.

static void tNumPrint (tNum *num) {
    int i, first;
    for (first = 1, i = 0; i < SZ; i++) {
        if (first) {
            if (num->data[i] != 0) {
                printf ("%d", num->data[i]);
                first = 0;
            }
        } else {
            printf ("%0*d", WIDTH, num->data[i]);
        }
    }
    if (first) {
        printf ("0");
    }
    printf ("\n");
}

 

// Double a number. Simplified form of add with carry. Carry is
//   initialised to zero then we work with the segments from right
//   to left. We double each one and add the current carry. If
//   there's overflow, we adjust for it and set carry to 1, else
//   carry is set to 0. If there's carry at the end, then we have
//   arithmetic overflow.

static void tNumDouble (tNum *num) {
    int i, carry;
    for (carry = 0, i = SZ - 1; i >= 0; i--) {
        num->data[i] = num->data[i] * 2 + carry;
        if (num->data[i] >= ROLLOVER) {
            num->data[i] -= ROLLOVER;
            carry = 1;
        } else {
            carry = 0;
        }
    }
    if (carry == 1) {
        printf ("OVERFLOW ERROR\n");
        exit (1);
    }
}

 

// Test program to output all powers of 2^n where n is in
//   the range 0 to 200 inclusive.

int main (void) {
    int i;
    tNum *num = tNumCreate (1);
    printf ("2^  0 = ");
    tNumPrint (num);
    for (i = 1; i <= 200; i++) {
        tNumDouble (num);
        printf ("2^%3d = ", i);
        tNumPrint (num);
    }
    tNumDestroy (num);
    return 0;
}

and its associated output:

2^  0 = 1
2^  1 = 2
2^  2 = 4
2^  3 = 8
2^  4 = 16
2^  5 = 32
2^  6 = 64
2^  7 = 128
2^  8 = 256
2^  9 = 512
: : : : :
2^191 = 3138550867693340381917894711603833208051177722232017256448
2^192 = 6277101735386680763835789423207666416102355444464034512896
2^193 = 12554203470773361527671578846415332832204710888928069025792
2^194 = 25108406941546723055343157692830665664409421777856138051584
2^195 = 50216813883093446110686315385661331328818843555712276103168
2^196 = 100433627766186892221372630771322662657637687111424552206336
2^197 = 200867255532373784442745261542645325315275374222849104412672
2^198 = 401734511064747568885490523085290650630550748445698208825344
2^199 = 803469022129495137770981046170581301261101496891396417650688
2^200 = 1606938044258990275541962092341162602522202993782792835301376

Answer 2

If unsigned long int is 64 bits then the largest value for 2^n that you can represent is 2^63 (i.e. n = 63):

unsigned long int x = (1UL << n); // n = 0..63

Answer 3

It's been ages since I've used Java seriously, but: BigInteger class? It has all the usual mathematical (multiply, pow) and bitwise (shiftLeft) operations.

Your tagging is a little confusing though, which language did you prefer?

Answer 4

In C/C++ I don't know of a standard way you can store integers that big, pax's solution is the rightway to go.

However for Java, you do have a way out, BigInteger

Answer 5

Use java.math.BigInteger.shiftLeft.

    for (int i = 0; i <= 200; i++) {
        System.out.format("%d = %s%n", i, BigInteger.ONE.shiftLeft(i));
    }

Excerpt of output:

0 = 1
1 = 2
2 = 4
3 = 8
4 = 16
:
197 = 200867255532373784442745261542645325315275374222849104412672
198 = 401734511064747568885490523085290650630550748445698208825344
199 = 803469022129495137770981046170581301261101496891396417650688
200 = 1606938044258990275541962092341162602522202993782792835301376

If BigInteger is unavailable, you can also just manually do the multiplication and store it in a String.

    String s = "1";
    for (int i = 0; i < 200; i++) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (char ch : s.toCharArray()) {
            int d = Character.digit(ch, 10) * 2 + carry;
            sb.append(d % 10);
            carry = d / 10;
        }
        if (carry != 0) sb.append(carry);
        s = sb.toString();
        System.out.format("%d = %s%n", i + 1, sb.reverse());
    }

(see full output)

Answer 6

python supports big integers out of the box. At any linux prompt, run this:

$ python -c "for power in range(201): print power, 2**power"
0 1
1 2
2 4
3 8
4 16
5 32
6 64
<snip>
196 100433627766186892221372630771322662657637687111424552206336
197 200867255532373784442745261542645325315275374222849104412672
198 401734511064747568885490523085290650630550748445698208825344
199 803469022129495137770981046170581301261101496891396417650688
200 1606938044258990275541962092341162602522202993782792835301376

This can be easily made into a script if necessary. See any python tutorial.

Answer 7

double is perfectly capable of storing powers of two up to 1023 exactly. Don't let someone tell you that floating point numbers are somehow always inexact. This is a special case where they aren't!

double x = 1.0;
for (int n = 0; n <= 200; ++n)
{
    printf("2^%d = %.0f\n", n, x);
    x *= 2.0;
}

Some output of the program:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
...
2^196 = 100433627766186892221372630771322662657637687111424552206336
2^197 = 200867255532373784442745261542645325315275374222849104412672
2^198 = 401734511064747568885490523085290650630550748445698208825344
2^199 = 803469022129495137770981046170581301261101496891396417650688
2^200 = 1606938044258990275541962092341162602522202993782792835301376

Answer 8

Use scheme!

1 => (expt 2 200)
1606938044258990275541962092341162602522202993782792835301376