Алгоритм БКМ

Алгоритм BKM — это алгоритм сложения и сложения для вычисления элементарных функций , впервые опубликованный в 1994 году Жан-Клодом Бажаром, Сильванусом Кла и Жаном-Мишелем Мюллером. BKM основан на вычислении комплексных логарифмов ( L-режим ) и экспонент ( E-режим ) с использованием метода, аналогичного алгоритму, который Генри Бриггс использовал для вычисления логарифмов. Используя предварительно вычисленную таблицу логарифмов отрицательных степеней двойки, алгоритм BKM вычисляет элементарные функции, используя только операции сложения, сдвига и сравнения целых чисел.

BKM похож на CORDIC , но использует таблицу логарифмов, а не таблицу арктангенсов . На каждой итерации выбор коэффициента производится из набора из девяти комплексных чисел: 1, 0, −1, i, −i, 1+i, 1−i, −1+i, −1−i, а не только -1 или +1, как используется CORDIC. BKM предоставляет более простой метод вычисления некоторых элементарных функций, и в отличие от CORDIC, BKM не требует коэффициента масштабирования результата. Скорость сходимости BKM составляет примерно один бит на итерацию, как и CORDIC, но BKM требует большего количества предварительно вычисленных элементов таблицы для той же точности, поскольку таблица хранит логарифмы комплексных операндов.

Как и другие алгоритмы класса сложения и сложения, BKM особенно хорошо подходит для аппаратной реализации. Относительная производительность программной реализации BKM по сравнению с другими методами, такими как полиномиальные или рациональные аппроксимации, будет зависеть от наличия быстрых многобитовых сдвигов (т.е. бочкового сдвига ) или аппаратной арифметики с плавающей запятой .

Обзор

Чтобы решить уравнение

\ln(x)=y

алгоритм BKM использует основное свойство логарифмов

\ln(ab)=\ln(a)+\ln(b)

Используя обозначение Пи , это тождество обобщается до

\ln \left(\prod _{k=0}^{n}a_{k}\right)=\sum _{k=0}^{n}\ln(a_{k})

Поскольку любое число может быть представлено произведением, это позволяет нам выбирать любой набор значений. $a_{k}$ которые умножаются, чтобы получить значение, с которого мы начали. В компьютерных системах умножать и делить на кратные 2 гораздо быстрее, но поскольку не каждое число кратно 2, используя $a_{k}=1+2^{m}$ это лучший вариант, чем более простой выбор $a_{k}=2^{m}$ . Поскольку мы хотим начать с больших изменений и добиться более точных результатов, $k$ увеличивается, мы можем более конкретно использовать $a_{k}=1+2^{-k}$ , что позволяет продукту приближаться к любому значению от 1 до ~4,768, в зависимости от того, какое подмножество $a_{k}$ мы используем в конечном продукте. На данный момент приведенное выше уравнение выглядит следующим образом:

\ln \left(\prod _{k\in K\subset \mathbb {Z} _{0}^{+}}1+2^{-k}\right)=\sum _{k\in K\subset \mathbb {Z} _{0}^{+}}\ln(1+2^{-k})

Этот выбор $a_{k}$ снижает вычислительную сложность произведения от многократного умножения до простого сложения и сдвига битов в зависимости от реализации. Наконец, сохраняя значения $\ln(1+2^{-k})$ в таблице вычисление решения также является простым сложением. Итеративно это дает нам две отдельные последовательности. Одна последовательность приближается к входному значению $x$ в то время как другой приближается к выходному значению $\ln(x)=y$ :

$x_{k}={\begin{cases}1&{\text{if }}k=0\\x_{k-1}\cdot (1+2^{-k})&{\text{if }}x_{k}{\text{ would be}}\leq x\\x_{k-1}&{\text{otherwise}}\end{cases}}$

Учитывая это рекурсивное определение и поскольку $x_{k}$ строго возрастает, то с помощью индукции и сходимости можно показать , что

\lim _{k\to \infty }x_{k}=x

