I have a problem where I have to do left shift and right shift.

Long N;
int shiftby;

output = N >> shiftby;

Above N is shifted right.

Example if N=11101101 [binary value]

will become: 1110110 when shiftby=1;
will become: 0111011 when shiftby=2;
will become: 0011101 when shiftby=3;
will become: 0001110 when shiftby=4;
will become: 0000111 when shiftby=5;
will become: 0000011 when shiftby=6;
will become: 0000001 when shiftby=7;


When I want to shift left I can use

output = N << shiftby; //[Not change in sign "<<" instead of ">>"]

Above N is shifted left.

Example if N=11101101 [binary value]

will become: 111011010 when shiftby=1;
will become: 1110110100 when shiftby=2;
will become: 11101101000 when shiftby=3;
will become: 111011010000 when shiftby=4;
will become: 1110110100000 when shiftby=5;
will become: 11101101000000 when shiftby=6;
will become: 111011010000000 when shiftby=7;



I have to use use left shift and right shift to shift Number right/
left depending on value of shiftby

if (shift>0) output = N >> shiftby; else output = N << (-shiftby);//
working but inefficient.

I am using above shift operator many times.

I want to get rid of the if then else condition.

As If condition takes a lot of time.

I want something like

output = N >> shiftby; where N is shifted left / right automatically
if shiftby is -ve then shift left otherwise shift right.

I tried using below function

divider=2^shiftby; //<<=== Is it not 2*2* ... shiftby times????
math.pow() can also be used
output = N * divider;// automatically shifts left right depending on
value of divider
But this seems not to work.

math.pow() is again time consuming function. Can I use it? how much
faster is math.pow() function compared to if conditions?

Is there any way to avoid the if condition and do right shift and left
shift using operators depending on shiftby is +ve or -ve?

Bye
Sanny

Java Experts needed

http://www.GetClub.com/Experts.php

[Lots of coding jobs to choose]

Sanny wrote:

> I have a problem where I have to do left shift and right shift.
> 
[...]
> 
> I have to use use left shift and right shift to shift Number right/
> left depending on value of shiftby
> 
> if (shift>0) output = N >> shiftby; else output = N << (-shiftby);//
> working but inefficient.

In what way is it inefficient? Have you performed measurements
or do you simply think that it's slow and want to optimize
it prematurely?


Regards, Lothar
-- 
Lothar Kimmeringer                E-Mail: spamfang@kimmeringer.de
               PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
                 questions!

> Is there any way to avoid the if condition and do right shift and left
> shift using operators depending on shiftby is +ve or -ve?

I used below technique but it gives error.

divider=Math.pow(2,shiftby);
then
output = (long) N / divider;

This works for most cases but failed when output is greater than
9223372036854775807


N="9223372036854775807"; and shift by (-3);

long output=(long)(9223372036854775807 / 0.125);

The answer is "-1";

binary Value:
111111111111111111111111111111111111111111111111111111111111111

While correct answer is :
1000000000000000000000000000000000000000000000000000000000000000

It is because "long" is 64 bit signed variable. Can I get unsigned
Long?

Or bigger than long variable? So that 64 bit shifts can be done
easily?

Bye
Sanny

Java Experts needed

http://www.GetClub.com/Experts.php

[Lots of coding jobs to choose]

On 4/26/2011 12:55 AM, Lothar Kimmeringer wrote:
> Sanny wrote:
>
>> I have a problem where I have to do left shift and right shift.
>>
> [...]
>>
>> I have to use use left shift and right shift to shift Number right/
>> left depending on value of shiftby
>>
>> if (shift>0) output = N>>  shiftby; else output = N<<  (-shiftby);//
>> working but inefficient.
>
> In what way is it inefficient? Have you performed measurements
> or do you simply think that it's slow and want to optimize
> it prematurely?

It is very important that the measurement be done in context, using the
pattern of left and right shifts that occur in the real program. The
very worst possible case is the one that many people might use in a test
program, a random, equal probability, mix of left and right shifts. That
makes the hardware branch prediction no better than random.

Patricia

On 4/26/2011 5:04 AM, Sanny wrote:
>> Is there any way to avoid the if condition and do right shift and left
>> shift using operators depending on shiftby is +ve or -ve?
>
> I used below technique but it gives error.
>
> divider=Math.pow(2,shiftby);
> then
> output = (long) N / divider;

     Let me get this straight: You're worried about the inefficiency
of an `if' that chooses between a left or a right shift, so you plan
to eliminate the `if' by evaluating an exponential function?

     ARE YOU OUT OF YOUR MIND?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

