Power of N + Overcome Size Limitations

Hi, i am writing a program that asks the person for a number and then will out put that number by the power of 2. so 2 ^ 6 = 64. This program needes to be created without using the math functions all the maths have to be done programmaticaly.

i know i am prob wrong because i cant get anywhere with this program. here is the code so far.

Code:

#include <iostream> using namespace std; int power; int n; int counter; int main () { cout <<"Please enter a power number"; cin >> n; counter = 2; if(counter < n) { counter*2; } if(counter == n) { counter * n; } cout <<counter; system("pause"); }

the other problem i have is once i have the power to work i need to allow the program to overcome size limitations and show all the numbers. for example i need

Code:

2^200 = 1606938044258990275541962092341162602522202993782792835301376.

if anyone can help me with this then thanx soo much as i am finding this program hard to complete.

This will be a very hard problem for you*, because it seems as if you're a complete beginner. My advice is to study some example code and try to make some easier programs first, so you learn the basic concepts.

*) the last problem that is, the first one is quite easy. To solve the first one you should use a loop.

You need 2 variables - the counter, that you input, and a power variable, which will hold the output.

Edit: The second problem is much harder - you're trying to implement arbitrary-precision arithmetic.

You'll probably want to use a loop.

i have gone through all of the sheet on the basics n then this is the next question, lol. i am really stuck on it as you can prob tell.

can anyone give me any pointers on how to overcome the size limitations?

Quote:

Originally Posted by peckitt99

can anyone give me any pointers on how to overcome the size limitations?

If you're having trouble with the first part, then forget about the second part. It's orders of magnitude harder. I doubt if your instructor expected anyone to actually finish that part.

Edit: Actually, when I think about it, if the only arithmetic you have to implement is powers of 2, it's not nearly as bad as the general case. Don't get me wrong, it's still much harder than the first part, but still doable with some work. The general idea for arbitrary-precision arithmetic is that you represent numbers by strings instead of built-in numerical types, then implement by hand the rules of arithmetic you need, since the computer won't do it for you. I still strongly suggest you not think about it until after completing the first part.

not done the first part cause i cant seem to get it right for some reason.

i dont know about the size limitations and didnt know if it was that hard or what it involved.

HINT:

Inside your loop, you are going to need something like this:

x = x * 2; // Do this n times in a loop

Don't forget to initialize x before entering the loop.

A type unsigned long int will (probably) hold bigger numbers than a regular int. But, it's not going to hold 2^200 !!! :(

Quote:

Originally Posted by robatino

Edit: The second problem is much harder - you're trying to implement arbitrary-precision arithmetic.

It's trivially easy if you output the numbers in hexadecimal ;)

yeah, still trying to get the first bit done, just not happeneing, taking in all the advice but dont think i am implementing it in correctly because i dont get the right output etc.

Quote:

Originally Posted by Cat

It's trivially easy if you output the numbers in hexadecimal ;)

I don't know. You still have to break the string into blocks and handle the carries properly. Offhand it seems tricky.

A power of 2 in binary will only have a single bit set. In hex, you just need to modula 4 to tell if the first hex digit should be 1,2,4, or 8, then divide by 4 to tell how many zeroes should follow it.

E.g. 2^200 in hex is:

0x100000000000000000000000000000000000000000000000 000