для любого $1\leq x\lesssim 4.768$ . Для расчета вывода мы сначала создаем справочную таблицу

A_{k}=\ln(1+2^{-k})

Затем выходные данные вычисляются итеративно по определению $y_{k}={\begin{cases}0&{\text{if }}k=0\\y_{k-1}+A_{k}&{\text{if }}x_{k}{\text{ would be}}\leq x\\y_{k-1}&{\text{otherwise}}\end{cases}}$ Условия в этой итерации такие же, как и условия для ввода. Как и входные данные, эта последовательность также строго возрастает, поэтому можно показать, что

\lim _{k\to \infty }y_{k}=y

для любого $0\leq y\lesssim 1.562$ .

Поскольку приведенный выше алгоритм вычисляет и входные, и выходные данные одновременно, его можно немного изменить, чтобы $y$ известное значение и $x$ — это значение, которое мы хотим вычислить, тем самым вычисляя экспоненту вместо логарифма. Поскольку в этом случае x становится неизвестным, условие меняется с

\dots {\text{if }}x_{k}{\text{ would be}}\leq x

к

\dots {\text{if }}y_{k}{\text{ would be}}\leq y

Функция логарифма

Чтобы вычислить функцию логарифма (L-режим), алгоритм на каждой итерации проверяет, если $x_{n}\cdot (1+2^{-n})\leq x$ . Если да, то он вычисляет $x_{n+1}$ и $y_{n+1}$ . После $N$ итераций значение функции известно с погрешностью $\Delta \ln(x)\leq 2^{-N}$ .

Пример программы для вычисления натурального логарифма на C++ (см. A_e для стола):

 double log_e (const double Argument, const int Bits = 53) // 1 <= Argument <= 4.768462058
 {
    double  x = 1.0, y = 0.0, s = 1.0;

    for (int k = 0; k < Bits; k++) {
      double const  z = x + x*s;
      if (z <= Argument) {
          x  = z;
          y += A_e[k];
      }
      s *= 0.5;
    }
    return y;
 }

Логарифмы для оснований, отличных от e, можно вычислить с аналогичными усилиями.

Пример программы для вычисления двоичного логарифма на C++ (см. A_2 для стола):

 double log_2 (const double Argument, const int Bits = 53) // 1 <= Argument <= 4.768462058
 {
    double  x = 1.0, y = 0.0, s = 1.0;

    for (int k = 0; k < Bits; k++) {
      double const  z = x + x*s;
      if (z <= Argument) {
          x  = z;
          y += A_2[k];
      }
      s *= 0.5;
    }
    return y;
 }

Допустимый диапазон аргументов одинаков для обоих примеров (1 ≤ Argument ≤ 4,768462058…). В случае логарифма по основанию 2 показатель степени можно разделить заранее (чтобы получить целую часть), чтобы алгоритм можно было применить к остатку (между 1 и 2). Поскольку аргумент меньше 2,384231…, итерация k может начинаться с 1. Работая в любой системе счисления, умножение на s можно заменить прямым изменением показателя степени с плавающей запятой, вычитая из него 1 во время каждой итерации. В результате алгоритм использует только сложение, а не умножение.

Экспоненциальная функция

Чтобы вычислить экспоненциальную функцию (режим E), алгоритм на каждой итерации проверяет, если $y_{n}+\ln(1+2^{-n})\leq y$ . Если да, то он вычисляет $x_{n+1}$ и $y_{n+1}$ . После $N$ итераций значение функции известно с погрешностью $\Delta \exp(x)\leq 2^{-N}$ .

Пример программы на C++ (см. A_e для стола):

 double exp (const double Argument, const int Bits = 54)	// 0 <= Argument <= 1.5620238332
 {
   double  x = 1.0, y = 0.0, s = 1.0;

   for (int k = 0; k < Bits; k++) {
      double const  z = y + A_e[k];
      if (z <= Argument) {
         y = z;
         x = x + x*s;
      }
      s *= 0.5;
   }
   return x;
 }

Таблицы для примеров