On 04/26/2011 03:38 AM, Sanny wrote:
> divider=2^shiftby; //<<=== Is it not 2*2* ... shiftby times????
  the `^' here is the XOR operator, not an exponentiation operator.

> math.pow() is again time consuming function. Can I use it? how much
> faster is math.pow() function compared to if conditions?

Math.pow is S - L - O - W compared to an if and a shift. Barrel shifting 
can be done in the same amount of time as integer addition (circuit 
depth is both  O(lg N) in both cases), while Math.pow is a function that 
works with floating point (typically slower than integer math anyways), 
has lower precision (53 bits for double, 63 bits for long), and requires 
a lot more computation. This is a listing I have for the implementation 
of Math.pow, courtesy of OpenJDK:

double __ieee754_pow(double x, double y)
{
         double z,ax,z_h,z_l,p_h,p_l;
         double y1,t1,t2,r,s,t,u,v,w;
         int i0,i1,i,j,k,yisint,n;
         int hx,hy,ix,iy;
         unsigned lx,ly;

         i0 = ((*(int*)&one)>>29)^1; i1=1-i0;
         hx = __HI(x); lx = __LO(x);
         hy = __HI(y); ly = __LO(y);
         ix = hx&0x7fffffff;  iy = hy&0x7fffffff;

     /* y==zero: x**0 = 1 */
         if((iy|ly)==0) return one;

     /* +-NaN return x+y */
         if(ix > 0x7ff00000 || ((ix==0x7ff00000)&&(lx!=0)) ||
            iy > 0x7ff00000 || ((iy==0x7ff00000)&&(ly!=0)))
                 return x+y;

     /* determine if y is an odd int when x < 0
      * yisint = 0       ... y is not an integer
      * yisint = 1       ... y is an odd int
      * yisint = 2       ... y is an even int
      */
         yisint  = 0;
         if(hx<0) {
             if(iy>=0x43400000) yisint = 2; /* even integer y */
             else if(iy>=0x3ff00000) {
                 k = (iy>>20)-0x3ff;        /* exponent */
                 if(k>20) {
                     j = ly>>(52-k);
                     if((j<<(52-k))==ly) yisint = 2-(j&1);
                 } else if(ly==0) {
                     j = iy>>(20-k);
                     if((j<<(20-k))==iy) yisint = 2-(j&1);
                 }
             }
         }

     /* special value of y */
         if(ly==0) {
             if (iy==0x7ff00000) {       /* y is +-inf */
                 if(((ix-0x3ff00000)|lx)==0)
                     return  y - y;      /* inf**+-1 is NaN */
                 else if (ix >= 0x3ff00000)/* (|x|>1)**+-inf = inf,0 */
                     return (hy>=0)? y: zero;
                 else                    /* (|x|<1)**-,+inf = inf,0 */
                     return (hy<0)?-y: zero;
             }
             if(iy==0x3ff00000) {        /* y is  +-1 */
                 if(hy<0) return one/x; else return x;
             }
             if(hy==0x40000000) return x*x; /* y is  2 */
             if(hy==0x3fe00000) {        /* y is  0.5 */
                 if(hx>=0)       /* x >= +0 */
                 return sqrt(x);
             }
         }

         ax   = fabs(x);
     /* special value of x */
         if(lx==0) {
             if(ix==0x7ff00000||ix==0||ix==0x3ff00000){
                 z = ax;                 /*x is +-0,+-inf,+-1*/
                 if(hy<0) z = one/z;     /* z = (1/|x|) */
                 if(hx<0) {
                     if(((ix-0x3ff00000)|yisint)==0) {
                         z = (z-z)/(z-z); /* (-1)**non-int is NaN */
                     } else if(yisint==1)
                         z = -1.0*z;             /* (x<0)**odd = 
-(|x|**odd) */
                 }
                 return z;
             }
         }

         n = (hx>>31)+1;

     /* (x<0)**(non-int) is NaN */
         if((n|yisint)==0) return (x-x)/(x-x);

         s = one; /* s (sign of result -ve**odd) = -1 else = 1 */
         if((n|(yisint-1))==0) s = -one;/* (-ve)**(odd int) */

     /* |y| is huge */
         if(iy>0x41e00000) { /* if |y| > 2**31 */
             if(iy>0x43f00000){  /* if |y| > 2**64, must o/uflow */
                 if(ix<=0x3fefffff) return (hy<0)? huge*huge:tiny*tiny;
                 if(ix>=0x3ff00000) return (hy>0)? huge*huge:tiny*tiny;
             }
         /* over/underflow if x is not close to one */
             if(ix<0x3fefffff) return (hy<0)? s*huge*huge:s*tiny*tiny;
             if(ix>0x3ff00000) return (hy>0)? s*huge*huge:s*tiny*tiny;
         /* now |1-x| is tiny <= 2**-20, suffice to compute
            log(x) by x-x^2/2+x^3/3-x^4/4 */
             t = ax-one;         /* t has 20 trailing zeros */
             w = (t*t)*(0.5-t*(0.3333333333333333333333-t*0.25));
             u = ivln2_h*t;      /* ivln2_h has 21 sig. bits */
             v = t*ivln2_l-w*ivln2;
             t1 = u+v;
             __LO(t1) = 0;
             t2 = v-(t1-u);
         } else {
             double ss,s2,s_h,s_l,t_h,t_l;
             n = 0;
         /* take care subnormal number */
             if(ix<0x00100000)
                 {ax *= two53; n -= 53; ix = __HI(ax); }
             n  += ((ix)>>20)-0x3ff;
             j  = ix&0x000fffff;
         /* determine interval */
             ix = j|0x3ff00000;          /* normalize ix */
             if(j<=0x3988E) k=0;         /* |x|<sqrt(3/2) */
             else if(j<0xBB67A) k=1;     /* |x|<sqrt(3)   */
             else {k=0;n+=1;ix -= 0x00100000;}
             __HI(ax) = ix;

         /* compute ss = s_h+s_l = (x-1)/(x+1) or (x-1.5)/(x+1.5) */
             u = ax-bp[k];               /* bp[0]=1.0, bp[1]=1.5 */
             v = one/(ax+bp[k]);
             ss = u*v;
             s_h = ss;
             __LO(s_h) = 0;
         /* t_h=ax+bp[k] High */
             t_h = zero;
             __HI(t_h)=((ix>>1)|0x20000000)+0x00080000+(k<<18);
             t_l = ax - (t_h-bp[k]);
             s_l = v*((u-s_h*t_h)-s_h*t_l);
         /* compute log(ax) */
             s2 = ss*ss;
             r = s2*s2*(L1+s2*(L2+s2*(L3+s2*(L4+s2*(L5+s2*L6)))));
             r += s_l*(s_h+ss);
             s2  = s_h*s_h;
             t_h = 3.0+s2+r;
             __LO(t_h) = 0;
             t_l = r-((t_h-3.0)-s2);
         /* u+v = ss*(1+...) */
             u = s_h*t_h;
             v = s_l*t_h+t_l*ss;
         /* 2/(3log2)*(ss+...) */
             p_h = u+v;
             __LO(p_h) = 0;
             p_l = v-(p_h-u);
             z_h = cp_h*p_h;             /* cp_h+cp_l = 2/(3*log2) */
             z_l = cp_l*p_h+p_l*cp+dp_l[k];
         /* log2(ax) = (ss+..)*2/(3*log2) = n + dp_h + z_h + z_l */
             t = (double)n;
             t1 = (((z_h+z_l)+dp_h[k])+t);
             __LO(t1) = 0;
             t2 = z_l-(((t1-t)-dp_h[k])-z_h);
         }

     /* split up y into y1+y2 and compute (y1+y2)*(t1+t2) */
         y1  = y;
         __LO(y1) = 0;
         p_l = (y-y1)*t1+y*t2;
         p_h = y1*t1;
         z = p_l+p_h;
         j = __HI(z);
         i = __LO(z);
         if (j>=0x40900000) {                            /* z >= 1024 */
             if(((j-0x40900000)|i)!=0)                   /* if z > 1024 */
                 return s*huge*huge;                     /* overflow */
             else {
                 if(p_l+ovt>z-p_h) return s*huge*huge;   /* overflow */
             }
         } else if((j&0x7fffffff)>=0x4090cc00 ) {        /* z <= -1075 */
             if(((j-0xc090cc00)|i)!=0)           /* z < -1075 */
                 return s*tiny*tiny;             /* underflow */
             else {
                 if(p_l<=z-p_h) return s*tiny*tiny;      /* underflow */
             }
         }
     /*
      * compute 2**(p_h+p_l)
      */
         i = j&0x7fffffff;
         k = (i>>20)-0x3ff;
         n = 0;
         if(i>0x3fe00000) {              /* if |z| > 0.5, set n = [z+0.5] */
             n = j+(0x00100000>>(k+1));
             k = ((n&0x7fffffff)>>20)-0x3ff;     /* new k for n */
             t = zero;
             __HI(t) = (n&~(0x000fffff>>k));
             n = ((n&0x000fffff)|0x00100000)>>(20-k);
             if(j<0) n = -n;
             p_h -= t;
         }
         t = p_l+p_h;
         __LO(t) = 0;
         u = t*lg2_h;
         v = (p_l-(t-p_h))*lg2+t*lg2_l;
         z = u+v;
         w = v-(z-u);
         t  = z*z;
         t1  = z - t*(P1+t*(P2+t*(P3+t*(P4+t*P5))));
         r  = (z*t1)/(t1-two)-(w+z*w);
         z  = one-(r-z);
         j  = __HI(z);
         j += (n<<20);
         if((j>>20)<=0) z = scalbn(z,n); /* subnormal output */
         else __HI(z) += (n<<20);
         return s*z;
}

Well over a hundred lines of code, and consisting minimally of 1 if 
statement and maximally of around 2-3 dozen if statements.

All to avoid a single if statement? I think not.

With modern branch prediction, you'd probably lose out an amortized cost 
of a dozen clock cycles or so with that branch prediction, and there are 
some systems where the branch essentially becomes free (good candidate 
for predicates). If you're really that worried about a single if 
statement, then the sanity checks on your input parameters must be 
killing you.
-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

On 04/26/2011 07:34 AM, Eric Sosman wrote:
> On 4/26/2011 5:04 AM, Sanny wrote:
>>> Is there any way to avoid the if condition and do right shift and left
>>> shift using operators depending on shiftby is +ve or -ve?
>>
>> I used below technique but it gives error.
>>
>> divider=Math.pow(2,shiftby);
>> then
>> output = (long) N / divider;
>
> Let me get this straight: You're worried about the inefficiency
> of an `if' that chooses between a left or a right shift, so you plan
> to eliminate the `if' by evaluating an exponential function?
>
> ARE YOU OUT OF YOUR MIND?

Especially given that shift is blazingly efficient on just about any computer 
that supports Java.  You're optimizing something that's used *as* an 
optimization, Sanny-Boy.

Answer the questions people ask you, Sanny-Boy.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Lothar Kimmeringer wrote:
> Sanny wrote:
>
>> I have a problem where I have to do left shift and right shift.
>>
> [...]
>>
>> I have to use use left shift and right shift to shift Number right/
>> left depending on value of shiftby
>>
>> if (shift>0) output = N>>  shiftby; else output = N<<  (-shiftby);//
>> working but inefficient.

> In what way is it inefficient? Have you performed measurements
> or do you simply think that it's slow and want to optimize
> it prematurely?

Sanny-Boy, I see that you posted after Lothar asked you this very, very 
important question but that you did not answer this question.

This is a conversation, not a bunch of lackeys leaping to your bid.  Please 
answer the questions.

You claim inefficiency in something you have no clue whatsoever to be inefficient.

Here's another question, assuming you answer Lothar's question at all, if you 
did perform measurements, what were the results?

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On 26/04/2011 6:49 AM, Lew wrote:
> Lothar Kimmeringer wrote:
>> Sanny wrote:
>>
>>> I have a problem where I have to do left shift and right shift.
>>>
>> [...]
>>>
>>> I have to use use left shift and right shift to shift Number right/
>>> left depending on value of shiftby
>>>
>>> if (shift>0) output = N>> shiftby; else output = N<< (-shiftby);//
>>> working but inefficient.
>
>> In what way is it inefficient? Have you performed measurements
>> or do you simply think that it's slow and want to optimize
>> it prematurely?
>
> Sanny-Boy, I see that you posted after Lothar asked you this very, very
> important question but that you did not answer this question.
>
> This is a conversation, not a bunch of lackeys leaping to your bid.
> Please answer the questions.
>
> You claim inefficiency in something you have no clue whatsoever to be
> inefficient.
>
> Here's another question, assuming you answer Lothar's question at all,
> if you did perform measurements, what were the results?

And people claimed I was being arrogant to insist people learn to 
program before they learn Java...

On 26/04/2011 2:04 AM, Sanny wrote:
>> Is there any way to avoid the if condition and do right shift and left
>> shift using operators depending on shiftby is +ve or -ve?
>
> I used below technique but it gives error.
>
> divider=Math.pow(2,shiftby);
> then
> output = (long) N / divider;

My advice:
if (shift>0) output = N >> shiftby; else output = N << (-shiftby);

The above is pretty efficient, and once the hotspot compiler gets a hold 
of it, it will be even faster.

There is no assembly operator that shifts based on +/- bits; there are 
only shift-left and shift-right operators.  If there was a Java 
operator/function to do what you want, it would still be implemented (in 
machine language) as:

if (shift>0) output = N >> shiftby; else output = N << (-shiftby);

But I am curious why you consider the "if" test is expensive?

The usual rules for optimization:

1. Profile your code
2. Determine where your code is spending most of its time
3. Re-visit your algorithm and decide if you are using the right algorithm.
3a. If so, optimize the methods that are consuming most of the time.
3b. Implement a better algorithm and repeat these processes.

On 04/26/2011 10:09 AM, Travers Naran wrote:
> Lew wrote:
>> Here's another question, assuming you answer Lothar's question at all,
>> if you did perform measurements, what were the results?
>
> And people claimed I was being arrogant to insist people learn to program
> before they learn Java...

That's not arrogant, that's intelligent.  I agree mostly, although I believe 
it possible to learn both concurrently.  People most certainly should learn to 
program before they get paid to.

And I'm not arrogant, I'm supercilious.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Travers Naran wrote:
> Sanny wrote:
>>> Is there any way to avoid the if condition and do right shift and left
>>> shift using operators depending on shiftby is +ve or -ve?
>>
>> I used below technique but it gives error.
>>
>> divider=Math.pow(2,shiftby);

Please follow Java naming conventions.

>> then
>> output = (long) N / divider;

> My advice:
> if (shift>0) output = N >> shiftby; else output = N << (-shiftby);
>
> The above is pretty efficient, and once the hotspot compiler gets a hold of
> it, it will be even faster.
>
> There is no assembly operator that shifts based on +/- bits; there are only
> shift-left and shift-right operators. If there was a Java operator/function to
> do what you want, it would still be implemented (in machine language) as:

Doesn't matter, the Java operator *is* defined for negative values.

So the solution to Sanny's problem is:

  output = n >> shiftBy;

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Lew wrote:
> Doesn't matter, the Java operator *is* defined for negative values.
>
> So the solution to Sanny's problem is:
>
> output = n >> shiftBy;

OK, that is a trick answer because it's wrong.  True, the shift operator is 
defined for negative shift values, but those get masked to positive shift 
values regardless and don't give the OP's desired result.

Consider shifting an int by either 12 or -12

12  = 0b00001100
-12 = 0b11110100

The bottom five bits of the latter evaluate to 20.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On Tue, 26 Apr 2011 07:09:53 -0700, Travers Naran wrote:

> And people claimed I was being arrogant to insist people learn to
> program before they learn Java...

They were right. Java is a good choice for a programming neophyte because 
it imposes a sensible structure on the code being written.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

> This is a conversation, not a bunch of lackeys leaping to your bid. =A0Pl=
ease
> answer the questions.

Sorry, for that. I wanted to be short. not going into long
discussions.

> You claim inefficiency in something you have no clue whatsoever to be ine=
fficient.
>
> Here's another question, assuming you answer Lothar's question at all, if=
 you
> did perform measurements, what were the results?

I have computed and found "if statments" take 20-50 times longer than
basic arithmetic operations. So I wanted to replace if condition by
some arithmetics/ Maths.

Bye
Sanny

> >> Is there any way to avoid the if condition and do right shift and left
> >> shift using operators depending on shiftby is +ve or -ve?
>
> > I used below technique but it gives error.
>
> > divider=3DMath.pow(2,shiftby);
> > then
> > output =3D (long) N / divider;
>
> =A0 =A0 =A0Let me get this straight: You're worried about the inefficienc=
y
> of an `if' that chooses between a left or a right shift, so you plan
> to eliminate the `if' by evaluating an exponential function?
>
> =A0 =A0 =A0ARE YOU OUT OF YOUR MIND?

I didnt knew how much inefficient it is. I heard Math. (...) functions
are very fast and they use Native support like assembly language so
they are quite faster.

Is there a "Integer" in java which is longer than 64 bits?

byte: 8 bits
short: ???
int: 16/32 bits
long: 64 bit

any 128 bit integer???

I want something that can handle more bits than long. and I am able to
do bit operations on them.

I have heard of BigInteger I dont know how many bits it supports.

Can I use byte[] to represent a longer number and do multiplications/
divisions on them?

Bye
Sanny

> > Doesn't matter, the Java operator *is* defined for negative values.
>
> > So the solution to Sanny's problem is:
>
> > output =3D n >> shiftBy;
>
> OK, that is a trick answer because it's wrong. =A0True, the shift operato=
r is
> defined for negative shift values, but those get masked to positive shift
> values regardless and don't give the OP's desired result.

I did not get any error when using it but the answer was "0" when I
used negative shifts.

Maximum value a integer can hold is 64 bit in long variable. I want a
even larger number. Can I create a larger number which allows right-
shifts and left shifts? by multiplication/ division?

Bye
Sanny

On 4/26/2011 9:32 AM, Sanny wrote:
....
> I have computed and found "if statments" take 20-50 times longer than
> basic arithmetic operations. So I wanted to replace if condition by
> some arithmetics/ Maths.
....

You are seriously underestimating the range of variation of if-statement
time. It can be just as fast as an arithmetic statement. It must be
measured in context - you could be wasting your time if the actual mix
of left and right shifts has a pattern the branch predictor can pick up.

Patricia

On 4/26/2011 9:39 AM, Sanny wrote:
....
> I have heard of BigInteger I dont know how many bits it supports.
....

BigInteger uses int to index the bits, so it cannot contain more than
Integer.MAX_VALUE bits.

> Can I use byte[] to represent a longer number and do multiplications/
> divisions on them?

You could, with a lot of work, but the result would be a less efficient
version of BigInteger. BigInteger uses int[] internally to store the
data, reducing the number of separate operations when operating on a
large number.

Patricia

Sanny, please attribute your citations.

Sanny wrote:
>>>> Is there any way to avoid the if condition and do right shift and left
>>>> shift using operators depending on shiftby is +ve or -ve?
>>
>>> I used below technique but it gives error.
>>
>>> divider=Math.pow(2,shiftby);
>>> then
>>> output = (long) N / divider;

Eric Sosman wrote:
>>       Let me get this straight: You're worried about the inefficiency
>> of an `if' that chooses between a left or a right shift, so you plan
>> to eliminate the `if' by evaluating an exponential function?
>>
>>       ARE YOU OUT OF YOUR MIND?

Sanny wrote:
> I didnt knew how much inefficient it is. I heard Math. (...) functions
> are very fast and they use Native support like assembly language so
> they are quite faster.

Whence did you hear that?  Please let us know the source(s).

Think through on the basis of fundamental computer science.  Math.xxx() 
methods on floating point ('float' and 'double') are always going to be slower 
than integer operations, particularly single-instruction operations like 
shift.  However, the difference isn't always going to matter.

So when some anonymous, untrusted source tells you that a Math.xxx() method is 
"very fast", the context OBVIOUSLY is relative to other implementations of the 
same functionality, not "'Math.pow()' is faster than '>>>'".  If you saw 
*that* claim, throw away the source immediately.

Programming is an art that requires the practitioner to *think*.  Cargo-cult 
reactions based on no evidence or reason or even thought, such as "Math.pow() 
is 'very fast', so I'll use it instead of shift operators without measuring 
first what impact if any the shift operators have on actual performance."

> Is there a "Integer" in java [psic] which is longer than 64 bits?

RTFM. [1]

> byte: 8 bits
> short: ???
> int: 16/32 bits

Where do you get this?  Type sizes in Java are fixed to particular values, not 
"16/32".

> long: 64 bit
>
> any 128 bit integer???

How many question marks does it take to indicate an interrogative?

> I want something that can handle more bits than long. and I am able to
> do bit operations on them.
>
> I have heard of BigInteger I dont know how many bits it supports.

RTFM. [2]

> Can I use byte[] to represent a longer number and do multiplications/
> divisions on them?

Yes.

But why would you?

As for RTFMing, you will make zero progress as a programmer, in fact, you are 
not even a programmer unless you habitually and competently read and 
comprehend the documentation.

One who does not habitually and competently read and comprehend the 
documentation will learn less than nothing from questions asked and answers 
received of Usenet.

Assimilation of that advice will accelerate your skills a thousandfold.

[1]
<http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.2.1>

[2]
<http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html>

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Lew wrote:
>> ... java [psic] ...

self-[sic]

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Sanny, please attribute your citations.

Sanny wrote:
>>> Doesn't matter, the Java operator *is* defined for negative values.

See?  You didn't write that.

Sanny wrote:
> Lew wrote:

>>> Doesn't matter, the Java operator *is* defined for negative values.
>>> So the solution to Sanny's problem is:
>>
>>> output = n>>  shiftBy;
>>
>> OK, that is a trick answer because it's wrong.  True, the shift operator is
>> defined for negative shift values, but those get masked to positive shift
>> values regardless and don't give the OP's desired result.

Sanny wrote:
> I did not get any error when using it but the answer was "0" when I
> used negative shifts.

What was the shift value you used?  What were the lower five bits of the right 
operand (if the left operand was 'int') or six bits (if the left operand was 
'long')?

> Maximum value a integer can hold is 64 bit in long variable. I want a
> even larger number. Can I create a larger number which allows right-
> shifts and left shifts? by multiplication/ division?

RTFM.

<http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html#shiftLeft(int)>
<http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html#shiftRight(int)>

RTFM.  RTFM.  RTFM.  RTFM.  RTFM.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On 26/04/2011 20:55, Lew allegedly wrote:
> "'Math.pow()' is faster than '>>>'". If you saw *that* claim, throw
> away the source immediately.

And then beat it to a pulp and put its head on a pike, for good measure.

-- 
DF.
An escaped convict once said to me:
"Alcatraz is the place to be"

On 26.04.2011 09:38, Sanny wrote:

> output = N<<  shiftby; //[Not change in sign "<<" instead of">>"]

I am not sure what you mean by that comment.  Just for completeness 
reasons I want to make sure you are aware of operator ">>>":

http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#5121

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

On 4/26/2011 11:09 AM, Patricia Shanahan wrote:
> On 4/26/2011 9:32 AM, Sanny wrote:
> ...
>> I have computed and found "if statments" take 20-50 times longer than
>> basic arithmetic operations. So I wanted to replace if condition by
>> some arithmetics/ Maths.
> ...
>
> You are seriously underestimating the range of variation of if-statement
> time. It can be just as fast as an arithmetic statement. It must be
> measured in context - you could be wasting your time if the actual mix
> of left and right shifts has a pattern the branch predictor can pick up.

Incidentally, one of the fastest cases arises during multi-word
shifting. Each word in the shift will have the same pattern of taken and
not-taken branches. If you do an N-word shift, about (N-1)/N branches
will be correctly predicted by just about any reasonable algorithm, and
go as fast as a simple arithmetic operation.

The Math methods also need to be measured. The native implementations
will use whatever fast hardware is available, but some operations may
not have hardware support on every system.

Patricia

Lew <noone@lewscanon.com> wrote:
> Sanny, please attribute your citations.
> Sanny wrote: [sic*]
>>>>> Is there [...]
> Eric Sosman wrote: [sic*]
>>> Let me [...]
> Sanny wrote:
>> I didnt [...]

*: Two of three attributions (intendly?) wrongly indented.

Lew, please indent attributions with the correct number of ">"s.

On 4/26/2011 12:39 PM, Sanny wrote:
>>>> Is there any way to avoid the if condition and do right shift and left
>>>> shift using operators depending on shiftby is +ve or -ve?
>>
>>> I used below technique but it gives error.
>>
>>> divider=Math.pow(2,shiftby);
>>> then
>>> output = (long) N / divider;
>>
>>       Let me get this straight: You're worried about the inefficiency
>> of an `if' that chooses between a left or a right shift, so you plan
>> to eliminate the `if' by evaluating an exponential function?
>>
>>       ARE YOU OUT OF YOUR MIND?
>
> I didnt knew how much inefficient it is. I heard Math. (...) functions
> are very fast and they use Native support like assembly language so
> they are quite faster.

     "Fast" is not an absolute, and neither is "very fast."  If you
plant an acorn today and have a fifty-foot oak tree in ten years,
that's "fast."  If you strike a match now and see a flame in ten
minutes, that's "slow" even though its half a million times faster
than the "fast" oak tree.

     In other words, interpret "fast" in relation to the amount of
work being done.

> Is there a "Integer" in java which is longer than 64 bits?
> [...]
> I have heard of BigInteger I dont know how many bits it supports.

     Perhaps the Javadoc for BigInteger might be helpful?  Oh, no,
sorry, that's *way* too obvious, there must be a grue waiting for
anyone who tries to read the Javadoc.  Never mind.

> Can I use byte[] to represent a longer number and do multiplications/
> divisions on them?

     No.  Somebody else could, if he were sufficiently masochistic,
but at your present level of Java proficiency[*] it's pretty clear
that you cannot.

     [*] No offense: We all begin from ignorance.  Your progress from
the starting point is not yet enough to enable you to do this task.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

On 04/26/2011 07:32 PM, Andreas Leitgeb wrote:
> Lew<noone@lewscanon.com>  wrote:
>> Sanny, please attribute your citations.
>> Sanny wrote: [sic*]
>>>>>> Is there [...]
>> Eric Sosman wrote: [sic*]
>>>> Let me [...]
>> Sanny wrote:
>>> I didnt [...]
>
> *: Two of three attributions (intendly?) wrongly indented.
>
> Lew, please indent attributions with the correct number of ">"s.

Obviously you neglected to see how far back these quotes came.  The 
indentations were correct.  Check again.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On 26/04/2011 9:32 AM, Sanny wrote:
> I have computed and found "if statments" take 20-50 times longer than
> basic arithmetic operations. So I wanted to replace if condition by
> some arithmetics/ Maths.

This is why I think assembly language should be mandatory in schools. :-)

An if statement gets translated into something like (using a 
pseudo-assembly for readability):

;; if (b > 0) return a << b else return a >> -b
  compare b to 0
  jump-less-than to L1
  a := a << b
  jump L2
L1:
  b := -b
  a := a >> b
L2:
  return  ;; result in a

It's the jump that's adding the time.  But on an x86, that kind of 
instruction can be entirely cached and the Intel/AMD processors can 
perform predictive branching to speed up this bit of code.

The only way you should be getting 20-50 times longer is if you aren't 
using any sort of optimizing run-time.  Example: running always as byte 
code without compiling.

But usually this kind of if-checking and bit-twiddling is so fast that 
it's not worth optimizing beyond a single statement.  What are you 
coding that makes this the most expensive calculation in your program?


OFF-TOPIC
=========

Bonus Question:
If branching is "20-50 times longer" than any of the operations 
(negation or shifting), how could you re-write this assembly to use a 
single branch statement?

Extra Bonus:
Using your favorite processor instruction set, come up with a fast 
implementation of: if (b > 0) return a << b; else return a >> -b;

Lew <noone@lewscanon.com> wrote:
> On 04/26/2011 07:32 PM, Andreas Leitgeb wrote:
>> Lew<noone@lewscanon.com>  wrote:
>>> Sanny, please attribute your citations.
>>> Sanny wrote: [sic*]
>>>>>>> Is there [...]
>>> Eric Sosman wrote: [sic*]
>>>>> Let me [...]
>>> Sanny wrote:
>>>> I didnt [...]
>> *: Two of three attributions (intendly?) wrongly indented.
>> Lew, please indent attributions with the correct number of ">"s.
> Obviously you neglected to see how far back these quotes came.  The 
> indentations were correct.  Check again.

I said they were wrongly *indented*, not that they were wrongly placed.

As I explained already once, a snippet like this:

   Eric Sosman wrote:
   >> Let me [...]

does NOT say, that the words "Let me" were Eric's, but instead implies,
that Eric Sosman had quoted someone who wrote those words, because there
are two levels difference in indentation.

Had you instead written:
   > Eric Sosman wrote:
   >> Let me [...]
it would have been correct and remained clear in further followups,
each adding another ">" infront of all the lines (except the new
initial attribution line).

PS: there was another [sic] in my post, though: the word "intendedly" 
  had unnoticedly lost one of its "ed"s.

PPS: The higher the need to strictly clarify who wrote what, the lower 
  really the use of contributing to that particular subthread. :-)

On 11-04-27 03:57 AM, Andreas Leitgeb wrote:
[ SNIP ]

> As I explained already once, a snippet like this:
> 
>    Eric Sosman wrote:
>    >> Let me [...]
> 
> does NOT say, that the words "Let me" were Eric's, but instead implies,
> that Eric Sosman had quoted someone who wrote those words, because there
> are two levels difference in indentation.
[ SNIP ]

That's strictly true, but Jesus, I hope nobody does that. :-) I've seen
a few too many flame wars start from attribution confusion caused by
quoting finessing like that.

AHS

On 4/26/2011 10:40 PM, Travers Naran wrote:
....
> ;; if (b > 0) return a << b else return a >> -b
>  compare b to 0
>  jump-less-than to L1
>  a := a << b
>  jump L2
> L1:
>  b := -b
>  a := a >> b
> L2:
>  return  ;; result in a
....
> It's the jump that's adding the time. But on an x86, that kind of
> instruction can be entirely cached and the Intel/AMD processors can
> perform predictive branching to speed up this bit of code.
>
> The only way you should be getting 20-50 times longer is if you
> aren't using any sort of optimizing run-time. Example: running always
> as byte code without compiling.
>
> But usually this kind of if-checking and bit-twiddling is so fast
> that it's not worth optimizing beyond a single statement. What are
> you coding that makes this the most expensive calculation in your
> program?
....

The obvious possibility is a random mix of left and right shifts, with
the two directions equally probable. In that case, the hardware branch
prediction would mis-predict, on average, half the time.

When the hardware branch prediction gets it wrong, the result is a
complete pipeline flush. With deep pipelines and multiple instructions
in each pipeline stage, a pipeline flush costs the equivalent of dozens
of simple arithmetic operations.

My question is whether the measurement was from the actual program, or
from a benchmark that may differ from the real program in ways that
affect branch prediction.

> If branching is "20-50 times longer" than any of the operations
> (negation or shifting), how could you re-write this assembly to use a
> single branch statement?

Why bother? Your sample code only has one conditional branch,
"jump-less-than to L1". Unconditional jumps to a fixed target, such as
"jump L2" are always correctly predicted, and take about the same time
as a simple arithmetic operation. The method is short enough that the
JVM will in-line it anywhere it is frequently called so we don't have to
worry about the return.

Patricia

Andreas Leitgeb wrote:
> Lew wrote:
>>  Andreas Leitgeb wrote:
>>> Lew  wrote:
>>>> Sanny, please attribute your citations.
>>>> Sanny wrote: [sic*]
>>>>>>>> Is there [...]
>>>> Eric Sosman wrote: [sic*]
>>>>>> Let me [...]
>>>> Sanny wrote:
>>>>> I didnt [...]
>>> *: Two of three attributions (intendly?) wrongly indented.
>>> Lew, please indent attributions with the correct number of ">"s.
>> Obviously you neglected to see how far back these quotes came.  The
>> indentations were correct.  Check again.

[Andreas]
> I said they were wrongly *indented*, not that they were wrongly placed.
>
> As I explained already once, a snippet like this:
>
>     Eric Sosman wrote:
>     >>  Let me [...]
>
> does NOT say, that the words "Let me" were Eric's, but instead implies,
> that Eric Sosman had quoted someone who wrote those words, because there
> are two levels difference in indentation.

TFB, dude.

> Had you instead written:
>     >  Eric Sosman wrote:
>     >>  Let me [...]
> it would have been correct and remained clear in further followups,
> each adding another ">" infront of all the lines (except the new
> initial attribution line).
>
> PS: there was another [sic] in my post, though: the word "intendedly"
>    had unnoticedly lost one of its "ed"s.
>
> PPS: The higher the need to strictly clarify who wrote what, the lower
>    really the use of contributing to that particular subthread. :-)

Fuck that.  I'm sticking with the indentation Thunderbird gives me, and the 
occasional reinforcement with reminders of whose speaking.  Work it out or 
don't read it, I don't care which.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

Travers Naran wrote:
> On 26/04/2011 9:32 AM, Sanny wrote:
>> I have computed and found "if statments" take 20-50 times longer than
>> basic arithmetic operations. So I wanted to replace if condition by
>> some arithmetics/ Maths.
>
> This is why I think assembly language should be mandatory in schools. :-)

I think assembly level died when hot spot, branch prediction, parallelism
and deep pipelines came in.

I will never forget the day when a compiler BEAT me :-(

   BugBear

Lew <noone@lewscanon.com> wrote:
> TFB, dude.

I wouldn't care a dime, either, if you weren't always so 
f'ing insisting on others following usenet conventions.

On 4/26/2011 6:47 AM, Lew wrote:
> On 04/26/2011 07:34 AM, Eric Sosman wrote:
>> On 4/26/2011 5:04 AM, Sanny wrote:
>>>> Is there any way to avoid the if condition and do right shift and left
>>>> shift using operators depending on shiftby is +ve or -ve?
>>>
>>> I used below technique but it gives error.
>>>
>>> divider=Math.pow(2,shiftby);
>>> then
>>> output = (long) N / divider;
>>
>> Let me get this straight: You're worried about the inefficiency
>> of an `if' that chooses between a left or a right shift, so you plan
>> to eliminate the `if' by evaluating an exponential function?
>>
>> ARE YOU OUT OF YOUR MIND?
>
> Especially given that shift is blazingly efficient on just about any
> computer that supports Java. You're optimizing something that's used
> *as* an optimization, Sanny-Boy.

As far as I can tell, Lew-Boy, he has not asked to optimize out the
shift, except as a means to the end of avoiding a conditional branch.
Whether that is an issue or not depends on the context, the
predictability of the branch, and the performance of the alternatives.

[I had not previously seen appending "-Boy" to the name as a convention
for addressing people in USENET articles, but I'll go along with
whatever mode of address the person I'm responding to seems to prefer.]

Patricia

Patricia Shanahan wrote:
> Lew wrote:
> As far as I can tell, Lew-Boy, ...
>
> [I had not previously seen appending "-Boy" to the name as a convention
> for addressing people in USENET articles, but I'll go along with
> whatever mode of address the person I'm responding to seems to prefer.]

It's an informal mode of address popular in the U.S.  It rhymes with "Danny 
Boy", title the famous song set to an English folk tune.  It's a rubric often 
used between friends, as in, "Hey, Jimmy-Boy!  How the hell have you been, you 
old so-and-so?"

I suppose you're complaining that I was being too informal.  Sorry.  You, of 
course, Dr. Shanahan, do not have to ask for the privilege of being informal 
with me.  I would be honored to have you call me "Lew-Boy".

-- 
Lew
I am known as "Mr. Boy."  I fetch and carry, wrap wires, do useful things around.

On 04/27/2011 10:03 AM, Andreas Leitgeb wrote:
> Lew<noone@lewscanon.com>  wrote:
>> TFB, dude.
>
> I wouldn't care a dime, either, if you weren't always so
> f'ing insisting on others following usenet [sic] conventions.

You mean like actually attributing citations and providing enough useful 
information about a problem that someone could help them?

Yeah, those are pretty fucking arbitrary conventions.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On Apr 27, 7:49=A0pm, Lew <no...@lewscanon.com> wrote:
....
> It's an informal mode of address popular in the U.S. =A0It rhymes with "D=
anny
> Boy", title the famous song set to an English folk tune. =A0It's a rubric=
 often
> used between friends, as in, "Hey, Jimmy-Boy! =A0How the hell have you be=
en, you
> old so-and-so?"

Describing "Londonderry Air" as an _English_ folk tune could get you
into troubles [sic].

P.S.  I didn't realise your use of "-Boy" was just informal
friendliness. I'd assumed you used it as a mild insult. Is that not
the case?

Paul Cager wrote:
> Lew wrote:
>> ... "DannyBoy", title [of] the famous song set to an English folk tune. ...

> Describing "Londonderry Air" as an _English_ folk tune could get you
> into troubles [sic].

Good catch!  My boo-boo.  Me Oirish ancestors'd take a shillelagh to me for 
that error.

-- 
Lew

On Tue, 26 Apr 2011 09:49:24 -0400, Lew <noone@lewscanon.com> wrote,
quoted or indirectly quoted someone who said :

>You claim inefficiency in something you have no clue whatsoever to be inefficient.

If you examined the code generated, you might be pleasantly surprised.
I did a fair bit of looking at the code Jet generated and came to the
conclusion it would nearly always generate better code than a human
would. It was not only optimising cycles, it was optimising pipelines.

-- 
Roedy Green Canadian Mind Products
http://mindprod.com
Politicians complain that Kindles and iBooks are killing jobs by 
destroying the paper book industry.  I see it that they have create a way 
to produce books for less than a third the cost without destroying forests 
and emitting greenhouse gases in the process.  They have created wealth.  
They are encouraging literacy and cutting the costs of education.  

On 04/27/2011 10:25 PM, Roedy Green wrote:
> On Tue, 26 Apr 2011 09:49:24 -0400, Lew<noone@lewscanon.com>  wrote,
> quoted or indirectly quoted someone who said :
>
>> You claim inefficiency in something you have no clue whatsoever to be inefficient.
>
> If you examined the code generated, you might be pleasantly surprised.
> I did a fair bit of looking at the code Jet generated and came to the
> conclusion it would nearly always generate better code than a human
> would. It was not only optimising cycles, it was optimising pipelines.

Excellent point.  Hotspot also optimizes code to a good level due to its 
dynamic nature.  I don't know how to examine its results, although that would 
be interesting to capture somehow.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On 2011-04-27 08:34:32 -0400, Patricia Shanahan said:

> On 4/26/2011 10:40 PM, Travers Naran wrote:
> ...
>> ;; if (b > 0) return a << b else return a >> -b
>> compare b to 0
>> jump-less-than to L1
>> a := a << b
>> jump L2
>> L1:
>> b := -b
>> a := a >> b
>> L2:
>> return  ;; result in a
> ...
>> It's the jump that's adding the time. But on an x86, that kind of
>> instruction can be entirely cached and the Intel/AMD processors can
>> perform predictive branching to speed up this bit of code.
>> 
>> The only way you should be getting 20-50 times longer is if you
>> aren't using any sort of optimizing run-time. Example: running always
>> as byte code without compiling.
>> 
>> But usually this kind of if-checking and bit-twiddling is so fast
>> that it's not worth optimizing beyond a single statement. What are
>> you coding that makes this the most expensive calculation in your
>> program?
> ...
> 
> The obvious possibility is a random mix of left and right shifts, with
> the two directions equally probable. In that case, the hardware branch
> prediction would mis-predict, on average, half the time.

There are worse distributions. Consider a program that alternates 
between the two possible branch outcomes, assuming a four-bit branch 
prediction counter like those found in several generations of Intel 
chips: it's possible that the sequence will start by acting opposite to 
the prediction and flipping the predicted direction for the next branch 
(from b01 to b10 or vice versa). A strictly alternating sequence of 
branches would then be mis-predicted *every time*.

One of the things that could've made Itanic so cool was the ability to 
pre-emptively evaluate both sides of a branch, many instructions in 
advance, and throw away all the alternatives but the one that "actually 
happened". Unfortunately, programming around this was really hard even 
for experienced compiler writers, and the chips were notoriously 
power-hungry and expensive, so it never really took off.

> When the hardware branch prediction gets it wrong, the result is a
> complete pipeline flush. With deep pipelines and multiple instructions
> in each pipeline stage, a pipeline flush costs the equivalent of dozens
> of simple arithmetic operations.
> 
> My question is whether the measurement was from the actual program, or
> from a benchmark that may differ from the real program in ways that
> affect branch prediction.

My question is "who cares?"

There are lots of ways to squeeze more performance out of an 
otherwise-optimal algorithm: make better use of vector operations, 
migrate some or all of the work to the GPU (a massively-parallel 
floating point unit), or find ways to avoid running it at all. 
Measuring the cost of an if statement is pretty far down the list of 
tuning choices.

(Having seen examples of Sanny's code in other newsgroups, I am 
extremely doubtful that he's reached the "optimal algorithm" stage. 
However, I haven't seen his code, so it's possible.)

>> If branching is "20-50 times longer" than any of the operations
>> (negation or shifting), how could you re-write this assembly to use a
>> single branch statement?
> 
> Why bother? Your sample code only has one conditional branch,
> "jump-less-than to L1". Unconditional jumps to a fixed target, such as
> "jump L2" are always correctly predicted, and take about the same time
> as a simple arithmetic operation.

Unless they force a cache stall. For a routine as trivial as the one 
Travers posted, it's unlikely that the final 'return' would be on a 
separate cache line from the start of the routine, but in a longer 
routine, replacing the jump-to-return with a return might actually keep 
the end of the routine out of cache.

Of course, if the code that called this routine has fallen out of 
cache, the return instruction will force a cache stall, instead.

> The method is short enough that the
> JVM will in-line it anywhere it is frequently called so we don't have to
> worry about the return.

Agree. Even though it's not actually magic and doesn't always produce 
totally optimal (either in time or in space) code, the JIT compiler 
produces surprisingly good code most of the time. Second-guessing it 
down at the level of individual machine instructions is the sort of 
thing that impresses bystanders but rarely accomplishes anything useful.

-o

Travers Naran wrote:

> The usual rules for optimization:
> 
> 1. Profile your code
> 2. Determine where your code is spending most of its time
> 3. Re-visit your algorithm and decide if you are using the right algorithm.
> 3a. If so, optimize the methods that are consuming most of the time.
> 3b. Implement a better algorithm

3c Run your testcases to check that nothing is broken
3d Realize that you haven't one
3e Roll back your changes using SVN->Revert
3f Write a testcase checking the current algorithm and its
   borders where it's not working anymore and run it
3g Go back to 3b and skip 3d - 3g

3f
> and repeat these processes.


Regards, Lothar
-- 
Lothar Kimmeringer                E-Mail: spamfang@kimmeringer.de
               PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
                 questions!

On 4/27/2011 9:37 PM, Owen Jacobson wrote:
> On 2011-04-27 08:34:32 -0400, Patricia Shanahan said:
....
>> The obvious possibility is a random mix of left and right shifts, with
>> the two directions equally probable. In that case, the hardware branch
>> prediction would mis-predict, on average, half the time.
>
> There are worse distributions. Consider a program that alternates
> between the two possible branch outcomes, assuming a four-bit branch
> prediction counter like those found in several generations of Intel
> chips: it's possible that the sequence will start by acting opposite to
> the prediction and flipping the predicted direction for the next branch
> (from b01 to b10 or vice versa). A strictly alternating sequence of
> branches would then be mis-predicted *every time*.
....

I agree that, depending on the branch predictor implementation, it is
possible to get worse than 50% mis-prediction for a single conditional
branch. However, the right patterns are relatively unlikely.

On the other hand, someone who does not understand branch prediction
would be quite likely write a conditional branch benchmark that gets 50%
mis-prediction.

Patricia

Owen Jacobson wrote:
> 
> One of the things that could've made Itanic so cool was the ability to
> pre-emptively evaluate both sides of a branch, many instructions in
> advance, and throw away all the alternatives but the one that "actually
> happened". Unfortunately, programming around this was really hard even
> for experienced compiler writers, and the chips were notoriously
> power-hungry and expensive, so it never really took off.

Eh? Speculative execution is hardly a rare CPU feature, among modern
general-purpose CPUs. At least one reference[1] claims "all modern
CPUs" have spec-exec - which seems dubious, but I suppose one could
quibble over what a "modern" CPU is. x86 CPUs have had it at least
since the Pentium Pro (P6).[2] PPC has had it since at least the 603.[3]

If it's branch predication (note I'm talking about *predication*, not
*prediction*, here) you're thinking of, that also antedates Itanium
and continues to be implemented in modern CPUs. DEC Alpha and HP
PA-RISC had limited predication, where stores to memory on a
speculative branch could be rewritten to write to a register instead,
with a predicate-controlled store after the branch result was known;
and PPC has had aggressive predication since at least the 604.[4]

US patent 5,471,593 describes predicated execution; it was filed in
1995. And it cites prior work, including the Cydra 5 from the late
'80s - which I don't know much about, but which apparently had a basic
predicated-execution system.

So, not new in the Itanium, and not sinking with it either.

[1] http://www.hardwaresecrets.com/printpage/209
[2] http://www.datasheetarchive.com/datasheet-pdf/078/DSAE0072944.html
[3] http://www.cs.pitt.edu/~alanjawi/history.html
[4]
http://www.princeton.edu/~rblee/ELE572Papers/the-effects-of-predicated.pdf

-- 
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University

On 27.04.2011 07:40, Travers Naran wrote:
> On 26/04/2011 9:32 AM, Sanny wrote:
>> I have computed and found "if statments" take 20-50 times longer than
>> basic arithmetic operations. So I wanted to replace if condition by
>> some arithmetics/ Maths.
>
> This is why I think assembly language should be mandatory in schools. :-)
>
> An if statement gets translated into something like (using a
> pseudo-assembly for readability):
>
> ;; if (b > 0) return a << b else return a >> -b
> compare b to 0
> jump-less-than to L1
> a := a << b
> jump L2
> L1:
> b := -b
> a := a >> b
> L2:
> return ;; result in a

Folks, this is all too complicated. As already stated, branches can kill 
the performance, but it is just too easy without them:

(x >> r) << l.

And set l = max(-s,0) and r = max(s,0) where is is the "signed right 
shift". If the shift is always by the same constant, it is easier to 
precalculate l and r once and apply the shift all over again.

Alternatively, if the shift is always dynamic, l and r can also be 
computed without any branch:

int m = (s >> 31);
int r = s & m;
int l = (-s) & (~m);
int x = (x >> r) << l;

Whether this is faster depends of course whether a branch prediction is 
able to predict the branches well.

Greetings,
	Thomas