src/add/fsqrt.py

   1 def sqrt(num):
   2     """
   3     res = 0
   4     bit = 1 << 14
   5
   6     while (bit > num):
   7         bit >>= 2
   8
   9     while (bit != 0):
  10         if (num >= res + bit):
  11             num -= res + bit
  12             res = (res >> 1) + bit
  13         else:
  14             res >>= 1
  15         bit >>= 2
  16
  17     return res
  18     """
  19     r = None
  20     D = None
  21     Q = 0
  22     R = 0
  23     for i in range(15):
  24         i -= 1
  25
  26         if (R>=0):
  27
  28             R = (R<<2)|((D>>(i+i))&3)
  29             R = R-((Q<<2)|1) #/*-Q01*/
  30
  31         else:
  32
  33             R = (R<<2)|((D>>(i+i))&3)
  34             R = R+((Q<<2)|3) #/*+Q11*/
  35
  36         if (R>=0):
  37             Q = (Q<<1)|1 #/*new Q:*/
  38         else:
  39             Q = (Q<<1)|0 #/*new Q:*/
  40
  41
  42     if (R<0):
  43         R = R+((Q<<1)|1)
  44         r = R
  45     return Q
  46
  47
  48 for Q in range(1,20):
  49     print(sqrt(Q))
  50
  51 """
  52 //This is the main code of integer sqrt function found here:http://verilogcodes.blogspot.com/2017/11/a-verilog-function-for-finding-square-root.html
  53 //
  54
  55 module testbench;
  56
  57 reg [15:0] sqr;
  58
  59 //Verilog function to find square root of a 32 bit number.
  60 //The output is 16 bit.
  61 function [15:0] sqrt;
  62     input [31:0] num;  //declare input
  63     //intermediate signals.
  64     reg [31:0] a;
  65     reg [15:0] q;
  66     reg [17:0] left,right,r;
  67     integer i;
  68 begin
  69     //initialize all the variables.
  70     a = num;
  71     q = 0;
  72     i = 0;
  73     left = 0;   //input to adder/sub
  74     right = 0;  //input to adder/sub
  75     r = 0;  //remainder
  76     //run the calculations for 16 iterations.
  77     for(i=0;i<16;i=i+1) begin
  78         right = {q,r[17],1'b1};
  79         left = {r[15:0],a[31:30]};
  80         a = {a[29:0],2'b00};    //left shift by 2 bits.
  81         if (r[17] == 1) //add if r is negative
  82             r = left + right;
  83         else    //subtract if r is positive
  84             r = left - right;
  85         q = {q[14:0],!r[17]};
  86     end
  87     sqrt = q;   //final assignment of output.
  88 end
  89 endfunction //end of Function
  90
  91
  92 c version (from paper linked from URL)
  93
  94 unsigned squart(D, r) /*Non-Restoring sqrt*/
  95     unsigned D; /*D:32-bit unsigned integer to be square rooted */
  96     int *r;
  97 {
  98     unsigned Q = 0; /*Q:16-bit unsigned integer (root)*/
  99     int R = 0; /*R:17-bit integer (remainder)*/
 100     int i;
 101     for (i = 15;i>=0;i--) /*for each root bit*/
 102     {
 103         if (R>=0)
 104         { /*new remainder:*/
 105             R = R<<2)|((D>>(i+i))&3);
 106             R = R-((Q<<2)|1); /*-Q01*/
 107         }
 108         else
 109         { /*new remainder:*/
 110             R = R<<2)|((D>>(i+i))&3);
 111             R = R+((Q<<2)|3); /*+Q11*/
 112         }
 113         if (R>=0) Q = Q<<1)|1; /*new Q:*/
 114         else Q = Q<<1)|0; /*new Q:*/
 115     }
 116
 117     /*remainder adjusting*/
 118     if (R<0) R = R+((Q<<1)|1);
 119     *r = R; /*return remainder*/
 120     return(Q); /*return root*/
 121 }
 122
 123 From wikipedia page:
 124
 125 short isqrt(short num) {
 126     short res = 0;
 127     short bit = 1 << 14; // The second-to-top bit is set: 1 << 30 for 32 bits
 128
 129     // "bit" starts at the highest power of four <= the argument.
 130     while (bit > num)
 131         bit >>= 2;
 132
 133     while (bit != 0) {
 134         if (num >= res + bit) {
 135             num -= res + bit;
 136             res = (res >> 1) + bit;
 137         }
 138         else
 139             res >>= 1;
 140         bit >>= 2;
 141     }
 142     return res;
 143 }
 144
 145 """