static const double A_e [] = ...

 static const double A_e [] = // A_e[k] = ln (1 + 0.5^k)
 {
   0.693147180559945297099404706000, 0.405465108108164392935428259000,
   0.223143551314209769962616701000, 0.117783035656383447138088388000,
   0.060624621816434840186291518000, 0.030771658666753686222134530000,
   0.015504186535965253358272343000, 0.007782140442054949100825041000,
   0.003898640415657322636221046000, 0.001951220131261749216850870000,
   0.000976085973055458892686544000, 0.000488162079501351186957460000,
   0.000244110827527362687853374000, 0.000122062862525677363338881000,
   0.000061033293680638525913091000, 0.000030517112473186377476993000,
   0.000015258672648362398138404000, 0.000007629365427567572417821000,
   0.000003814689989685889381171000, 0.000001907346813825409407938000,
   0.000000953673861659188260005000, 0.000000476837044516323000000000,
   0.000000238418550679858000000000, 0.000000119209282445354000000000,
   0.000000059604642999033900000000, 0.000000029802321943606100000000,
   0.000000014901161082825400000000, 0.000000007450580569168250000000,
   0.000000003725290291523020000000, 0.000000001862645147496230000000,
   0.000000000931322574181798000000, 0.000000000465661287199319000000,
   0.000000000232830643626765000000, 0.000000000116415321820159000000,
   0.000000000058207660911773300000, 0.000000000029103830456310200000,
   0.000000000014551915228261000000, 0.000000000007275957614156960000,
   0.000000000003637978807085100000, 0.000000000001818989403544200000,
   0.000000000000909494701772515000, 0.000000000000454747350886361000,
   0.000000000000227373675443206000, 0.000000000000113686837721610000,
   0.000000000000056843418860806400, 0.000000000000028421709430403600,
   0.000000000000014210854715201900, 0.000000000000007105427357600980,
   0.000000000000003552713678800490, 0.000000000000001776356839400250,
   0.000000000000000888178419700125, 0.000000000000000444089209850063,
   0.000000000000000222044604925031, 0.000000000000000111022302462516,
   0.000000000000000055511151231258, 0.000000000000000027755575615629,
   0.000000000000000013877787807815, 0.000000000000000006938893903907,
   0.000000000000000003469446951954, 0.000000000000000001734723475977,
   0.000000000000000000867361737988, 0.000000000000000000433680868994,
   0.000000000000000000216840434497, 0.000000000000000000108420217249,
   0.000000000000000000054210108624, 0.000000000000000000027105054312
 };

