Revisiting Square Roots with a Fast Estimator

London Journal of Research in Computer Science and Technology
Volume | Issue | Compilation
Authored by Dr. Anthony Overmars , Dr. Sitalakshmi Venkatraman, Dr. Sazia Parvin
Classification: D.1.0
Keywords: square root, applications, silver ratio, babylonian method, infinite series, optimisation, efficiency.
Language: English

The square root of prime numbers is an important mathematical primitive with wide applications and its computational complexity has drawn much attention among researchers. In particular, principal square root of 2 is known to be irrational.

               

Revisiting Square Roots with a Fast Estimator

Dr. Anthony Overmarsα, Dr. Sitalakshmi Venkatramanσ & Dr. Sazia Parvinρ

____________________________________________

  1. ABSTRACT

The square root of prime numbers is an important mathematical primitive with wide applications and its computational complexity has drawn much attention among researchers. In particular, principal square root of 2 is known to be irrational. The Silver Ratio  is also irrational. These can be approximated by a ratio of rational numbers.

This paper revisits some important applications of square root and proposes a new method to compute square root of 2. The proposed estimator determines the infinite series ratio of rational numbers with infinite precision. The optimised method isolates the simple fractional part and expresses this as a ratio of two rational numbers, such that . We compare the new method with the well known Babylonian method. The experimental results show that our proposed method is efficient and outperforms the Babylonian method in both accuracy and speed.  

Keywords: square root, applications, silver ratio, Babylonian method, infinite series, optimisation,  efficiency.

Author α σ ρ: School of Engineering, Construction & Design, Melbourne Polytechnic, Victoria, Australia.

  1. INTRODUCTION

Square root is one of the most useful and frequently used operations in many different real world applications such as  computer graphics, multimedia, data processing, cryptosystems and many scientific calculation applications [1] [2].  Several mathematical studies have determined that the theoretical complexity of such scientific calculations can be reduced by adding square roots to the basic operations [3]. In particular, square root of 2 and its associated Silver ratio have fascinated mathematicians since ancient times due to their computational complexity and applications in many real-world scenarios including architecture, modern printing, nature, music and even today's information system applications such as security and big data [4].

It is a classical hard problem to get an accurate result for computing square root and methods are available in literature such as Rough estimation, Babylonian method, Taylor-series expansion algorithm and Newton-Raphson method [5].  However, in this information age with mountains of data, applications require improved methods that are sufficiently fast with high precision [6].  Various applications make use of square root of different numbers and understanding their requirements would help in making use of s suitable square root estimator. This paper proposes a new method that we derive for estimating square root with high accuracy. In particular, we show how square root of 2 can be calculated very fast and compare with the well-known Babylonian method. The associated Silver    Ratio is also estimated and discussed.

The remaining paper is organized as follows. Section III provides an overview of the various  real-life applications square root. The proposed method is derived in Sections IV and optimised in Section V.  The Babylonian method is described in  Section VI. Experimental results for benchmarking our proposed method are summarized in Section VII. Finally, we present our conclusions in Section VIII.

  1. SQUARE ROOT APPLICATIONS 

Several real world applications require computing square root and square root of two [7] [1].  The most common application of square root in everyday life is found in standard paper sizes. The base A0 size of paper is defined as having an area of 1 m2 and a side ratio of 1 by √2,. Successive paper sizes in the series A1, A2, A3, and the frequently used A4 paper sizes have a nice property that they are derived by halving the preceding one along the larger dimension.  Similarly, folded brochures of any size can be made by using sheets of the next larger size. For example,  A5 sixe brochures can be made by folding A4 sheets along the length of the paper. The standard system of basing a paper size upon an aspect ratio of √2 has several advantages of not only scaling from one size to but also in fast processing of office photocopiers.

Another real life example of square root is to calculate the interest of saving account. The factor by which the account grows is exponential. This means that if it grows by some factor in a given time, it will grow by the square of that factor in double the time. So, to compute the growth in half the time, square root is used.  

Square roots have been traditionally used to calculate time and distance, such as in the applications of object falling and land area triangulation measurements.  For falling  objects, square root can be used to calculate the time t it takes for something to fall x distance when it is dropped. From Newton's laws with g as acceleration due to gravity, we have,

