What I have is a function f(N) that accepts integer arguments only (it
happens to be monotonic, but that's not particularly important).  What
I'd like to do is find an integer k such that f(k) and f(k+1) have
opposite signs.  Meaning, an actual root of the function f(N),
pretending N is real, lies somewhere between the successive integers k
and k+1.  Also, I will note that using "fzero" is out of the question,
as my function f(N) simply does not accept non-integer values.

SUMMARY
  I need the integer k such that  f(k)*f(k+1) < 0

Is there some sort of bracketing algorithm in Matlab to do this?

I know this can be done in a stupid way by calculating the function
for a large range of integers and using "find" or something like that,
but I'd like something that converges faster.

Thanks,
Jim

Jim Rockford wrote:
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important).

It is important: it allows you to know that if the sign is the same on two 
ends of an interval, then it is not because the sign changed twice on the 
interval.

>  What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs.  Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1.

You can use a bisection method, also known as a binary search. The time 
required would be proportional to log2 of the search range.

Jim Rockford <jim.rockford1@gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b@l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important).  What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs.  Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1.  Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
> 
> SUMMARY
>   I need the integer k such that  f(k)*f(k+1) < 0
> 
> Is there some sort of bracketing algorithm in Matlab to do this?
> 
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.
> 
> Thanks,
> Jim

Hi

Can you write a wrapper around f(N) which does accept non-integer values?

function val=fwrap(x);
val=f(round(x));
end

and now use fzero on fwrap, with the tolerance on x set so that when x is changing by less than 0.5 you stop?

Ross

Jim Rockford <jim.rockford1@gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b@l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important).  What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs.  Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1.  Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
> 
> SUMMARY
>   I need the integer k such that  f(k)*f(k+1) < 0
> 
> Is there some sort of bracketing algorithm in Matlab to do this?
> 
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.

Why don't you write a wrapper function that accepts a double input, say x, and internally calls f(floor(x)) and f(ceil(x)) and returns an interpolated result. Then find the root of that wrapper function.

James Tursa

Jim Rockford <jim.rockford1@gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b@l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important).  What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs.  Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1.  Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
> 
> SUMMARY
>   I need the integer k such that  f(k)*f(k+1) < 0
> 
> Is there some sort of bracketing algorithm in Matlab to do this?
> 
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.
> 
> Thanks,
> Jim

Why won't bisection work, until the interval is reduced
to 1 unit in length?

If you don't have a bracket on the interval, then you
can extrapolate two points until you do have a bracket
on the "root", then apply bisection.

For example, find x such that sqrt(x) - 37 = 0

fofx = @(x) sqrt(x) - 37;

fofx(1)
ans =
   -36

fofx(2)
ans =
         -35.5857864376269

fofx(4)
ans =
   -35

Keep going, until you reach these points...

fofx(1024)
ans =
    -5

fofx(2048)
ans =
          8.25483399593904

So we have a bracket. Now use bisection.

fofx(1536)
ans =
          2.19183588453085

Eventually, we will arrive at fofx(1369) == 0.

John