static const double A_2 [] = ...

 static const double A_2 [] = // A_2[k] = log_2 (1 + 0.5^k)
 {
   1.0000000000000000000000000000000000000000000000000000000000000000000000000000,
   0.5849625007211561814537389439478165087598144076924810604557526545410982276485,
   0.3219280948873623478703194294893901758648313930245806120547563958159347765589,
   0.1699250014423123629074778878956330175196288153849621209115053090821964552970,
   0.0874628412503394082540660108104043540112672823448206881266090643866965081686,
   0.0443941193584534376531019906736094674630459333742491317685543002674288465967,
   0.0223678130284545082671320837460849094932677948156179815932199216587899627785,
   0.0112272554232541203378805844158839407281095943600297940811823651462712311786,
   0.0056245491938781069198591026740666017211096815383520359072957784732489771013,
   0.0028150156070540381547362547502839489729507927389771959487826944878598909400,
   0.0014081943928083889066101665016890524233311715793462235597709051792834906001,
   0.0007042690112466432585379340422201964456668872087249334581924550139514213168,
   0.0003521774803010272377989609925281744988670304302127133979341729842842377649,
   0.0001760994864425060348637509459678580940163670081839283659942864068257522373,
   0.0000880524301221769086378699983597183301490534085738474534831071719854721939,
   0.0000440268868273167176441087067175806394819146645511899503059774914593663365,
   0.0000220136113603404964890728830697555571275493801909791504158295359319433723,
   0.0000110068476674814423006223021573490183469930819844945565597452748333526464,
   0.0000055034343306486037230640321058826431606183125807276574241540303833251704,
   0.0000027517197895612831123023958331509538486493412831626219340570294203116559,
   0.0000013758605508411382010566802834037147561973553922354232704569052932922954,
   0.0000006879304394358496786728937442939160483304056131990916985043387874690617,
   0.0000003439652607217645360118314743718005315334062644619363447395987584138324,
   0.0000001719826406118446361936972479533123619972434705828085978955697643547921,
   0.0000000859913228686632156462565208266682841603921494181830811515318381744650,
   0.0000000429956620750168703982940244684787907148132725669106053076409624949917,
   0.0000000214978311976797556164155504126645192380395989504741781512309853438587,
   0.0000000107489156388827085092095702361647949603617203979413516082280717515504,
   0.0000000053744578294520620044408178949217773318785601260677517784797554422804,
   0.0000000026872289172287079490026152352638891824761667284401180026908031182361,
   0.0000000013436144592400232123622589569799954658536700992739887706412976115422,
   0.0000000006718072297764289157920422846078078155859484240808550018085324187007,
   0.0000000003359036149273187853169587152657145221968468364663464125722491530858,
   0.0000000001679518074734354745159899223037458278711244127245990591908996412262,
   0.0000000000839759037391617577226571237484864917411614198675604731728132152582,
   0.0000000000419879518701918839775296677020135040214077417929807824842667285938,
   0.0000000000209939759352486932678195559552767641474249812845414125580747434389,
   0.0000000000104969879676625344536740142096218372850561859495065136990936290929,
   0.0000000000052484939838408141817781356260462777942148580518406975851213868092,
   0.0000000000026242469919227938296243586262369156865545638305682553644113887909,
   0.0000000000013121234959619935994960031017850191710121890821178731821983105443,
   0.0000000000006560617479811459709189576337295395590603644549624717910616347038,
   0.0000000000003280308739906102782522178545328259781415615142931952662153623493,
   0.0000000000001640154369953144623242936888032768768777422997704541618141646683,
   0.0000000000000820077184976595619616930350508356401599552034612281802599177300,
   0.0000000000000410038592488303636807330652208397742314215159774270270147020117,
   0.0000000000000205019296244153275153381695384157073687186580546938331088730952,
   0.0000000000000102509648122077001764119940017243502120046885379813510430378661,
   0.0000000000000051254824061038591928917243090559919209628584150482483994782302,
   0.0000000000000025627412030519318726172939815845367496027046030028595094737777,
   0.0000000000000012813706015259665053515049475574143952543145124550608158430592,
   0.0000000000000006406853007629833949364669629701200556369782295210193569318434,
   0.0000000000000003203426503814917330334121037829290364330169106716787999052925,
   0.0000000000000001601713251907458754080007074659337446341494733882570243497196,
   0.0000000000000000800856625953729399268240176265844257044861248416330071223615,
   0.0000000000000000400428312976864705191179247866966320469710511619971334577509,
   0.0000000000000000200214156488432353984854413866994246781519154793320684126179,
   0.0000000000000000100107078244216177339743404416874899847406043033792202127070,
   0.0000000000000000050053539122108088756700751579281894640362199287591340285355,
   0.0000000000000000025026769561054044400057638132352058574658089256646014899499,
   0.0000000000000000012513384780527022205455634651853807110362316427807660551208,
   0.0000000000000000006256692390263511104084521222346348012116229213309001913762,
   0.0000000000000000003128346195131755552381436585278035120438976487697544916191,
   0.0000000000000000001564173097565877776275512286165232838833090480508502328437,
   0.0000000000000000000782086548782938888158954641464170239072244145219054734086,
   0.0000000000000000000391043274391469444084776945327473574450334092075712154016,
   0.0000000000000000000195521637195734722043713378812583900953755962557525252782,
   0.0000000000000000000097760818597867361022187915943503728909029699365320287407,
   0.0000000000000000000048880409298933680511176764606054809062553340323879609794,
   0.0000000000000000000024440204649466840255609083961603140683286362962192177597,
   0.0000000000000000000012220102324733420127809717395445504379645613448652614939,
   0.0000000000000000000006110051162366710063906152551383735699323415812152114058,
   0.0000000000000000000003055025581183355031953399739107113727036860315024588989,
   0.0000000000000000000001527512790591677515976780735407368332862218276873443537,
   0.0000000000000000000000763756395295838757988410584167137033767056170417508383,
   0.0000000000000000000000381878197647919378994210346199431733717514843471513618,
   0.0000000000000000000000190939098823959689497106436628681671067254111334889005,
   0.0000000000000000000000095469549411979844748553534196582286585751228071408728,
   0.0000000000000000000000047734774705989922374276846068851506055906657137209047,
   0.0000000000000000000000023867387352994961187138442777065843718711089344045782,
   0.0000000000000000000000011933693676497480593569226324192944532044984865894525,
   0.0000000000000000000000005966846838248740296784614396011477934194852481410926,
   0.0000000000000000000000002983423419124370148392307506484490384140516252814304,
   0.0000000000000000000000001491711709562185074196153830361933046331030629430117,
   0.0000000000000000000000000745855854781092537098076934460888486730708440475045,
   0.0000000000000000000000000372927927390546268549038472050424734256652501673274,
   0.0000000000000000000000000186463963695273134274519237230207489851150821191330,
   0.0000000000000000000000000093231981847636567137259618916352525606281553180093,
   0.0000000000000000000000000046615990923818283568629809533488457973317312233323,
   0.0000000000000000000000000023307995461909141784314904785572277779202790023236,
   0.0000000000000000000000000011653997730954570892157452397493151087737428485431,
   0.0000000000000000000000000005826998865477285446078726199923328593402722606924,
   0.0000000000000000000000000002913499432738642723039363100255852559084863397344,
   0.0000000000000000000000000001456749716369321361519681550201473345138307215067,
   0.0000000000000000000000000000728374858184660680759840775119123438968122488047,
   0.0000000000000000000000000000364187429092330340379920387564158411083803465567,
   0.0000000000000000000000000000182093714546165170189960193783228378441837282509,
   0.0000000000000000000000000000091046857273082585094980096891901482445902524441,
   0.0000000000000000000000000000045523428636541292547490048446022564529197237262,
   0.0000000000000000000000000000022761714318270646273745024223029238091160103901
 };