That is how I personally would solve the problem (assuming they didn't explictly specify decimal answers) and bank on the grader finding it clever.

You're right. That's even easier than solving the first part using decimals - and of course the first part just falls out as a special case (assuming the grader buys it).

Edit: Actually, I'm thinking of binary. Well, if they buy base 16, why not 2?

at the moment i am still trying to calculate the power for the first bit.

am i right in using this to help work it out?

Code:

{ if (n == 0) // Base case return 1; else if (n > 0) // First general case return ( x * Power (x, n - 1)); else

That code looks to be a snipper from a recursive function, which calculates the x^n.

What it does is you call the first function, with 2^3 say.
It returns 2*2^2, then to work out 2^2 it calls the same function with that, so it returns 2*2^1, and that returns 2*2^0. 2^0 is then returned 1 by the special case, so it collapses to 2*(2*(2*(1))).

I would have just used a loop as I tend to prefer iterative over recursive solutions.

Code:

for(int n=0;n<power;n++) num *= 2;

I'm bored ;) here's a decimal power-of-2 using simple carry-add. Don't expect your grader to believe you wrote it yourself though.

Code:

#include <iostream> int main(){ int p=10,*d=new int[p],s=1,b,i,j,c,*t;*d=1; std::cout<<"Enter a number: "; std::cin>>b; for(i=0;c=0,i<b;++i){ for(j=0;j<s;++j){ j[d]+=j[d]+c; c=j[d]>9?1:0; j[d]-=j[d]>9?10:0; } if(c){ d[s++]=c; if(s==p){ t=new int[p<<=1]; for(j=0;j<s;++j)j[t]=j[d]; delete[]d,d=t; } } } std::cout<<"2^"<<b<<"\n"; for(i=s-1;i+1;--i)std::cout<<i[d]; return 0; }

It can do 2^100000 in 15~20 seconds. I could use binary splitting and Karatsuba/FFT, but hey this is a forum post. Perhaps you'll understand it someday.

Anyway, there is a shortcut. The << operator isn't only for cout. On integers, it shifts bits. (It's called the left shift operator.) Imagine that the number 19 is written in binary: 10011. What the left shift does is, it shifts all the bits left and adds a zero in the empty slot. So you get 100110 for (19 << 1), 1001100 for (19 << 2) and so on. So (2^X) == (1 << X). Have fun.

i have written more of the program and have come up with this using the shift command

Code:

#include <iostream> using namespace std; int main() { int power; int x = 2; int total; cout <<"enter a number"; cin >> power; total = (power) << (x); cout << total; system("pause"); }

when i do this it comes up with 24 or if i swtich the power and x the other way round i get 128.

can anyone let me know what i am doing wrong?

2^(power) = 1 << power. Also, you might want to make your total variable an unsigned type, like unsigned int or unsigned long, since that's what it is, and it increases the upper size limit of inputs that work (if power is too big, then the 1 bit falls off the high end and 1 << power suddenly becomes 0, not 2^(power) as intended).

Code:

total = 1 << (power);

But, lets' back-up a bit...

Quote:

...a program that asks the person for a number and then will out put that number by the power of 2...

The above means square the number (i.e. 6^2 = 6*6 = 36), which does not requre a loop, and is different from:

Quote:

...so 2 ^ 6 = 64.

Which I assume is the correct assignment (i.e. 2^6 = 2*2*2*2*2*2) = 64

I doubt this assignment is about bit-shifting. I'll bet you are studying loops. If you use bit shifting you are not going to get credit, and you are not going to learn about loops. And, if they give you a "power-of-3" problem on a test, you are not going to be able to solve it! (The bit shifting "trick" only works with powers of two.)

First, get it working without a loop...*

Code:

power = 0; // Initialize outside loop. (Don't need this 'till a loop is used.) result = 1; // X^0 always equals one cout<< "2^0 = " << result ; power++; // Needed later to keep track of the number of loops result = result * 2; // 1*2 = 2, 2^1 = 2 cout<< "2^1 = " << result << endl; power++; result = result * 2; // 2*2 = 4, 2^2 = 4 cout<< "2^2 = " << result << endl; power++; result = result * 2; // 4*2 = 8, 2^3 = 8 cout<< "2^3 = " << result << endl; power++; result = result * 2; // 8*2 = 16, 2^4 = 16 cout<< "2^4 = " << result << endl;

* That's always a good approach. Don't try to write the whole program at once. Write a few lines of code. Test-compile & test-run. Then add a few lines at a time test-compiling and test-running as you go.