incremental algorithm for a/(b+c*sqrt(x)) ?

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Ray Andrak » Fri, 06 Feb 2004 14:11:07



Hi folks,

My turn to ask for help.  My library is still packed up in
boxes (just moved), so I can't really paw through my books
at the moment.  Does anyone happen to know if there is an
incremental solution for r(x) given x=0,1,2,3,4.... and  a,
b, and c are static parameters?  I'm looking for a solution
that maps nicely into hardware that hopefully isn't much
more than some adds and perhaps a multiply.  The variable x
starts at 0 and increments, so an iterative solution that
uses the previous result and some delta function is
sufficient.

r(x) =  a/ (b + c*sqrt(x)).

r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

is what I am looking for.

This is for hardware that has to produce a new point every
clock at 120+ MHz, so the algorithm can't be very complex.
The solution seems like it shouldn't be difficult, but my
algebra is failing me miserably.

My standby is to approximate the function with a quadratic
and use a cascaded of four accumulators, but the problem is
in fitting the quadratic to the parameters reasonably
quickly.

Any pointers are greatly appreciated, thanks!

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950

http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin
Franklin, 1759

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Terje Mathise » Fri, 06 Feb 2004 17:46:42



> Hi folks,

> My turn to ask for help.  My library is still packed up in
> boxes (just moved), so I can't really paw through my books
> at the moment.  Does anyone happen to know if there is an
> incremental solution for r(x) given x=0,1,2,3,4.... and  a,
> b, and c are static parameters?  I'm looking for a solution
> that maps nicely into hardware that hopefully isn't much
> more than some adds and perhaps a multiply.  The variable x
> starts at 0 and increments, so an iterative solution that
> uses the previous result and some delta function is
> sufficient.

> r(x) =  a/ (b + c*sqrt(x)).

> r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

> is what I am looking for.

Hmmm. That's a seriously non-linear function, it starts as the constant
a/b and ends up close to a/c * (1/sqrt(x)). Both end-points are easy,
but as long as b is within some orders of magnitude of c*sqrt(x), it
would seem like a hard problem.

Since you want to run this more or less indefinitely, you cannot use
pure extrapolation, you require some form which is self-correcting, right?

Quote:> This is for hardware that has to produce a new point every
> clock at 120+ MHz, so the algorithm can't be very complex.
> The solution seems like it shouldn't be difficult, but my
> algebra is failing me miserably.

> My standby is to approximate the function with a quadratic
> and use a cascaded of four accumulators, but the problem is
> in fitting the quadratic to the parameters reasonably
> quickly.

How much of a setup time do you have, i.e. from the time a, b, c is
known until you have to start producing answers?

Could you combine an approximate (fast) quadratic, with a parallel
circuit which does the full calculation for every N x value?

I.e. by the time you have delivered N-1 extrapolated/approximated
results, the new exact starting point is known?

Quote:> Any pointers are greatly appreciated, thanks!

Good luck!

Terje

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Ray Andrak » Sat, 07 Feb 2004 00:13:50


Terje,

Thanks for your response.  It actually only needs to run for x=0 to 4095,  I'm
not privy to the range of the parameters b and c, but they are within an order
of magnitude or two.  Runs have to be more or less back to back, but typically
they reuse the same function for 40-50 runs before updating the parameters.
Right now, the plan is to use a very simple microprocessor (ala 8051) to do
the set-up, and some dedicated hardware to do the run.

That equation is actually an approximation (I'm still trying to find out to
what function) .  My thought is to fit either a quadratic or a cubic curve and
use a set of accumulators to produce that curve rather than attempting to
reproduce this harder function.  I wanted to find out, however, if there was
something out there to use the existing equation to avoid having the refit all
the data.

Perhaps the parallel computation to make a correction might do it.  Thanks
again.



> > Hi folks,

> > My turn to ask for help.  My library is still packed up in
> > boxes (just moved), so I can't really paw through my books
> > at the moment.  Does anyone happen to know if there is an
> > incremental solution for r(x) given x=0,1,2,3,4.... and  a,
> > b, and c are static parameters?  I'm looking for a solution
> > that maps nicely into hardware that hopefully isn't much
> > more than some adds and perhaps a multiply.  The variable x
> > starts at 0 and increments, so an iterative solution that
> > uses the previous result and some delta function is
> > sufficient.

