Power of N + Overcome Size Limitations

This is a discussion on Power of N + Overcome Size Limitations within the C++ Programming forums, part of the General Programming Boards category; That code looks to be a snipper from a recursive function, which calculates the x^n. What it does is you ...

  1. #16
    Cat Lover
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    109
    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;

  2. #17
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Last edited by jafet; 10-17-2006 at 08:52 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  3. #18
    Is Trying to Learn
    Join Date
    Mar 2006
    Location
    Hutton, Preston
    Posts
    215
    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?

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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).

  5. #20
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    Code:
    total = 1  << (power);

    But, lets' back-up a bit...
    ...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:

    ...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.
    Last edited by DougDbug; 10-17-2006 at 02:50 PM.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapsort
    By xENGINEERx in forum C Programming
    Replies: 2
    Last Post: 03-30-2008, 08:17 PM
  2. Invalid conversion from 'void*' to 'BYTE' help
    By bikr692002 in forum C++ Programming
    Replies: 9
    Last Post: 02-22-2006, 11:27 AM
  3. An exercise in optimization
    By Prelude in forum Contests Board
    Replies: 10
    Last Post: 04-29-2005, 04:06 PM
  4. File Size and File Size on Disk
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 12-15-2001, 08:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21