floating point aritha matic square root models vhdl/fpga

Discussion in 'The Projects Forum' started by alex warne, Feb 11, 2012.

  1. alex warne

    Thread Starter New Member

    Feb 10, 2012
    13
    0
    hi guys,
    i am a new user of this great site . i want to know which is the best model for the floating point square root model according to less area ,clock cycles and efficiency. ?
     
  2. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Probably your question is too broad to have one answer, but if you are dealing with IEEE floating point representations, I think this article mentions one of the best approaches for square root and reciprocal square root. At work, I have a paper on the reciprocal square root which I can post when I get back to work on Monday, I was amazed at just how efficient and fast this algorithm is.

    http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
     
  3. alex warne

    Thread Starter New Member

    Feb 10, 2012
    13
    0
    hi thank you for your reply steveb. i am using IEEE standard floating method . buti have not understand how to get or form the model with respect to the given method which you have showed in wiki. i need some help in this process.
    thank you
     
  4. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    You need to clarify which aspects are giving you trouble. The article gives a pretty good description and even gives some example code.

    There are two aspects to the computation. The first part involves the very efficient method to calculate an approximate answer to the square root (or the inverse square root could be considered). That step involves taking the IEEE single precision float value and using it in integer form. A simple calculation is then performed to take the log, and it involves bit shifting to divide by two 23 times and then subtraction of 127. Then divide that answer by two and convert back using the inverse algorithm (add 127 and bit shift back up). Clearly these operations are very efficient.

    The above part gives you an approximate answer. If this approximation is not good enough, you can implement Newtons method and use the above estimate as the first guess in the interations. Since, the first guess is already pretty good and since Newton's method converges well for this problem, very few iteration (hence relatively few calculations) are needed to get better and better accuracy.

    So, which part is giving you trouble? Is it the above descritpion, or the Newton's method that must follow, and which is not so well described by the article?

    If it is the latter part, you need to research Newton's method. Implementation of Newton's method for square root or inverse square root is relatively straight forward if you know the method.

    http://en.wikipedia.org/wiki/Newton's_method

    http://mathworld.wolfram.com/NewtonsMethod.html

    If you need double precision calculations, you could first cast the "double" into a standard "float" and then use the above algorithm to get a good single precision estimate of the answer. Then implement a double precision version of Newton's method again, using the single precision estimate as the first guess. This should converge very quickly.
     
  5. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    steveb, I would be interested in seeing that paper. I always promote the use of integer arithmetic over floating point. As an example, I have written a log function in assembler that is very efficient using shift operations.

    I have also written a program in asm in very little code space that calculates dewpoint to two decimal places.
     
  6. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I've attached a pdf of the paper.

    I definitely understand your point, and generally feel the same way. I can't say I always promote the use of integer math, but most of the time I do. There are times when double precision math is needed and at some point implementation with integer math becomes too cumbersome and unmaintainable. However, I expect that you are thinking about the types of systems we deal with mostly in this forum. Sensor/measurement systems, or simple control feedback systems generally are better implemented with integer math, for many different reasons.

    One thing many people don't realize is that a 32 bit integer fundamentally has more precision than a 32 bit float, since one full byte more is available for representing the mantissa. So, for some calculations (simple calculations that involve numbers of the same order of magnitude) you give up both speed and precision when you do floating point math. Other times, you only give up speed because the limitations of fixed point integers cause loss of some of those extra bits.

    The exception I've found to the above rule has become very relevant in work I do nowadays. With very complex control systems, the use of double precision math becomes the most cost effective approach that minimizes development time, has lower chance of bugs after validation with simulations and results in a more maintainable system that can be upgraded/modified by others in the future. The availability of low cost DSP and processors that do double precision floating point calculations quickly is the real game-changer. There is a minimum level of system complexity that would justify playing this game, but for some projects, the attempt to use integer math would be doomed to failure, or would at least result in higher project cost with greater risk of bugs. When one choses this path, the final hardware cost is probably significantly higher, but often the reliability, the development cost and the ongoing maintenance cost must be factored in.
     
    Last edited: Feb 15, 2012
  7. alex warne

    Thread Starter New Member

    Feb 10, 2012
    13
    0
    hi steveb. using newton method will be a disadvantgae because it covers lot of area and more no of cycles.
     
  8. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    "More" compared to what? Do you have another method as a benchmark? Have you done the implementations to make the comparison?

    As I mentioned, your question is too broad to have one answer. Of course there are advantages and disadvantages to the various known methods. You have to look at your requirements and make these trade-offs.
     
  9. alex warne

    Thread Starter New Member

    Feb 10, 2012
    13
    0
    hi steveb
    i have done some implementations.some designs cover more area and uses less clock cycles and some designs more clock cycles and covers less area. but now i am searching for a hardware design or model which i can implement in structurtal design style in vhdl.
     
  10. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Ah, OK. Your problem is clearer now. I didn't realize that you were focusing on a hardware implementation. Now your references to "area" are making sense to me. That sounds like an interesting problem.

    Do you have any specifications for accuracy? Are there any other specifications that constrain the problem? It's important to know all requirements before the best method can be selected.

    If you only need an approximate answer, the problem is easier. However, if you need full precision (I'm assuming you are dealing with 32 bit floats, which is single precision) with all bits accurate, the problem is more challenging. If you are needing 64 bit double precision floating point represetntations, that is even more difficult.
     
  11. alex warne

    Thread Starter New Member

    Feb 10, 2012
    13
    0
    hi steveb. now i am dealing with 32 bit floating point.later i will try for double precision or 64 bit. accuracy means in the structural program has to contains less cycles example load, store or rounding the bits like that and using less area or components like for hardware implementation. so i am searching for it. first i will implement on FPGA. later further implementation will be done.
     
Loading...