how could i translate this
into C++...what is the ^ in C++, for the powers?Code:For temp = 1 To 8
send(temp) = 2 ^ (temp - 1)
Next temp
Thanks
Printable View
how could i translate this
into C++...what is the ^ in C++, for the powers?Code:For temp = 1 To 8
send(temp) = 2 ^ (temp - 1)
Next temp
Thanks
Code:#include <cmath>
void somecode() {
for(temp = 0; temp < 8; temp++) {
send[temp] = std::pow(2, temp);
}
}
thanks parksie..just figured it out...how woud i write my own pow function though?
thanks
nevermind...i found a way...thanks again
actually, could you give me an example, cuz you might have a better one
i am trying to use a template
integer powers?
yup
i know an algoritm that will do it with log2(power) multiplications and bitshifts
was trying to write some pseudo for it but ended up writing the whole thing :p
haven't tested it yet though, but should workPHP Code:y=x;
for (;power; ){
if (power & 1)
y*=x*y;
else
y*=y;
power >>1;
}
i am not sure what bit shiftings are for? i know they do something with the value, but i am not sure what...
in
whats the point of doing this...what willl a end up being?Code:int a=8;
a >> 2;
thanks a lot
It's basically a quick way of doing power-of-2 multiplication/division.Code:int a = 8; // 1000 in binary
a = a >> 2; // Shift 2 places right = 0010 in binary, 2 in decimal :)
isn't there other ones like & and | ?
Thanks again
No, those are the masking operators (don't know what they should REALLY be called)::)Code:int x = 9; 1001
int y = 11; 1011
x & y = 1001;
x | y = 1011;
bit shifting shifts bits, so as a number is stored binary, if you shift n bits right the result will be the same as integer division with 2^n
the code doesn't work, when i explore it to show an example for you, the bit reading needs to be reversed, so i'll be right back
thanks a lot guys...it is a bit clearer now.. :)
so if i do
n would be equal to 0001, right?Code:int i=1011;
int j=0001;
int n;
n = i & j;
parksie, isn't there an ASM instruction to get the integer log2 of a value, that is the highest set bit?
or can you reverse the bits somehow?
yep, thats bitwise andQuote:
Originally posted by Amon Ra
so if i do
n would be equal to 0001, right?Code:int i=1011;
int j=0001;
int n;
n = i & j;
ok cool..
ok look, this is what i have so far, using what you gave me...i must have messed up somewhere
apparently when i run, it enters an infinite loopCode:template<class PA> inline
PA ipow(PA x, int y) {
int i = x;
for (int z=0 ; z < (y +1); ) {
if (y &1)
i *= x*i;
else
i *= i;
}
return (i);
}
well you modified it pretty much, anyways, the algoritm is the other way around, that is left to right not right to left bit reading
yea i modified it to see if it would stop the loop, but doesn't...what's wrong?
cuz when u put
isn't it normal that you have an endless loop?Code:for (; y;) {.....
say you want to take the 10'th power of xPHP Code:if (power){
mask=256;//or higher max power
for(;!(mask&power);mask>>1); // or something that finds the highest set bit
y=x;
mask>>1;
for (;mask; ){
if (mask&power)
y*=x*y;
else
y*=y;
mask>>1;
}
else
y=1;
}
10 is 1010 binary
4'th bit is 1: y=x
3'rd bit is 0: y=x*x
2'nd bit is 1: y=(x*x)*(x*x)*x
1'th bit is 0: y=((x*x)*(x*x)*x)*((x*x)*(x*x)*x)
analoguous with
y=x^10=x^5^2=(x^2*2)^2
not if y has a chance to get 0, in my case mask is bitshifted until all bits are 0Quote:
Originally posted by Amon Ra
cuz when u put
isn't it normal that you have an endless loop?Code:for (; y;) {.....
ok thanks...i 'll try to put that in a function...thank you very much!
i appreciate...=)
what should i return in my function?
there, i got it... :)
thank you so much!
here is the final function i am using..
thanks a lot :)Code:template<class PA> inline
PA ipow(PA x, int y) {
int mask=256, ret;
if (y) {
for (; !(mask & y); mask >>=1);
ret = x;
mask = mask >> 1;
for(;mask;) {
if (mask & y)
ret *= x*ret;
else
ret *= ret;
mask = mask >>1;
}
}
else
ret = 1;
return ret;
}
i think i read the function too many times, so i got confused :)
i tried figurin out what each line does...do you mind telling me? the bitshifting part confuse me..Code:template<class PA> inline
PA ipow(PA x, int y) {
int mask=256, ret;
if (y) {
for (; !(mask & y); mask >>=1);
ret = x;
mask = mask >> 1;
for(;mask {
if (mask & y)
ret *= x*ret;
else
ret *= ret;
mask = mask >>1;
}
}
else
ret = 1;
return ret;
}
Thanks again
great!! i got it! thank you very much guys :)
i apreciate
To save all disasterous mischiefs and to rid of endless looops, please use a while loop rather than a for loop.
that should be more stable :)Code:template<class PA> inline
PA ipow(PA x, int y) {
int mask=256, ret;
if (y) {
for (; !(mask & y); mask >>=1)
continue; // dont forget this...
// or
// while( !(mask&y) ) mask >>= 1;
ret = x;
mask = mask >> 1; // or mask >>= 1;
while(mask) {
if (mask & y)
ret *= x*ret;
else
ret *= ret;
mask = mask >>1; // or mask >>= 1;
}
}
else
ret = 1;
return ret;
}
What each line does:
first:
int mask=256;
int ret;
that declares 2 variables. mask that is 256 (0001 0000 0000, 0x100)
then you have:
if(y)
that means if (y != 0 && y != false && y != NULL ) basically it means that y exists and y doesnt equal 0.
the first for loop which is kind of fruity looking just does the following:
if mask and y "not equal to 0" then (basically keep dividing by 2 as long as mask and y are not the same)
ret = x; // duh!! set ret to equal x
mask = mask >> 1; // same as mask = mask/2;
then u have another fruity for loop, i prefer a while loop since it looks much clearer and its better suited for the loop itslef.
while(mask) "loop while mask <> 0"
if mask and y then
ret = ret * x * ret; // note: x *= y is the same as x=x*y;
else
ret = ret * ret;
end if
mask = mask / 2;
last but not least, if y was originally 0, just return 1.
thats about it. I hope you found this usefull.
BTW: the function is a template which means that it can be used for int, float, double, long, short, etc... and also, the word inline tells the compiler to compile this function everywhere that it sees the call of the function ipow(somevalue, thepower);. this is done to make the pow function as fast as possible.
-MoMad
Furthermore, Take a look at:
Arithmatic Operators in C++
- http://library.thinkquest.org/~C0111...ual.php?tid=16
- http://www.cplusplus.com/doc/papers/boolean.html
- http://www.cplusplus.com/doc/papers/hex.html
- http://www.cplusplus.com/doc/tutorial/tut1-3.html
The function itself can be simplified much more but the biggest reason ppl use C++ is that extra push of speed and efficiency so doing: mask = mask / 2; is not as fast as mask >>= 1; bitwise operators are extremly fast because all they do is take a look at the binary number and do a fast "switching" of bits (on/off).
Doesn't matter if you use a while of a for, the middle statement will be identical in the while statement. It's a qwestions of taste actually, because anything you can do with while, you can do with for, and vice versa.Quote:
Originally posted by MoMad
[B]To save all disasterous mischiefs and to rid of endless looops, please use a while loop rather than a for loop.
no, not really ;)Quote:
that should be more stable :)
Why would anyone need to know that? The reason I tested the base, was that X^0 is 1 for all X!=0. In other cases the solution had to be retrieved iteratively with multiplications.Quote:
then you have:
if(y)
that means if (y != 0 && y != false && y != NULL ) basically it means that y exists and y doesnt equal 0.
Why the heck would i do that? guess? No? I can see that you can't see the forest for the trees :)Quote:
the first for loop which is kind of fruity looking just does the following:
if mask and y "not equal to 0" then (basically keep dividing by 2 as long as mask and y are not the same)
ret = x; // duh!! set ret to equal x
Actual Reasons: I want to find first set bit and for the second at least one factor x is used, the set bit indicating 1 gives y*=y*x giving x. For each odd bit the additional factor x is included in the recursion to compensate the amount of factors.
Why? Because I need to check next bit, for next recursion.Quote:
mask = mask >> 1; // same as mask = mask/2;
Does anyone know what i'm trying to achieve here?
The algoritms obvious goal is to minimize the amount of multiplications on a power. A regular recursive multiplication would take n-1 multiplications for power of n, this algoritm reduces it to log2(n).
Say we have X^68
it could be written as
X^34^2
and further
X^17^2^2
(X^16*X)^2^2
(X^8^2*X)^2^2
(X^4^2^2*X)^2^2
(X^2^2^2^2*X)^2^2
notice the extra *X in there, that got there to compensate the odd value 17. If you take a look at the binary equivalent of 68:
1000100
you notice it's the 5'th from left, 3'rd from right, and when you look at:
(X^2^2^2^2*X)^2^2
the extra *X is at 5'th from left and 3'rd from right. Since the recursions goes from left to right, as you obviously need to start with the first X, the algoritms will start from the most significant bit as well, as it will be most significant in the recursion as a factor.
Ahh, I see what u mean. But why do u keep talking about recursion, do you mean the loop? I dont see any recursions here, just nested loop.
Yes, essentially a inlined data recursion, most recursions can and should be written inline to save performance :)
I still dont get it man. Its a LOOP the function doesnt call itself. So im lost.
This is what i call recursion:
Not this:Code:int recurse(int n) { if( --n > 0 ) recurse(n); return n; }
Which, in both cases should return 0. What do u think kadaman?Code:int norecurse(int n) { while( --n > 0 ) continue; return n; }
It is two implementations of the same algoritm, actually I have to agree with you, the first implementation is recursive while in the second the recursion is inlined to to a iterative solution.
However I still think you can still talk about recursive algoritms, and the implementations of them as iterative :)
Ooohhh I see, so in iterating, you hope to save stack flow.
Hmm, you're right about every recursive problem being able to be reduced to an iteration... but the whole point of using recursion is to show off how complicated you can make the simplest problem right??> lol... j/k. Yeah, I totally have to agree with you there.
So again, you said something to throw me off... "the recursion is inlined"????? Whats that supposed to mean, that the recursion is in a form of a loop? Oh well, i guess we'll be on the same page for now :D
Hehe, actually I don't know what you should call it then, doesn't matter anyway :D