Similarly. let us consider calculating the period T of a swing that is safe for children amusement park without a fall.  The period of a swing with length L is calculated by the following equation:

In land areas, in order to measure the diagonal of any rectangular space when the dimensions of the sides are known, Pythagorean theorem is usually applied to measure it as the square root of sum of square of the two sides. In this context, the aspect ratio of square root application is even more prominent in today's multimedia world of graphic designs and web designs.  The reciprocal of square root is also an important operation with applications in three-dimensional graphics or scientific computations.

Square root is commonly used to transform data which has applications in computer processors, statistics, big data and information security. It is possible to reduce the theoretical complexity of certain problems by adding square roots to the basic operations in the computer processor. There exists a number of situations in which square roots are used as common transformations, for e.g.  square roots  are computed to be faster than divides.  Similarly, while both the logarithm and square root transformations are commonly used for power transformations of positive data,  the square root is preferred because there is no requirement to use special treatment for zeros. Power transformations have wide applications in big data and information security.  The square roots of small integers are used in both the SHA-1 and SHA-2 hash function designs in cryptosystems to achieve information security [8] [9].  Square roots are used in decryption in order to compute the encrypted text  called the cipher text. If the cipher text c is modulo of the primes p and q, then square roots can be  more easily calculated by choosing q in order to decrypt the message. Hence, the basic step of using square roots in public-key cryptosystems is in decryption where  if the cipher text is given, one can extract the keys using square root. The metallic numbers, namely Golden ratio and Silver ratio have been used extensively in cryptography [10] [11].

In summary, square root is an important mathematical primitive having many applications. Due its computational complexity there are some difficulties to ensure its security and efficiency in distributed computing [12]. Hence, several algorithms have evolved, such as Goldschmidt’s algorithm using linear approximation, Manuel Liedel algorithm through the fixed-point arithmetic framework of Catrina/Saxena. Goldschmidt’s algorithm for square root is preferred over the traditional Newton-Raphson iterations due to faster computation as  iteration contains fewer dependent multiplications with the same computational complexity. In this paper we address the problem of computational complexity by proposing a faster optimised method with high precision. for estimating square roots, in particular square root of two as it has wide applications in the computing field.

  1. PROPOSED METHOD

We consider square root of as an illustration for our proposed method of estimating square roots.  In Fig. 1, we pictorially represent square root as the hypotenuse of a right angled triangle with base and height to be equal of value 1 unit each.

   

Figure 1: Square Root of 2 as a right angle triangle

We now consider the three propositions of representing square root of two as shown in Fig 2. The first proposition increases more rapidly than the others because of the  term. We can re-express this in terms of

Let us now express sides as :

                                                       (1)                                            

This is consistent with Fig. 1. From previous work [13] [14] it can be shown that sides  can be expressed as three Diophantine equations in terms of   where

                                     (2)                                  

                          (3)                                

               (4)                                    

     

Figure 2: Approximations of Square Root of 2

Note the special condition that we specified in proposition:

 

Case (1): Substituting in for :

This gives us the special condition:

                             (5)                  

                                               (6)                              

Solving this gives:

Case (2): Substituting in for :

   

This gives us the special condition:

                                 (7)              

                                                    (8)

Solving this gives: .   is also a solution.

We observe the following:

.

In equation (8) , is true.

Therefore,  the following conjecture holds:    

 

                                                                                                                             (9)       

From equation (1), we have

And equations (2), (3), (4), we get

,

 ,

     

Re-expressing     

         

Substituting the above expressions, we get

 

From equation (1)  

Recalling

Expressing this in terms of  the following, we get

                   (10)

Now using equation (10)

 =

..

..

..

 

   ..

From equations (9) and (10) the results of which are shown in Table 1.

Table 1: Precision per iteration

1

2

3

4

4

120

137904

183648021600

5

169

195025

259717522849

.

2

5

11

24

5

6

325692820333408821261504

1024358667630340232633308608283887388728479963520

460599203683050495415105

1448661920497260706754234635502788141981004285569

.

48

97

V.    OPTIMISING THE METHOD

It can be seen from Table 1 that the decimal accuracy doubles up each iteration and that after the 6th iteration we have an accuracy of 97 decimal places. Since the sides of the triangles are co-prime [13]:  the sides have a gcd(c,b)=1. From equation (10) it can also be shown that     has no common factors and is irreducible.

