2016-02-25 6 views
3

, так что в настоящее время я помогаю в разработке языка программирования, и мы достигли точки, в которой нам нужно реализовать тип фиксированной точки, используя C++ в качестве нашего базового языка, чтобы написать это. умеет вычислять, как добавлять, вычитать, умножать, делить, однако я рисую пробел, как это сделать для модуля и экспоненты. Я чувствую, что я близок к выяснению экспоненциальности, поэтому я сосредоточу этот вопрос на модуле., реализующий модуль с фиксированной точкой типа

В настоящее время я делаю это, я беру строковый литерал и отслеживаю точку радиуса и нахожу расстояние от конца строки, и это дает мне мой коэффициент масштабирования. После этого мы сохраняем целое большое целое число, которое должно быть ограничено фиксированным типом (если не возникнут такие обстоятельства, как деление ... или, возможно, модуль), в этот момент мы увеличиваем дробную сторону основания на почти половину размера целой части). Я реализовал способы захвата значений слева от основания и справа от оснований путем умножения на коэффициенты 10 (я хочу, чтобы точность, которая приходит с базой 10, в отличие от скорости базы 2), чтобы получить место, где радикс будет сидеть. Я искал googled, как реализовать модуль по типам фиксированных точек, но безрезультатно.

Я не могу понять, как можно реализовать его. Есть ли способ реализовать это? Знают ли люди об обобщенном алгоритме? Что-нибудь, чтобы указать мне в правильном направлении? Помните, я нацелен на точность. Скорость тоже хороша, но главной директивой является точность.

Чтобы уточнить, оборудование, над которым мы будем работать, обобщается. Что касается определения того, что я хочу ... вот почему я здесь. Я не знаю, чего хочу, хочу узнать несколько примеров и варианты выбора. На самом деле я просто пытаюсь узнать об этом.

Пример:

сказать, что есть fixed8x8 и я выталкивать 2% 1,2 (2 может быть 2,0, а здесь), результат должен вернуться 0,8. Какое хорошее правило для расширения размеров правой стороны, чтобы компенсировать точность?

+0

Что означает «модуль» в этом контексте? Числа с фиксированной точкой представляют действительные числа, а по действительным числам умножение обратимо, поэтому нет понятия «остаток». –

+1

«Я хочу точность, которая приходит с базой 10, в отличие от скорости базы 2»? вы ожидаете получить больше точности, используя базу 10? – user463035818

+0

Я не уверен, что понимаю, что вы имеете в виду, когда умножение является обратимым. Я получаю, что они представляют действительные числа, но, безусловно, есть еще способ захватить остаток из группы. Вы говорите мне, что все вычисления фракций по модулю выполняются в плавающей точке и, возможно, я неправильно понимаю? –

ответ

3

С исправлением 1,2% 2 == 1,2, тогда просто игнорируйте десятичную величину, например. это то же самое, что и 12% 20 == 12

Вы можете просто использовать вычитание, чтобы вычислить это, если скорость действительно не нужна. Например. для любого A% M просто продолжайте вычитать M от A до A < M, для M! = 0 (бесконечный цикл!). Это обеспечит тот же результат, 1,2, так как на вычитание не влияет на десятичные точки, если они представлены как фиксированные.

Если скорость имеет значение, и у вас нет процедур умножения, которые могут игнорировать десятичную (большинство не будет), вам может понадобиться их построить, поскольку в 8x8 вам не хватит места для смещения всего значения в левую часть (для некоторых операций я реализовал 24x8 регистры с фиксированной точкой в ​​моей библиотеке PIC 16F, чтобы обеспечить более высокую точность при выполнении вычислений с фиксированной точкой 16x8).

Чтобы уточнить с помощью умножения для ускорения арифметики, и по этой причине вы должны умножению процедуры, которые могут игнорировать десятичные,

Сначала мы проанализируем более медленное вычитание подхода с помощью этого псевдо-C++ кода:

auto answer = A; 
while(answer >= M) 
    answer -= M; 
// now, your answer is in answer 

Но если бы мы знали, сколько итераций были необходимы заранее, мы могли бы просто:

auto answer = A - M * number_of_iterations; 

конечно, мы не будем знать-е на, поэтому цель состоит в том, чтобы уменьшить количество итераций, которые нам нужны.Это можно сделать с помощью обратного факторизации - учитывая число M, найдите, сколько раз вы можете умножить его на 10 (одна цифра влево), и он все равно будет меньше A, так, например, если A равно 1023.32, а M равно 4.1, вы можете умножить M на 10 дважды, в результате получится M * 10 * 10 = 410. Вычтите это от A до A < M * 10 * 10, оставив A '= 203.32 и продолжайте повторять пока ваша рабочая копия A не будет меньше M. Этот подход обычно включает операцию O (N) в операцию O (log (N)), если вы не добавляете слишком много накладных расходов при вычислениях (в моем PIC 16F я должен был быть осторожен, потому что у чипа было всего 384 байта общей памяти, поэтому, разумеется, это было медленнее, чем могло бы быть).

В основном я работал в base-2, но те же идеи переводили и на base-10, поэтому что-то вроде этого должно значительно уменьшить количество итераций, особенно для более крупных предметов (и это можно отрегулировать в зависимости от ваше внутреннее представление, так что вы можете использовать цифру сдвига вместо умножения для каждого шага):

auto currentA = A; 
while(currentA >= M){ 
    auto scaledM = M; 
    while(scaledM*10 < currentA) 
    scaledM *= 10; 
    // this second loop prevents recomputing scaledM where 
    // currentA > n*scaledM for some n < 10; not needed in base-2 
    while(currentA > scaledM) 
    currentA -= scaledM; 
} 

И currentA будет содержать модуль, когда это завершает.

+0

Я собираюсь переварить это некоторое время, а затем придет к вам с несколькими вопросами. –

+0

Считаете ли вы, что вы можете подробно остановиться на построении подпрограмм умножения? Что-то вроде примера, как формула выше? –

+0

Да. Это побеждает. Я собираюсь продолжать возвращаться сюда, возможно, с большим количеством вопросов. Большое спасибо за помощь. –