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?

Solution 1

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

Solution 2

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

Solution 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?

Solution 4

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.

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

View more solutions

Comments

[mousey]

If I want to do using my own data structure what is the procedure >

[mousey]

using strings or arrays we can represent more.

[Yuliy]

@mousey: that really depends on your data structure. Propose a data structure, and you might get some suggestions for that.

[Denis Tulskiy]

+1 With BigInteger it's one line of code: java.sun.com/j2se/1.4.2/docs/api/java/math/…

[polygenelubricants]

@mousey: see my solution using String.

[polygenelubricants]

pow is unneeded; shiftLeft is sufficient. See my answer.

[paxdiablo]

I believe this is what you need: stackoverflow.com/questions/2643487/… :-)

[AngryWhenHungry]

Instead of left-shifting BigInteger.ONE 'i' times in each iteration, is it more efficient to start off with a copy of BigInteger.ONE and left-shift it once per iteration?

[polygenelubricants]

@Angry: I was going for conciseness and readability over efficiencies, but I think for BigInteger shifting 1 bit k times may in fact be cheaper than shifting k-1 bits (most of which are zeroes) 1 time.

[AngryWhenHungry]

Your way is definitely more concise. Thanks for pointing out that in this context it is also more efficient. +1 : )

[polygenelubricants]

@Angry: Don't just take my words for it -- look at the benchmark! ideone.com/wIRln

[Potatoswatter]

How are you the only one to think of this? How did the others get so many votes??

[fredoverflow]

Well, my solution breaks for most other bases, so in that respect, it's definitely inferior to other solutions posted. Plus many people are scared of floating point numbers because they don't understand their internal representation.

[bta]

Great catch, FredOverflow. Since we only really need the most-significant bit and number of zeros following it, double works perfectly here.

[Mark Ransom]

Although the internal storage of the number is complete and exact, I don't think the conversion to decimal for printing is guaranteed to be exact. You got lucky.

[bukzor]

@Thorarin: I didn't see anything language-specific in the question. I'm just now seeing the tags with C/C++/Java, but that implies that he doesn't care too much about which language is used. Maybe I infer too much...

[Thom Smith]

This will work in ALMOST ALL cases, but technically, the C standard does not specify the internal representation of floating point values. Depending on the implementation, you could still get round-off errors. On common platforms, this will probably work.

[fredoverflow]

@Thom Right, I am assuming IEEE754 here.

[Potatoswatter]

IEEE 754-1985 §5.6: "When the integer … lies outside the range … 10^17 for double, the implementor may, at his option, alter all significant digits after … the seventeenth … to other decimal digits, typically 0." But that doesn't stop you from implementing your own perfectly precise decimal printer, presuming string conversion is even relevant to the problem. (Such would come full circle viz. finding powers, though.)

[fredoverflow]

@Potato But there are no significant digits after the 17th...?

[Potatoswatter]

@Fred: sorry, I was unclear… that paragraph is talking about printing numbers in decimal.

[Jonathan]

Welcome to Stackoverflow. Please explain your solution.