1. AMM
  2. Всі випуски
  3. Випуск 1, Номер 1, 2019
  4. Проста модифікація алгоритму швидкого обчислення зворотного квадратного кореня для чисел з рухомою комою одинарної точності

Проста модифікація алгоритму швидкого обчислення зворотного квадратного кореня для чисел з рухомою комою одинарної точності

AMM.
2019;
Випуск 1, Номер 1
: cc. 39 - 45
Автори:
  1. Л. В. Мороз
  2. А. Гринчишин
  3. О. Я. Горячий
1
Національний університет «Львівська політехніка», кафедра безпеки інформаційних технологій
2
Національний університет «Львівська політехніка», кафедра безпеки інформаційних технологій
3
Національний університет «Львівська політехніка», кафедра безпеки інформаційних технологій

Опис прості алгоритма швидкого добування зворотного квадратного кореня з вико- ристанням магічної константи зі зменшеними відносними похибками обчислень для чисел типу float.

магічна константа
числа типу float
стандарт IEEE-754
відносна похибка обчислень
зворотний квадратний корінь з рухомою комою
  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.