Логарифмическая система счисления
Логарифмическая система счисления (LNS) — это арифметическая система, иногда используемая для представления вещественных чисел в компьютере и в цифровых аппаратных средствах, особенно в цифровой обработке сигналов.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c1/Gaussian_logarithm.svg/300px-Gaussian_logarithm.svg.png)
Теория
правитьВ LNS число представлено логарифмом следующим образом:
где - его абсолютное значение; обозначающий знак ( если и если ).
Эта формулировка упрощает операции умножения, деления, возведения в степень, так как они сводятся к сложению, вычитанию, умножению и делению, соответственно. С другой стороны, операции сложения и вычитания в такой форме записи оказываются более сложными, и они рассчитываются по формулам:
где разница между логарифмами операндов, функция «суммы» , а функция «разницы» . Эти функции и , изображенные на рисунке справа, также известны как логарифмы Гаусса. Упрощение умножения, деления, взятия корня и возведения в степень компенсируется сложностью оценки этих функций для сложения и вычитания. Эта добавленная стоимость оценки может быть незначительна при использовании LNS в первую очередь для повышения точности операций с плавающей запятой.
История
правитьЛогарифмическая система счисления была независимо изобретена и опубликована по крайней мере три раза, в качестве альтернативы системам счисления с фиксированной и с плавающей запятой[1].
Кингсбери и Рейнер представили «логарифмическую арифметику» для цифровой обработки сигналов в 1971 году.[2]
Аналогичная LNS была описана в 1975 году Шварцлендером и Алехопоулосом.[3]
Ли и Эдгар описал подобную систему счисления, которую они назвали «Фокус», в 1977 году[4]
Математические основы для сложения и вычитания в LNS восходят к Карлу Фридриху Гауссу и Z. Leonelli[5][6].
Применение
правитьLNS была использована в Gravity Pipe[англ.] (GRAPE) — специальном суперкомпьютере[7], который выиграл Премию Гордона Белла в 1999 году.
LNS обычно используется как часть скрытых марковских моделей, таких как Алгоритм Витерби, для распознавания речи и секвенирования ДНК.
Значительные усилия в исследовании применимости LNS в качестве жизнеспособной альтернативы системам с плавающей запятой общего назначения для обработки одинарной точности вещественных чисел описаны в контексте «Европейского логарифмического микропроцессора» (ELM).[8] Представлен прототип 32-разрядного процессора, функционирующего в LNS. Дальнейшее совершенствование LNS, основанной на архитектуре ELM вновь показало значительно лучшую скорость вычислений и большую точность, нежели вычисления с плавающей запятой.[9]
LNS иногда используется в FPGA — приложениях, где большинство арифметических операций это умножение и деление.[10]
Примечания
править- ↑ S. C. Lee and A. D. Edgar. Addendum to "The Focus Number System" (англ.) // IEEE Transactions on Computers[англ.] : journal. — 1979. — September (vol. C—28, no. 9). — P. 693. — doi:10.1109/TC.1979.1675442.
- ↑ N. G. Kingsbury and P. J. W. Rayner. Digital filtering using logarithmic arithmetic (англ.) // Electronics Letters[англ.] : journal. — 1971. — 28 January (vol. 7). — P. 55.
- ↑ E. E. Swartzlander and A. G. Alexopoulos. The Sign/Logarithm Number System (англ.) // IEEE Transactions on Computers[англ.] : journal. — 1975. — December (vol. C—24, no. 12). — P. 1238—1242. — doi:10.1109/T-C.1975.224172.
- ↑ S. C. Lee and A. D. Edgar. The focus number system (англ.) // IEEE Transactions on Computers[англ.] : journal. — 1977. — November (vol. C—26, no. 11). — P. 1167—1170. — doi:10.1109/TC.1977.1674770.
- ↑ Logarithm: Addition and Subtraction, or Gaussian Logarithms . Encyclopædia Britannica Eleventh Edition. Дата обращения: 18 января 2013. Архивировано из оригинала 29 января 2013 года.
- ↑ G. Waldo Dunnington. Carl Friedrich Gauss (неопр.). — MAA, 2002. — ISBN 0-88385-547-X.
- ↑ J Makino and M. Taiji. Scientific Simulations with Special Purpose Computers: The GRAPE Systems (англ.). — Wiley, 1998. — ISBN 978-0-471-96946-4.
- ↑ J. N. Coleman, C. I. Softley, J. Kadlec, R. Matousek, M. Tichy, Z. Pohl, A. Hermanek, and N. F. Benschop. The European Logarithmic Microprocessor (англ.) // IEEE Transactions on Computers[англ.] : journal. — 2008. — April (vol. 57, no. 4). — P. 532—546. — doi:10.1109/TC.2007.70791.
- ↑ R.C Ismail and J.N Coleman. ROM-less LNS (неопр.) // 2011 20th IEEE Symposium on Computer Arithmetic (ARITH). — 2011. — July. — С. 43—51. — doi:10.1109/ARITH.2011.15.
- ↑ Haohuan Fu, Oskar Mencer, Wayne Luk. Comparing Floating-point and Logarithmic Number Representations for Reconfigurable Acceleration (англ.) // IEEE Conference on Field Programmable Technology : journal. — 2006. — December. — P. 337. — doi:10.1109/FPT.2006.270342. Архивировано 19 января 2012 года.