Примечания

Ссылки

Бажар, Жан-Клод; Кла, Сильванус; Мюллер, Жан-Мишель (август 1994 г.). «БКМ: новый аппаратный алгоритм для сложных элементарных функций» (PDF) . Транзакции IEEE на компьютерах . 43 (8): 955–963. дои : 10.1109/12.295857 . ISSN 0018-9340 . Збл 1073.68501 . Архивировано (PDF) из оригинала 3 ноября 2018 г. Проверено 21 декабря 2017 г.
Скаф, Али; Мюллер, Жан-Мишель; Гийо, Ален (20–22 сентября 1994 г.). Аппаратная реализация в режиме реального времени для комплексной экспоненты и логарифма . ESSCIRC '94: Двадцатая Европейская конференция по твердотельным схемам. Ульм, Германия. CiteSeerX 10.1.1.47.7521 . ISBN 2-86332-160-9 . Проверено 23 августа 2021 г. (5 страниц) [1] [2]
Бажар, Жан-Клод; Имбер, Лоран (2 ноября 1999 г.). Люк, Франклин Т. (ред.). «Оценка сложных элементарных функций: новая версия BKM» (PDF) . Труды SPIE, усовершенствованные алгоритмы обработки сигналов, архитектуры и реализации IX . Усовершенствованные алгоритмы обработки сигналов, архитектуры и реализации IX. 3807 . Общество инженеров фотооптического приборостроения (SPIE): 2–9. Бибкод : 1999SPIE.3807....2B . дои : 10.1117/12.367631 . S2CID 121001818 . Архивировано (PDF) из оригинала 9 июня 2020 г. Проверено 9 июня 2020 г. (8 страниц) [3]
Имбер, Лоран; Мюллер, Жан-Мишель; Рико, Фабьен (24 мая 2006 г.) [01 июня 2000 г., сентябрь 1999 г.]. «Алгоритм Radix-10 BKM для вычисления трансцендентных чисел на карманных компьютерах» . Журнал обработки сигналов СБИС (отчет об исследовании). 25 (2). Kluwer Academic Publishers / Национальный институт исследований в области информатики и автоматизации (INRIA): 179–186. дои : 10.1023/А:1008127208220 . ISSN 0922-5773 . S2CID 392036 . РР-3754. ИНРИА-00072908. Тема 2 ISSN 0249-6399 . Архивировано из оригинала 11 июля 2018 г. Проверено 11 июля 2018 г. (1+15 страниц) [4] [5] [6]
Дидье, Лоран-Стефан; Рико, Фабьен (21 января 2002 г.). «Алгоритм BKM по старому основанию с выбором путем округления» (PDF) . S2CID 17750192 . губа6.2002.009. hal-02545612. Архивировано (PDF) из оригинала 23 августа 2021 г. Проверено 23 августа 2021 г. [7] (1+11 страниц)
Дидье, Лоран-Стефан; Рико, Фабьен (1 декабря 2004 г.). «Алгоритм БКМ с высоким основанием» . Численные алгоритмы . Международная конференция СКАН'2002. 37 (1–4 [4]). Springer Science+Business Media, LLC : 113–125. Бибкод : 2004NuAlg..37..113D . дои : 10.1023/B:NUMA.0000049459.69390.ff . eISSN 1572-9265 . ISSN 1017-1398 . S2CID 2761452 . [8]
Мюллер, Жан-Мишель (2006). Элементарные функции: алгоритмы и реализация (2-е изд.). Бостон, Массачусетс, США: Биркхойзер . ISBN 978-0-8176-4372-0 . LCCN 2005048094 .
Мюллер, Жан-Мишель (12 декабря 2016 г.). Элементарные функции: алгоритмы и реализация (3-е изд.). Бостон, Массачусетс, США: Биркхойзер . ISBN 978-1-4899-7981-0 . ISBN 1-4899-7981-6 .

