1. AMM
  2. All Volumes and Issues
  3. Volume 1, Number 1, 2019
  4. А Simple Modification of the Fast Inverse Square Root Calculation Algorithm for Single-precision Fl Ting-point Numbers

А Simple Modification of the Fast Inverse Square Root Calculation Algorithm for Single-precision Fl Ting-point Numbers

AMM.
2019;
Volume 1, Number 1
: pp. 39 - 45
Authors:
  1. L. Moroz
  2. A. Hrynchyshyn
  3. O. Horiachyy
1
Lviv Polytechnic National University
2
Lviv Polytechnic National University
3
Lviv Polytechnic National University

Simple algorithms of the fast inverse square root with the use of magic constant with reduced relative errors for numbers of type float are described in the paper.

magic constant
floating-point numbers
IEEE-754 standard
relative error
fast inverse square root
  1. Multiplier-free divide, square root, and log algorithms / F.  Auger,  Z.  Lou,  B.  Feuvrie, F.  Li  // IEEE Signal Process. Mag. 2011. Vol. 28. No. 4. P. 122–126.
  2. Allie M. A. Root of Less Evil / M. Allie, R. Lyons // IEEE Signal Process. Mag.: DSP Tips and Tricks. 2005. Vol. 22. P. 93–96.
  3. Parhami B. Computer Arithmetic: Algorithms and Hardware Designs / B. Parhami. 2nd ed. New York : Oxford Univ. Press, 2010. 
  4. Lemaitre Florian. Cholesky Factorization on SIMD multi-core architectures / Florian Lemaitre, Benjamin Couturier, Lionel Lacassagne // Journal of Systems Architecture. Elsevier, 2017. Vol. 79. P. 1–15.
  5. A Fast FPGA Based Architecture for Computation of Square Root and Inverse Square Root / A. Hasnat,T. Bhattacharyya, A. Dey, S. Halder, D. Bhattacharjee // Devices for Integrated Circuit (DevIC): int. conf., 23–24 Mar., 2017. Kalyani, 2017. P. 383–387.
  6. Beebe N. H. F. The Mathematical-Function Computation Handbook: Programming Using the MathCW Portable Software Library / N. H. F. Beebe. Springer, 2017.
  7. Optimizations of Two Compute-bound Scientific Kernels on the SW26010 Many-core Processor / J. Lin, Z.  G.  Xu,  A.  Nukada,  N.  Maruyama,  S.  Matsuoka  //  46th International  Conference  on  Parallel  Processing, 14–17 Aug. 2017. Bristol : IEEE, 2017. P. 432–441.
  8. Improving Deep Learning By Inverse Square Root Linear Units (ISRLUS) / Brad Carlile, Guy Delamarter, Paul Kinney, Akiko Marti, Brian Whitney. 2018.
  9. Andriy Hrynchyshyn. An efficient algorithm for fast inverse square root / Hrynchyshyn Andriy, Horyachyy Oleh, Tymoshenko Oleksandr // Przetwarzanie, transmisja i bezpieczeństwo informacji. Bielsko-Biała : Wydawnictwo Naukowe ATH w Bielsku-Białej, 2018. T. 2. P. 105–113.
  10. Hanninen T. Novel detector implementations for 3G LTE downlink and uplink / T. Hanninen, J. Janhunen, M. Juntti // Analog. Integr. Circ. Sig. Process. 2014. Vol. 78. No. 3. P. 645–655.
  11. Floating point unit demonstration on STM32 microcontrollers: Application note AN4044. STMicroelectronics N.V., 2016.
  12. ARM® NEON™ Intrinsics Reference: IHI 0073B. ARM Limited, 2016.
  13. Hsu C. J. An Efficient Hardware Implementation of HON4D Feature Extraction for Real-time Action Recognition / C. J. Hsu, J. L. Chen, L. G. Chen // IEEE International Symposium on Consumer Electronics (ISCE). 2015.
  14. A UWB Radar Signal Processing Platform for Real-Time Human Respiratory Feature Extraction Based on Four-Segment Linear Waveform Model / C. H. Hsieh, Y. F. Chiu, Y. H. Shen, T. S. Chu, Y. H. Huang // IEEE Trans. Biomed. Circ. Syst. 2016. Vol. 10. No. 1. P. 219–230.
  15. Ziqiang Li.  OFDM  Synchronization  implementation  based  on  Chisel  platform  for  5G  research  / Li Ziqiang, Chen Yun, Zeng Xiaoyang // IEEE 11th International Conference on ASIC (ASICON). Chengdu : IEEE, 2015. P. 1–4.
  16. Sangeetha D. Efficient Scale Invariant Human Detection using Histogram of Oriented Gradients for IoT Services / D. Sangeetha, P. Deepa // IEEE 30th International Conference on VLSI Design and 16th International Conference on EmbeddedSystems. Hyderabad : IEEE, 2017. P. 61–66.
  17. Fog A. Software optimization resources, Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs [Electronic resource] / A. Fog. Regime of access: http://www.agner.org/optimize/.
  18. x86 and amd64 instruction reference [Electronic resource]. Regime of access: http://www.felixcloutier.com/x86/index.html.
  19. Lomont C. Fast inverse square root [Electronic resource] / C. Lomont // Purdue University : Tech. Rep. – 2003. – Regime of access: http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf.
  20. Blinn J. Floating-point tricks / J. Blinn // IEEE Comput. Graphics Appl. IEEE, 1997. Vol. 17. No. 4. P. 80–84.
  21. Zafar S. Hardware architecture design and mapping of “Fast Inverse Square Root’s algorithm” / S. Zafar, R. Adapa // International Conference on Advances in Electrical Engineering (ICAEE). 2014. P. 1–4.
  22. Martin P. Eight Rooty Pieces / P. Martin // Overload Journal. No. 135. 2016. P. 8–12.
  23. Fast calculation of inverse square root with the use of magic constant – analytical approach / L. Moroz, C. J. Walczyk, A. Hrynchyshyn, V. Holimath, J.L. Cieslinski // Appl. Math. Computation. Elsevier, 2018.  Vol. 316.P. 245–255.
  24. Eberly D. H. GPGPU Programming for Games and Science / D. H. Eberly. Florida : CRC Press, 2015. 
  25. Walczyk C. J. Improving the accuracy of the fast inverse square root algorithm [Electronic resource] /  C. J. Walczyk,  L. V.  Moroz,  J.  L.  Cieslinski.  –  arXiv  preprint  arXiv:  1802.06302.  2018  Regime  of  access: https://arxiv.org/pdf/1802.06302.pdf.