We now optimise the number of arithmetic operations per iteration for the new method.

Recall equation (9) as follows;

        

We are only concerned with   to determine  and  so only equations (3), (4) are needed.  Recall the following equations:

This can now be optimised to minimise the number of arithmetic operations.  

,

 

,

                                  (11)                                  

                                   (12)                                                                                                

Equation (11) has 5 arithmetic operations and equation (12) has 2 so this is 7 operations per iteration. The final division (costly) is only required in the last calculation, equation (10) which adds further 4 operations. Table 2 summarises the number of operations.

Table 2: Operations per iteration

1

2

3

4

5

6

7

.

2

5

11

24

48

97

?

Ops

11

18

25

32

39

46

53

From table 2 we can approximate the operations per iteration as 7 with a corresponding accuracy of number of decimal digits of precision. Each can be determined without any divisions being required until the last calculation in equation (10).

   

The accuracy can be estimated per operation as:

We can test this with 53 operations and estimate that the accuracy will be  decimal places.

 =192

  1. THE BABYLONIAN METHOD

There are a number of algorithms for approximating √2, which in expressions as a ratio of integers or as a decimal can only be approximated. The most common algorithm that has been used in many computers and calculators is the Babylonian method [15] of computing square roots. In this section, we present the highlights of the Babylonian method for estimating square root of 2.  By choosing, a0 > 0, we iterate through the recursive computation for this method:

Each iteration approximately doubles the number of correct digits. Starting with a0 = 1 the next approximations are:

 =

 =

..

..

           ..

     ..

The results of which are shown in Table 3.

Table 3: Babylonian method - precision per iteration

1

2

3

4

3

17

577

665857

2

12

408

470832

.

1

3

5

11

5

6

886731088897

1572584048032918633353217

627013566048

1111984844349868137938112

.

24

48

Though the divide operation is usually costly, in this case, a division by 2 can be simply implemented with a binary shift left operation of the whole binary number. This usually takes one clock cycle. For Big Integers, this will take longer, but can be efficiently performed using the above method. The divide is very expensive computationally and a simple addition is all that is required to obtain the iteration. So, we have three arithmetic operations per iteration with accuracy as given below:

   

  1. COMPARISON OF RESULTS

The accuracy of our proposed  new method per operation can be estimated as:  as compared to the accuracy of the Babylonian method given by .

The result of operations for our proposed method is  shown in Table 4.

Table 4: Results of proposed method

1

2

3

4

5

6

7

11

18

25

32

39

46

53

2

5

11

24

48

97

192

3

6

9

12

15

18

21

1

3

5

11

24

48

96

The Babylonian method achieves an accuracy of 48 decimal digits with 18 operations. This same level of accuracy requires the proposed method to perform 39 arithmetic operations. At the outset, the Babylonian method may appear more efficient by a factor of 2 per iteration. However, the Babylonian is specifically optimised to only solving the . For larger accuracies the cost of the two divides per iteration plays a major  factor on its efficiency [16] [17]. Comparatively, the proposed method only needs one divide at the very end, while the Babylonian method requires it for every iteration. It is also very efficient in determining a series of rational numbers, which can be expressed as a quotient, that when divided, very accurately represents . The proposed method is also capable of solving more general cases of the .

  1. CONCLUSIONS

The computation of square roots have wide real-life applications. This paper proposed a new method for estimating square roots efficiently.  We compared our method with the well-known Babylonian method. The experimental results shows that the Babylonian method achieves an equivalent accuracy to the proposed method with one additional iteration. Even though  it is about  times more efficient for small quotients, for larger factors the cost of the two divisions per iteration is impeding its performance. The Babylonian method exhibits a specific optimisation to only solving the . The proposed method considers only the fractional component and is capable of expressing this as  a series of quotients whose accuracy need only be determined by one division at the end of the desired resolution. The advantage of our proposed method is that with a simple addition, both  can both be determined. This is achieved by performing an addition of 1 for , and an addition of 2 for the Silver ratio, .  The proposed method is also capable of solving more general cases of the  problem, which will be presented in future papers.

