"Hicham Mouline" <(E-Mail Removed)> writes:

> Hello,

>

> I have code that resembles:

>

> double Get(...) {

>

> double var1;

> double bound1.... boundN; // N is of the order of 7/8

>

> double output;

> if (var1< bound1)

> output = ...;

> else if (var1< bound2)

> output = ...;

> ...

> else if (var1< boundN)

> output = ...;

> else

> output = ...;

>

> return output;

>

> }

>

>

> is there a more efficient way of writing this?
If N is really big and the bounds don't change, and you have to test

several times, Michael's solution could be a good one.

But there is quite an over head in building the vector...

The problem is that writting a discriminating tree you will be able to

determine the output in log2(N) cmp+jlt, while allocating the vector,

copying the bounds there, will take a lot of instructions in O(N),

before you start searching (which will be O(log2(N)) but with bigger

constants than the discriminating tree of ifs...

So:

if(var1<bound(N/2)){

if(var1<bound(N/4)){

if(var1<bound(N/

){

}else{

}

}else{

if(var1<bound(N/4+N/

){

}else{

}

}

}else{

if(var1<bound(N/2+N/4)){

if(var1<bound(N/2+N/

){

}else{

}

}else{

if(var1<bound(N/2+N/4+N/

){

}else{

}

}

}

That is, in the case where N=8:

if(var1<bound4){

if(var1<bound2){

if(var1<bound1){

}else{

}

}else{

if(var1<bound3){

}else{

}

}

}else{

if(var1<bound6){

if(var1<bound5){

}else{

}

}else{

if(var1<bound(7)){

}else{

}

}

}

It is easy to write a little emacs function to generate such a

discriminating if tree for any value of N.

--

__Pascal Bourguignon__