Sqrt operation for bit widths bigger than 32

    Hello Community,


    in my recent work I got a Problem: Sqrt for values bigger than 32 Bit.

    Just shifting right with a hard coded number of Bits is not a good idea, since there may be small Values observed, too.


    I want to share my solution I came up with.


    What the design does:

    1. Check which set bit's number is the most significant
    2. Shift dynamically to the right -> "Anti fractional Bits", they have to be an even number, as the sqrt operation divides them by two
    3. Perform the sqrt operation on the shifted value
    4. Shift left by the "Anti fractional Bits" divided by two


    Pro:

    • High precision

    Con:

    • Extremely Expensive

    It's just like the poor man's floating point

    Please feel free to comment - maybe there is some ability to improve this.


    Best regards

    Simon

    Hello,


    I did some optimization:

    • As the sqrt operation only allows shift-increments by two, the adaptive shift operations can be done with 16 cases and not 32
    • The "highest bit set" logic can be done via combinatoric logic

    This leads to the following improvements:

    Old New
    LUT 1218 789
    Flip Flop 218 105


    Best regards

    Simon