> > r(x) =  a/ (b + c*sqrt(x)).

> > r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

> > is what I am looking for.

> Hmmm. That's a seriously non-linear function, it starts as the constant
> a/b and ends up close to a/c * (1/sqrt(x)). Both end-points are easy,
> but as long as b is within some orders of magnitude of c*sqrt(x), it
> would seem like a hard problem.

> Since you want to run this more or less indefinitely, you cannot use
> pure extrapolation, you require some form which is self-correcting, right?

> > This is for hardware that has to produce a new point every
> > clock at 120+ MHz, so the algorithm can't be very complex.
> > The solution seems like it shouldn't be difficult, but my
> > algebra is failing me miserably.

> > My standby is to approximate the function with a quadratic
> > and use a cascaded of four accumulators, but the problem is
> > in fitting the quadratic to the parameters reasonably
> > quickly.

> How much of a setup time do you have, i.e. from the time a, b, c is
> known until you have to start producing answers?

> Could you combine an approximate (fast) quadratic, with a parallel
> circuit which does the full calculation for every N x value?

> I.e. by the time you have delivered N-1 extrapolated/approximated
> results, the new exact starting point is known?

> > Any pointers are greatly appreciated, thanks!

> Good luck!

> Terje

> --

> "almost all programming can be viewed as an exercise in caching"

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950

http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Raymond To » Sat, 07 Feb 2004 02:00:12


    Ray> Thanks for your response.  It actually only needs to run for x=0 to 4095,  I'm
    Ray> not privy to the range of the parameters b and c, but they are within an order
    Ray> of magnitude or two.  Runs have to be more or less back to back, but typically
    Ray> they reuse the same function for 40-50 runs before updating the parameters.
    Ray> Right now, the plan is to use a very simple microprocessor (ala 8051) to do
    Ray> the set-up, and some dedicated hardware to do the run.

How about writing the equation as 1/(b/a+c/a*sqrt(x)).  Then keep
sqrt(x) in a 4096-element table.  Can you afford a multiply, an add,
and a reciprocal?  Of course, you'll have to precompute b/a and c/a,
but that's only once per run.

Ray

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Ray Andrak » Sat, 07 Feb 2004 02:26:58


Memory is at a high premium, otherwise I would just have the microprocessor fill the memory
with the function directly.  Reciprocal and square root are expensive functions in
hardware, which is why I was looking for something that would work as an incremental
function where I would take the previous output and some delta function to get the next
output.



>     Ray> Thanks for your response.  It actually only needs to run for x=0 to 4095,  I'm
>     Ray> not privy to the range of the parameters b and c, but they are within an order
>     Ray> of magnitude or two.  Runs have to be more or less back to back, but typically
>     Ray> they reuse the same function for 40-50 runs before updating the parameters.
>     Ray> Right now, the plan is to use a very simple microprocessor (ala 8051) to do
>     Ray> the set-up, and some dedicated hardware to do the run.

> How about writing the equation as 1/(b/a+c/a*sqrt(x)).  Then keep
> sqrt(x) in a 4096-element table.  Can you afford a multiply, an add,
> and a reciprocal?  Of course, you'll have to precompute b/a and c/a,
> but that's only once per run.

> Ray

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950

http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by glen herrmannsfeld » Sat, 07 Feb 2004 07:46:58



> My turn to ask for help.  My library is still packed up in
> boxes (just moved), so I can't really paw through my books
> at the moment.  Does anyone happen to know if there is an
> incremental solution for r(x) given x=0,1,2,3,4.... and  a,
> b, and c are static parameters?  I'm looking for a solution
> that maps nicely into hardware that hopefully isn't much
> more than some adds and perhaps a multiply.  The variable x
> starts at 0 and increments, so an iterative solution that
> uses the previous result and some delta function is
> sufficient.

> r(x) =  a/ (b + c*sqrt(x)).

> r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

> is what I am looking for.

My first thought on reading this was to wonder if it
could be a homework problem.  Then I saw who posted it.

You don't say how many bits of precision and/or accuracy
you require.  Fixed or floating point?