REFERENCES

  1. Sutikno T., An Efficient Implementation of the Non Restoring Square Root Algorithm in Gate Level, International Journal of Computer Theory and Engineering, Volume 3, Issue 1, pp. 46-51, 2011.
  2. Wang X., Variable Precision Floating-Point Divide and Square Root for Efficient FPGA Implementation of Image and Signal Processing Algorithms, PhD Thesis, Electrical and Computer Engineering, Northeastern University, Boston, Massachusetts, 2007.
  3. Dong-Guk H., Choi D., Kim H., Improved Computation of Square Roots in Specific Finite Fields, IEEE Transactions on Computers, Volume 58, pp. 188-196, 2009.
  4. Llamocca-Obregon D. R., A Core Design to Obtain Square Root Based on a Non-Restoring Algorithm, IBERCHIPS Workhsop, Salvador Bahia, Brazil, 2005.
  5. Chu W. and Y. Li;, Cost/Performance Tradeoff of n-Select Square Root Implementations, in 5th Australasian Computer Architecture, 2000.
  6. Lachowicz S. and Pfleiderer H. J., Fast Evaluation of the Square Root and Other Nonlinear Functions in FPGA,. 4th IEEE International Symposium on Electronic Design, Test and Applications, DELTA 2008, pp. 474-477, 2008.
  7. Kornerup, P. Digit selection for SRT division and square root. IEEE Transactions on Computers, Volume 54, Issue 3, pp. 294-303, 2005,
  8. Buchmann J.A., Introduction to Cryptography (2nd ed.). Springer. 2005.
  9. Kelly S. and Frankel S., Using HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512 with IPsec, Internet Engineering Task Force (IETF), May 2007.
  10. Overmars A. and Venkatraman S., A New Method of Golden Ratio Computation for Faster Cryptosystems,  IEEE Cybersecurity and Cyberforensics Conference (CCC), London, UK, 21-23 Nov. 2017.
  11. Sudha K. R., Sekhar A. C. ,and  Reddy P.V.G.D, Cryptography protection of digital signals using some recurrence relations, Int. J.of Comp. Sci. and Network Security, Volume 7, pp. 203-207, 2007.
  12. Tahghighi M., Turaev S., Jaafar A., Mahmod R. and Md.Said M., On the Security of Golden Cryptosystems”, Int. J. Contemp. Math Sciences, Volume 7, pp. 327 – 335, 2012.
  13. Overmars A. and Ntogramatzidis L., A new parameterisation of Pythagorean triples in terms of odd and even series, Cornell University, arXiv:1504.03163 [math.HO], pp. 1-9, 2015.
  14. Overmars A. and Venkatraman S., Pythagorean-platonic lattice method for finding all co-prime right angle triangles,  International Journal of Computer and Information Engineering World Academy of Science, Engineering and Technology, Volume 4,  Issue 11, pp. 1-4, 2017.
  15. David F. and Eleanor R., Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context, Historia Mathematica, Volume 25, Issue 4, pp. 366–378, 1998.
  16. Tommiska M T, Area-efficient implementation of a fast square root algorithm, Proceedings of the Third IEEE International Conference on Devices, Circuits and Systems, S18/1-S18/4, 2000.
  17. Takagi N, A hardware algorithm for computing reciprocal square root, Proceedings of the 15th IEEE Symposium on Computer Arithmetic, pp. 94 –100, 2001.



author

For Authors

Author Membership provide access to scientific innovation, next generation tools, access to conferences/seminars
/symposiums/webinars, networking opportunities, and privileged benefits.
Authors may submit research manuscript or paper without being an existing member of LJP. Once a non-member author submits a research paper he/she becomes a part of "Provisional Author Membership".

Know more

institutes

For Institutions

Society flourish when two institutions come together." Organizations, research institutes, and universities can join LJP Subscription membership or privileged "Fellow Membership" membership facilitating researchers to publish their work with us, become peer reviewers and join us on Advisory Board.

Know more

subsribe

For Subscribers

Subscribe to distinguished STM (scientific, technical, and medical) publisher. Subscription membership is available for individuals universities and institutions (print & online). Subscribers can access journals from our libraries, published in different formats like Printed Hardcopy, Interactive PDFs, EPUBs, eBooks, indexable documents and the author managed dynamic live web page articles, LaTeX, PDFs etc.

Know more