operator

[Amon Ra]

how could i translate this

    For temp = 1 To 8
        send(temp) = 2 ^ (temp - 1)
    Next temp

into C++...what is the ^ in C++, for the powers?
Thanks

[parksie]

#include <cmath>

void somecode() {
    for(temp = 0; temp < 8; temp++) {
        send[temp] = std::pow(2, temp);
    }
}

[Amon Ra]

thanks parksie..just figured it out...how woud i write my own pow function though?
thanks

[Amon Ra]

nevermind...i found a way...thanks again

[Amon Ra]

actually, could you give me an example, cuz you might have a better one

[Amon Ra]

i am trying to use a template

[kedaman]

integer powers?

[Amon Ra]

yup

[kedaman]

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

y=x;
for (;power; ){
 if (power & 1)
  y*=x*y;
 else
  y*=y;
  power >>1;
} 

haven't tested it yet though, but should work

[Amon Ra]

i am not sure what bit shiftings are for? i know they do something with the value, but i am not sure what...
in

int a=8;
a >> 2;

whats the point of doing this...what willl a end up being?
thanks a lot

[parksie]

int a = 8; // 1000 in binary

a = a >> 2; // Shift 2 places right = 0010 in binary, 2 in decimal :)

It's basically a quick way of doing power-of-2 multiplication/division.

[Amon Ra]

isn't there other ones like & and | ?
Thanks again

[parksie]

No, those are the masking operators (don't know what they should REALLY be called):

int x = 9; 1001
int y = 11; 1011

x & y = 1001;
x | y = 1011;

[kedaman]

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

[Amon Ra]

thanks a lot guys...it is a bit clearer now..

[Amon Ra]

so if i do

int i=1011;
int j=0001;
int n;

n = i & j;

n would be equal to 0001, right?

[kedaman]

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?

[kedaman]

Originally posted by Amon Ra
so if i do

int i=1011;
int j=0001;
int n;

n = i & j;

n would be equal to 0001, right?

yep, thats bitwise and

[Amon Ra]

ok cool..
ok look, this is what i have so far, using what you gave me...i must have messed up somewhere

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);
}

apparently when i run, it enters an infinite loop

[kedaman]

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

[Amon Ra]

yea i modified it to see if it would stop the loop, but doesn't...what's wrong?

[Amon Ra]

cuz when u put

for (; y;) {.....

isn't it normal that you have an endless loop?

[kedaman]

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;
} 

say you want to take the 10'th power of x
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

[kedaman]

Originally posted by Amon Ra
cuz when u put

for (; y;) {.....

isn't it normal that you have an endless loop?

not if y has a chance to get 0, in my case mask is bitshifted until all bits are 0

[Amon Ra]

ok thanks...i 'll try to put that in a function...thank you very much!
i appreciate...=)

[Amon Ra]

what should i return in my function?

[Amon Ra]

there, i got it...
thank you so much!

[Amon Ra]

here is the final function i am using..

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 a lot

[Amon Ra]

i think i read the function too many times, so i got confused

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 tried figurin out what each line does...do you mind telling me? the bitshifting part confuse me..
Thanks again

[Amon Ra]

great!! i got it! thank you very much guys
i apreciate

[MoMad]

To save all disasterous mischiefs and to rid of endless looops, please use a while loop rather than a for loop.

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;
}

that should be more stable

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

[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).

[kedaman]

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.

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.

that should be more stable

no, not really

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 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.

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

Why the heck would i do that? guess? No? I can see that you can't see the forest for the trees
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.

mask = mask >> 1; // same as mask = mask/2;

Why? Because I need to check next bit, for next recursion.

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.

[MoMad]

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.

[kedaman]

Yes, essentially a inlined data recursion, most recursions can and should be written inline to save performance

[MoMad]

I still dont get it man. Its a LOOP the function doesnt call itself. So im lost.

This is what i call recursion:

int recurse(int n) { if( --n > 0 ) recurse(n); return n; }

Not this:

int norecurse(int n) { while( --n > 0 ) continue; return n; }

Which, in both cases should return 0. What do u think kadaman?

[kedaman]

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

[MoMad]

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

[kedaman]

Hehe, actually I don't know what you should call it then, doesn't matter anyway