P is for Practical PerlMonks

### search algo to reach a number

by vijesh (Novice)
 on Sep 27, 2013 at 15:05 UTC Need Help??
vijesh has asked for the wisdom of the Perl Monks concerning the following question:

Hello Experts. I am trying to get an program to reach a number with minimum number of iteration. what I wrote is given below. Is there a better way? <\p>

```eg: I want to reach 1000 starting from 30.

script output
-------------

Find 1000

ASCENT
130
230
330
430
530
630
730
830
930
1030

DESCENT
1442
1186
1058
994
1026
1010
1002
998
1000

GOT IT...\$newScale == \$dest --> 1000 == 1000
Total Iteration taken is 21

```my \$dest = 1000;
my \$start = 30;
my \$steps = 100;
my \$newScale = \$start;
my \$ascent = 1;
my \$descent = 0;
my \$n = 9; # n is power of 2 to reach \$steps
my \$i=1;
print "Find \$dest\n";
print "\n\nASCENT\n";
while (\$ascent) {

if (\$newScale < \$dest) {
\$i++;
\$newScale = \$newScale + \$steps;
print "\$newScale\n";

} else {
\$ascent = 0;
\$descent = 1;
\$newScale = \$newScale - \$steps;
\$i++;

}
}

print "\n\nDESCENT\n";
while (\$descent) {
if ( \$n < 0 ) { last; }
if (\$newScale > \$dest) {
\$newScale = \$newScale - 2**\$n;
print "\$newScale\n";
\$i++;
} else {
\$newScale = \$newScale + 2**\$n;
\$i++;
print "\$newScale\n";
}
if (\$newScale == \$dest) {
print "\n\nGOT IT...\\$newScale == \\$dest --> \$newScale == \$des
+t \nTotal Iteration taken is \$i \n";
last;
}
\$n--;
}

Replies are listed 'Best First'.
Re: search algo to reach a number
by Laurent_R (Canon) on Sep 27, 2013 at 17:39 UTC

Make a Google search on the following words: dichotomic search algorithm, binary search algorithm or half-interval search algorithm. This is likely to be your more efficient solution.

Re: search algo to reach a number
by davido (Archbishop) on Sep 27, 2013 at 15:18 UTC

What is this for?

Dave

There is a requirement to get a scaled number by considering certain parameters (memory usage, cpu usage..). eg: if I configure 1000 numbers in a machine, its mem goes to 85%. if I configure 900 numbers in a machine, its mem goes to 82%. ---- ---- I need to find a number where machines memory does not cross 80%. Hence I have to go up and down and get the exact number that hit 80%. my algo starts with 100 goes all the way till 1000. When cross 1000, I presume, my machine hit util of > 80%. Hence I need to descent and then reach 1000. Am I clear now?

The most computationally inexpensive solution would be a mathematical formula, rather than a brute force search through your problem domain.

If it's impossible to come up with an exact formula, I suppose you could use a binary search, which guarantees that you will find your target in a list of numbers between 100 and 1000 in ten iterations or less.

Let's say you are able to determine that some set of criteria produces some known result. And let's say that there is a tolerable range; you wouldn't want to have more than some amount of resources idle, nor would you want to have more than some amount of resources in use. So you are ok with some narrow range surrounding, say, your 80% target. You can binary search using a derivation function and a custom comparator.:

```use List::BinarySearch qw/ binsearch /;

my @domain = ( 100 .. 1000 );

print "Target: ", \$domain[ binsearch { comparator( \$a, \$b ) } 80, @dom
+ain ], "\n";

sub comparator {
my( \$low, \$high ) = derive(\$b);
return -1 if \$a < \$low;
return  1 if \$a > \$high;
return 0;
}

sub derive {
my \$raw = shift;
my \$low = \$raw * .14;
my \$high = \$raw * .19;
return ( \$low, \$high );
}
__END__
__OUTPUT__
422

My derive function is highly contrived. Presumably you have some way of knowing what your resource load will be for a given set of inputs, and that's what would need to be calculated in the derive function.

I don't fully understand the challenges you are facing, but incrementing by 30 and then descending from some number again is a linear approach, whereas a binary search is a logarithmic approach. I have no idea what you would need to stick into derive() to make this technique work. But I do hope it gives you some ideas.

Dave

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1055995]
Approved by marinersk
help
Chatterbox?
 LanX it's an imaginary list ... LanX ... reflecting root problems choroba uses real lists so he can easily insert as many items in between as needed LanX questions the integerity of this approach. .. LanX doesn't sound natural [LanX]: welcome to a new episode of Big Perl Theory...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (10)
As of 2018-03-20 10:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (250 votes). Check out past polls.

Notices?