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 email ray@andraka.com 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)) ?
Started by ●February 4, 2004
Reply by ●February 5, 20042004-02-05
Am Wed, 04 Feb 2004 20:15:25 -0500 schrieb Ray Andraka:> 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!Hi Ray, I think, an exact recursion formula will not work here, because both possible forms will contain terms like sqrt(x) and sqrt(x+1). But what we can do is an approximation. I tried the following: express sqrt(x+1) by sqrt(x) (for x>0) by a finite Taylor series expansion at evaluation point x. let s(x)=sqrt(x), then s(x+1) = s(x) + 1/(2*s(x)) - 1/(8*s(x)^3) + 1/(16*s(x)^5) -... Store the values s(0)=0, s(1)=1 and use this recursion starting from x=1. Then we can express your problem using this recursion: r(x)=a'/(1+c'*s(x)) with constants a'=a/b, c'=c/b r(0)=a' s(0)=0 r(1)=a'/(1+c') s(1)=1 and starting recursion with x=1: s(x+1) = s(x) + 1/(2*s(x)) - 1/(8*s(x)^3) + 1/(16*s(x)^5) r(x+1)=a'/(1+c'*s(x+1)) An example with a'=1 and c'=1,7 worked well. For x=0..50, the maximum error is 0.0017 (at x=4). At x=50 the error is <6e-5. Hope this helps. Siegbert
Reply by ●February 5, 20042004-02-05
Am Thu, 5 Feb 2004 22:19:22 +0100 schrieb Siegbert Steinlechner:> Am Wed, 04 Feb 2004 20:15:25 -0500 schrieb Ray Andraka: > >> 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! > > Hi Ray, > > I think, an exact recursion formula will not work here, because both > possible forms will contain terms like sqrt(x) and sqrt(x+1). > But what we can do is an approximation. I tried the following: express > sqrt(x+1) by sqrt(x) (for x>0) by a finite Taylor series expansion at > evaluation point x. > > let s(x)=sqrt(x), then > s(x+1) = s(x) + 1/(2*s(x)) - 1/(8*s(x)^3) + 1/(16*s(x)^5) -... > Store the values s(0)=0, s(1)=1 and use this recursion starting from x=1. > Then we can express your problem using this recursion: > > r(x)=a'/(1+c'*s(x)) with constants a'=a/b, c'=c/b > > r(0)=a' s(0)=0 > r(1)=a'/(1+c') s(1)=1 > and starting recursion with x=1: > s(x+1) = s(x) + 1/(2*s(x)) - 1/(8*s(x)^3) + 1/(16*s(x)^5) > r(x+1)=a'/(1+c'*s(x+1)) > > An example with a'=1 and c'=1,7 worked well. For x=0..50, the maximum error > is 0.0017 (at x=4). At x=50 the error is <6e-5. > > Hope this helps. > SiegbertHer is another solution: an exact rekursion, but not in the form you mentioned. This recursion comes out from the solution of a quadratic equation. I got this equation when I solved r(x) = a'/ (1 + c'*sqrt(x)) for sqrt(x) and r(x+1) = a'/ (1 + c*sqrt(x+1)) for sqrt(1+x). Then we square both equations and take the difference. This yields two solutions (but only one is the right one): r(x + 1) = - ((a' * r(x) * sqrt((c'^2 + 1) * r^2(x) - 2 * a' * r(x) + a'^2) + a' * r^2(x))/(c'^2 * r^2(x) - 2 * a' * r(x) + a'^2)) or r(x + 1) = ((a' * r(x) * sqrt((c^2 + 1) * r^2(x) - 2 * a' * r(x) + a'^2) - a' * r^2(x))/(c'^2 * r^2(x) - 2 * a' * r(x) + a'^2))] But I think, your hardware will not like the square root... Siegbert
Reply by ●February 5, 20042004-02-05
Thank you so much for the reply. I'm starting to see that this does not have a simple solution. The exact recursion with the square root doesn't work very well with hardware as you suspected. The other looks workable, so I am going to look closer at it. The hardware still does not look very simple, but after spending quite a bit of time looking at it, it is becoming apparent that there is probably not a simpler solution. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759
Reply by ●February 6, 20042004-02-06
Hi Ray, have you seen the single-cycle square root scheme by QSigma of San Jose, Calif.? There's info at: http://www.findarticles.com/cf_dls/m3161/25_50/94894254/p1/article.jhtml Just thought I'd mention it. [-Rick-] ------------------------------------------ On Thu, 05 Feb 2004 17:36:40 -0500, Ray Andraka <ray@andraka.com> wrote:>Thank you so much for the reply. I'm starting to see that this does not have >a simple solution. The exact recursion with the square root doesn't work very >well with hardware as you suspected. The other looks workable, so I am going >to look closer at it. The hardware still does not look very simple, but after >spending quite a bit of time looking at it, it is becoming apparent that there >is probably not a simpler solution. > >-- >--Ray Andraka, P.E. >President, the Andraka Consulting Group, Inc. >401/884-7930 Fax 401/884-7950 >email ray@andraka.com >http://www.andraka.com > > "They that give up essential liberty to obtain a little > temporary safety deserve neither liberty nor safety." > -Benjamin Franklin, 1759 > >
Reply by ●February 6, 20042004-02-06
r.lyons@_BOGUS_ieee.org (Rick Lyons) writes:> Hi Ray, > > have you seen the single-cycle square root > scheme by QSigma of San Jose, Calif.? There's > info at: > > http://www.findarticles.com/cf_dls/m3161/25_50/94894254/p1/article.jhtml > > Just thought I'd mention it. > > [-Rick-]Rick, This sounds impossible, at least not without using large lookup tables. Any insight? (I couldn't get any reading the link you provided - that "cluster" idea didn't make much sense.) --Randy> > ------------------------------------------ > On Thu, 05 Feb 2004 17:36:40 -0500, Ray Andraka <ray@andraka.com> > wrote: > >>Thank you so much for the reply. I'm starting to see that this does not have >>a simple solution. The exact recursion with the square root doesn't work very >>well with hardware as you suspected. The other looks workable, so I am going >>to look closer at it. The hardware still does not look very simple, but after >>spending quite a bit of time looking at it, it is becoming apparent that there >>is probably not a simpler solution. >> >>-- >>--Ray Andraka, P.E. >>President, the Andraka Consulting Group, Inc. >>401/884-7930 Fax 401/884-7950 >>email ray@andraka.com >>http://www.andraka.com >> >> "They that give up essential liberty to obtain a little >> temporary safety deserve neither liberty nor safety." >> -Benjamin Franklin, 1759 >> >> >-- % Randy Yates % "How's life on earth? %% Fuquay-Varina, NC % ... What is it worth?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://home.earthlink.net/~yatescr
Reply by ●February 6, 20042004-02-06
The article in the link is not really complete enough for an evaluation, but it appears that perhaps he is not including the conversion to and from log space in his single cycle claim. With a log number system, square root is just a shift. The cluster thing looks like perhaps an approach to doing the log conversions, although it is not clear what he is doing from this brief abstract. He may have worked out something by using superposition of bit pairs for a specific function, but you can't tell from the article. Randy Yates wrote:> r.lyons@_BOGUS_ieee.org (Rick Lyons) writes: > > > Hi Ray, > > > > have you seen the single-cycle square root > > scheme by QSigma of San Jose, Calif.? There's > > info at: > > > > http://www.findarticles.com/cf_dls/m3161/25_50/94894254/p1/article.jhtml > > > > Just thought I'd mention it. > > > > [-Rick-] > > Rick, > > This sounds impossible, at least not without using large lookup tables. Any > insight? (I couldn't get any reading the link you provided - that "cluster" > idea didn't make much sense.) > > --Randy > > > > > ------------------------------------------ > > On Thu, 05 Feb 2004 17:36:40 -0500, Ray Andraka <ray@andraka.com> > > wrote: > > > >>Thank you so much for the reply. I'm starting to see that this does not have > >>a simple solution. The exact recursion with the square root doesn't work very > >>well with hardware as you suspected. The other looks workable, so I am going > >>to look closer at it. The hardware still does not look very simple, but after > >>spending quite a bit of time looking at it, it is becoming apparent that there > >>is probably not a simpler solution. > >> > >>-- > >>--Ray Andraka, P.E. > >>President, the Andraka Consulting Group, Inc. > >>401/884-7930 Fax 401/884-7950 > >>email ray@andraka.com > >>http://www.andraka.com > >> > >> "They that give up essential liberty to obtain a little > >> temporary safety deserve neither liberty nor safety." > >> -Benjamin Franklin, 1759 > >> > >> > > > > -- > % Randy Yates % "How's life on earth? > %% Fuquay-Varina, NC % ... What is it worth?" > %%% 919-577-9882 % 'Mission (A World Record)', > %%%% <yates@ieee.org> % *A New World Record*, ELO > http://home.earthlink.net/~yatescr-- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759
Reply by ●February 6, 20042004-02-06
Ray Andraka <ray@andraka.com> wrote in message news:<4023B77D.3CC9487D@andraka.com>...> The article in the link is not really complete enough for an evaluation, but it > appears that perhaps he is not including the conversion to and from log space in his > single cycle claim. With a log number system, square root is just a shift. The > cluster thing looks like perhaps an approach to doing the log conversions, although > it is not clear what he is doing from this brief abstract. He may have worked out > something by using superposition of bit pairs for a specific function, but you can't > tell from the article. > > Randy Yates wrote: >Hi Ray, The paper in the following link discusses the design of a high-speed logarithmic multiplier. You may be able to use the logarithm and anti-logarithm algorithms discussed in the paper to implement the square root and division operations involved in your function. http://www.cadence.com/whitepapers/IEEESoCConference2003-Logr.pdf Hope this helps Jitendra
Reply by ●February 6, 20042004-02-06
On Fri, 06 Feb 2004 13:29:46 GMT, Randy Yates <yates@ieee.org> wrote:>r.lyons@_BOGUS_ieee.org (Rick Lyons) writes: > >> Hi Ray, >> >> have you seen the single-cycle square root >> scheme by QSigma of San Jose, Calif.? There's >> info at: >> >> http://www.findarticles.com/cf_dls/m3161/25_50/94894254/p1/article.jhtml >> >> Just thought I'd mention it. >> >> [-Rick-] > >Rick, > >This sounds impossible, at least not without using large lookup tables. Any >insight? (I couldn't get any reading the link you provided - that "cluster" >idea didn't make much sense.) > >--Randy >Hi Randy, I saw the QSigma article in Electronic Design magazine. It caught my eye, so I tore the page out and stuck it in my files. But when I went to the QSigma website today, it was unbelievably amateurish!! I'd be very cautious at this point. [-Rick-]
Reply by ●February 11, 20042004-02-11
Ray,
Not sure if this is useful, but there is a simple way of computing
the integer value of sqrt(x) if you know that x=0,1,2,...
1. Let x=0, x2 = 0, y = 0.
2. Compute p = x - x2. q = 2*y+1.
3. If p = q,
y = y + 1.
x2 = x.
4. x = x + 1.
5. Repeat from 2.
For example:
x x2 p = x - x2 q = 2*y+1 y
------ ------ ------------- ---------- ------
0 0 0 0 0
1 0 1 1 1 (p == q)
2 1 1 3 1
3 1 2 3 1
4 1 3 3 2 (p == q)
5 4 1 5 2
6 4 2 5 2
7 4 3 5 2
8 4 4 5 2
9 4 5 5 3 (p == q)
10 9 1 7 3
This algorithm is based on the idea of using successive approximations
when computing sqrt(x):
Let's say we need to find y = sqrt(x).
Then we can say y^2 = x.
Let y_ be an estimate of y. We will add a value N to y_ until it is
equal to the true value of y. A way to check if y_ = y is to look
at the difference (y_ + N)^2 - y_^2:
delta = (y_ + N) ^ 2 - y_ ^ 2 = 2 * N * y_ + 1
----------------------------------------------
If we start from a known value of
y_ = sqrt(x0),
adding N to y_ will add delta to x0, so that
y_ + N = sqrt(x0 + delta)
If (x0 + delta) still doesn't equal the given value of x, add N one
more time:
y_ + N + N2 = sqrt(x0 + delta + delta2)
And so on.
N is normally a decreasing power of 2, but in our case it can always
be one. So:
delta = 2 * y_ + 1
This case is particularly interesting because it's a simple (but not
necessarily fast) algorithm of computing sqrt(x): "integer sqrt(x)
equals the number of odd integers starting from one, the sum of which
equals x".
For example:
sqrt(1 + 3) = 2
sqrt(1 + 3 + 5) = 3
sqrt(1 + 3 + 5 + 7) = 4
...
Hope that helps.
Nikolai