If you are doing this with an FPGA with block RAM there
could be lots of possibilities using that RAM.  A successive
approximation algorithm, pipelined so that one result can
come out each cycle, even if it takes more than one cycle
to compute each should be possible.

Quote:> This is for hardware that has to produce a new point every
> clock at 120+ MHz, so the algorithm can't be very complex.
> The solution seems like it shouldn't be difficult, but my
> algebra is failing me miserably.
> My standby is to approximate the function with a quadratic
> and use a cascaded of four accumulators, but the problem is
> in fitting the quadratic to the parameters reasonably
> quickly.

Or a higher order polynomial.   I would start by considering
the iterative algorithms used to do divide on pipelined
processors, which are well described in some of the pipelined
computer architecture books from some years ago.  The IBM
360/91 and Cray-1 are the two favorite examples.   Those
algorithms converge quadratically (twice the digits each
cycle) so they might answer this problem pretty well.

Do you have a reasonable sized FPGA available to do this?

-- glen

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Ray Andrak » Sat, 07 Feb 2004 08:29:53


Glen,

It is a space application, so depending on the results and timing
of qual testing we are either in an XCV1000 or an XC2V3000.  This
is actually a pretty small portion of the entire algorithm.  The
prototype, which did not have this part of the algorithm fit into
an XCV1000, but requires all of the memory for a 4k point
FFT/IFFT.  If, in the likely event that we are stuck with the
XCV1000, then we don't have much room to work with . The floorplan
of the prototype is on my website gallery
(http://www.andraka.com/wsoa.htm).  If we are fortunate enough to
be able to use the XC2V3000, then using memory becomes a viable
option, and then things like successive approximation or newton's
method become possibilities. We're talking 15-17 bits precision
here with matching accuracy.

I have looked at using some of the division routines, but have not
come up with a simple extension to this yet.  I'm hoping that the
systems guys will let us go with fitting a polynomial to the curve
instead so that I can get away with a set of cascaded
accumulators.  So far, though, they haven't been to open to
changes.



> > My turn to ask for help.  My library is still packed up in
> > boxes (just moved), so I can't really paw through my books
> > at the moment.  Does anyone happen to know if there is an
> > incremental solution for r(x) given x=0,1,2,3,4.... and  a,
> > b, and c are static parameters?  I'm looking for a solution
> > that maps nicely into hardware that hopefully isn't much
> > more than some adds and perhaps a multiply.  The variable x
> > starts at 0 and increments, so an iterative solution that
> > uses the previous result and some delta function is
> > sufficient.

> > r(x) =  a/ (b + c*sqrt(x)).

> > r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

> > is what I am looking for.

> My first thought on reading this was to wonder if it
> could be a homework problem.  Then I saw who posted it.

> You don't say how many bits of precision and/or accuracy
> you require.  Fixed or floating point?

> If you are doing this with an FPGA with block RAM there
> could be lots of possibilities using that RAM.  A successive
> approximation algorithm, pipelined so that one result can
> come out each cycle, even if it takes more than one cycle
> to compute each should be possible.

> > This is for hardware that has to produce a new point every
> > clock at 120+ MHz, so the algorithm can't be very complex.
> > The solution seems like it shouldn't be difficult, but my
> > algebra is failing me miserably.

> > My standby is to approximate the function with a quadratic
> > and use a cascaded of four accumulators, but the problem is
> > in fitting the quadratic to the parameters reasonably
> > quickly.

> Or a higher order polynomial.   I would start by considering
> the iterative algorithms used to do divide on pipelined
> processors, which are well described in some of the pipelined
> computer architecture books from some years ago.  The IBM
> 360/91 and Cray-1 are the two favorite examples.   Those
> algorithms converge quadratically (twice the digits each
> cycle) so they might answer this problem pretty well.

> Do you have a reasonable sized FPGA available to do this?

> -- glen

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950

http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

 
 
 

incremental algorithm for a/(b+c*sqrt(x)) ?

Post by Ray Andrak » Sat, 07 Feb 2004 09:05:39


I should clarify.  If we are stuck with XCV1000's we are going with
two chips, which will free up some CLB resources, but the memory is
more than accounted for still.  The large areas in the prototype
floorplan are buffers made out of CLB resources because of the lack of
memory.  We do have quite a bit more processing to do than the
prototype had, and my current estimates have us fairly well utilized,
70+%.  I am very much hoping that we can get the XC2V3000's (these are
actually the mil rad *es, I just don't remember the number)
through qual early enough to be able to use them.

SO you can see I am in a bit of a pickle here.  Not much room for an
added function that the systems guys thought was something easy to
do.  Hence my search for simple ways to do it.  The square root thing
is an approximation in the first place, so personally I don't see why
we couldn't fit a polynomial instead.  Anyway, I just need to convice
the systems guys that it would be a good thing.  Your input, as well
as others I have gotten helps to bolster my argument, as well as
provide me additional ideas should I not be allowed the polynomial
route.  Thanks again.


> Glen,

> It is a space application, so depending on the results and timing
> of qual testing we are either in an XCV1000 or an XC2V3000.  This
> is actually a pretty small portion of the entire algorithm.  The
> prototype, which did not have this part of the algorithm fit into
> an XCV1000, but requires all of the memory for a 4k point
> FFT/IFFT.  If, in the likely event that we are stuck with the
> XCV1000, then we don't have much room to work with . The floorplan
> of the prototype is on my website gallery
> (http://www.veryComputer.com/).  If we are fortunate enough to
> be able to use the XC2V3000, then using memory becomes a viable
> option, and then things like successive approximation or newton's
> method become possibilities. We're talking 15-17 bits precision
> here with matching accuracy.

> I have looked at using some of the division routines, but have not
> come up with a simple extension to this yet.  I'm hoping that the
> systems guys will let us go with fitting a polynomial to the curve
> instead so that I can get away with a set of cascaded
> accumulators.  So far, though, they haven't been to open to
> changes.



> > > My turn to ask for help.  My library is still packed up in
> > > boxes (just moved), so I can't really paw through my books
> > > at the moment.  Does anyone happen to know if there is an
> > > incremental solution for r(x) given x=0,1,2,3,4.... and  a,
> > > b, and c are static parameters?  I'm looking for a solution
> > > that maps nicely into hardware that hopefully isn't much
> > > more than some adds and perhaps a multiply.  The variable x
> > > starts at 0 and increments, so an iterative solution that
> > > uses the previous result and some delta function is
> > > sufficient.

> > > r(x) =  a/ (b + c*sqrt(x)).

> > > r(x+1) = a/(b + c*sqrt(x+1))  = r(x)+f(x,dx) or r(x)*f(x,dx)

> > > is what I am looking for.

> > My first thought on reading this was to wonder if it
> > could be a homework problem.  Then I saw who posted it.

> > You don't say how many bits of precision and/or accuracy
> > you require.  Fixed or floating point?

> > If you are doing this with an FPGA with block RAM there
> > could be lots of possibilities using that RAM.  A successive
> > approximation algorithm, pipelined so that one result can
> > come out each cycle, even if it takes more than one cycle
> > to compute each should be possible.

> > > This is for hardware that has to produce a new point every
> > > clock at 120+ MHz, so the algorithm can't be very complex.
> > > The solution seems like it shouldn't be difficult, but my
> > > algebra is failing me miserably.

> > > My standby is to approximate the function with a quadratic
> > > and use a cascaded of four accumulators, but the problem is
> > > in fitting the quadratic to the parameters reasonably
> > > quickly.

> > Or a higher order polynomial.   I would start by considering
> > the iterative algorithms used to do divide on pipelined
> > processors, which are well described in some of the pipelined
> > computer architecture books from some years ago.  The IBM
> > 360/91 and Cray-1 are the two favorite examples.   Those
> > algorithms converge quadratically (twice the digits each
> > cycle) so they might answer this problem pretty well.

> > Do you have a reasonable sized FPGA available to do this?

> > -- glen

> --
> --Ray Andraka, P.E.
> President, the Andraka Consulting Group, Inc.
> 401/884-7930     Fax 401/884-7950

> http://www.veryComputer.com/

>  "They that give up essential liberty to obtain a little
>   temporary safety deserve neither liberty nor safety."
>                                           -Benjamin Franklin, 1759

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950

http://www.veryComputer.com/

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759