Дальнейшее чтение

Йорке, Гюнтер; Лампа, Бернар; Венгель, Норберт (1989). Арифметические алгоритмы микровычислительной техники (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . стр. 280–282. ISBN 3-34100515-3 . ISBN 978-3-34100515-6 . ЕАН 9783341005156 . МПН 5539165. Лицензия 201.370/4/89 . Проверено 1 декабря 2015 г.
Меггитт, Джон Э. (29 августа 1961 г.). «Псевдоделение и псевдоумножение» . Журнал исследований и разработок IBM . 6 (2). Ривертон, Нью-Джерси, США: IBM Corporation (опубликовано в апреле 1962 г.): 210–226, 287. doi : 10.1147/rd.62.0210 . Проверено 1 декабря 2015 г.
Чи Чен, Тянь (июль 1972 г.). «Автоматическое вычисление экспонент, логарифмов, отношений и квадратных корней» . Журнал исследований и разработок IBM . 16 (4). Сан-Хосе, Калифорния, США; Ривертон, Нью-Джерси, США: Исследовательская лаборатория IBM в Сан-Хосе ; Корпорация IBM : 380–388. дои : 10.1147/rd.164.0380 . Проверено 1 декабря 2015 г.
Револь, Натали ; Якубсон, Жан-Клод (1 мая 2000 г.). «Ускоренные алгоритмы сдвига и сложения» (PDF) . Надежные вычисления . 6 (2). Бостон, США: Лаборатория цифрового анализа и оптимизации (ANO) Университета наук и технологий Лилля ; Издательство Kluwer Academic : 193–205. дои : 10.1023/A:1009921407000 . eISSN 1573-1340 . ISSN 1385-3139 . OCLC 67306353 . S2CID 10716391 . Архивировано (PDF) из оригинала 23 августа 2021 г. Проверено 23 августа 2021 г. (14 страниц) [9]