Вычисление sqrt и arcTan в javacard без типа float

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

1- Могу ли я использовать число с плавающей запятой в форме массива байтов и работать над ним? как? 2- Как обычно эти операции рассчитываются в javacard?

Я нашел несколько ссылок, но не смог мне помочь: http://stackoverflow.com/questions/15363244/math-library-for-javacard http://javacardos.com/javacardforum/viewtopic.php?t=437

Я должен упомянуть, что я должен рассчитать эти операции на карте. Большое спасибо, если кто-нибудь может мне помочь.


math javacard
person Mohsen Gorgani    schedule 23.12.2016    source источник
comment
Какие именно входы? Каков их формат данных, (подразумеваемая) точность и т. д. Что ожидается от результатов, насколько точными они должны быть? Вы знаете ручной алгоритм квадратного корня? Алгоритмы CORDIC?   -  person Lutz Lehmann    schedule 23.12.2016
comment
Спасибо за ответ. Разве алгоритм не работает с типом данных float? У меня нет типа данных с плавающей запятой на карте.   -  person Mohsen Gorgani    schedule 23.12.2016
comment
Поэтому я и спросил про формат входных и выходных данных. Если вы не можете получить данные и не имеете структуры для размещения результата, то способ вычисления становится довольно второстепенным.   -  person Lutz Lehmann    schedule 23.12.2016
comment
На самом деле входные данные — это изображения в формате minutia (формат для хранения отпечатков пальцев в javacard), а выходные данные — это оценка в формате с плавающей запятой, которая указывает, насколько отпечатки пальцев похожи друг на друга. Мне нужно вычислить какую-то математическую операцию над двумя картинками и подсчитать балл.   -  person Mohsen Gorgani    schedule 23.12.2016
comment
И все с кодом 80kB и данными 2kB? Итак, вам нужно вычислить скалярное произведение, две векторные нормы и арккосинус? Или достаточно указать соотношение в процентах?   -  person Lutz Lehmann    schedule 23.12.2016
comment
Если я правильно понял ваш вопрос, ввод данных в формате minutia для каждого изображения составляет около 200 байт. Мелочи не являются картинкой, а извлекаются из картинки. Для вычисления корреляции двух изображений мне нужно рассчитать некоторый алгоритм, который использует sqrt и арктангенс, и, наконец, показать корреляцию в процентах.   -  person Mohsen Gorgani    schedule 23.12.2016
comment
Также проверьте описание алгоритма, если вам действительно нужен угол или просто нормализованный вектор направления. Даже угловые операции часто выполняются быстрее, если использовать тригонометрические тождества векторов направлений.   -  person Lutz Lehmann    schedule 24.12.2016
comment
Если это не для академических целей, вам следует изучить существующие продукты.   -  person Paul Bastian    schedule 24.12.2016

Ответы (2)


arrow_upward
2
arrow_downward

Идея CORDIC при вычислении atan состоит в том, чтобы иметь таблицу значений

angle[i] = atan(pow(2,-i));

Неважно, предварительно вычислены углы в радианах или градусах. Затем используйте касательную теорему сложения

tan(a+b)=(tan(a)+tan(b) ) / ( 1-tan(a)*tan(b) )

чтобы последовательно уменьшить заданное значение тангенса

tan(x) {
    if(x<0) return -atan(-x);
    if(x>1) return 2*angle[0]-atan(1/x);
    pow2=1.0;
    phi=0;
    for(i=0;i<10; i++) {
        if(x>pow2) {
            phi += angle[i];
            x = (x-pow2)/(1+pow2*x);
        }
        pow2 /= 2;
    }
    return phi+x;

Теперь нужно перевести эти операции и константы в какой-то формат с фиксированной точкой.

person Lutz Lehmann    schedule 23.12.2016
comment
Это странная реализация CORDIC. Это не очень эффективно из-за разделения в петле. Существует лучшее решение только с добавлениями и сдвигами. - person Yves Daoust; 24.12.2016
comment
Да, это было просто записано без проверки других источников. Поиск в Интернете находит convict.lu/Jeunes/Math/arctan.htm, который имеет, вероятно, достаточную квадратичную полиномиальную аппроксимацию и общую идею CORDIC. - person Lutz Lehmann; 24.12.2016
comment
Спасибо Лутцл за ответ. Есть ли способ представить тип float в массиве байтов и работать над ним? - person Mohsen Gorgani; 24.12.2016
comment
Да, форматы с множественной точностью устроены так, см., например, Pari, была написана целая книга о том, как построить CAS таким образом. -- Но для ваших целей было бы проще использовать формат с фиксированной точкой. Например, все числа являются 32-битными и интерпретируются как x/2^16. Таким образом, продукт будет (x/2^16)*(y/2^16)=(x*y/2^16)/2^16 и т. д. Это также лучше подходит для реализации с использованием сдвигов. - person Lutz Lehmann; 24.12.2016
comment
Спасибо Лутцл. Я протестирую его и сообщу вам о результате. - person Mohsen Gorgani; 24.12.2016

arrow_upward
4
arrow_downward

Целочисленный квадратный корень можно вычислить с помощью вавилонского метода, если доступно целочисленное деление.

Просто повторить

R' = (R + S / R) / 2

с подходящим начальным R.

Такое значение можно найти с помощью

R= 1
while S > 2:
  R*= 2
  S/= 4

(желательно реализовать со сменами, если таковые имеются).

Вы можете остановить итерации, когда значение R стабилизируется (также можно априори определить постоянное количество итераций, обеспечивающее достаточную точность).

person Yves Daoust    schedule 23.12.2016
comment
Спасибо Ив за ответ. У меня нет плавающего типа в карточке. как реализовать этот процесс с помощью байтового массива? - person Mohsen Gorgani; 24.12.2016
comment
@MohsenGorgani: я не уверен, что вы поняли мой ответ. Он использует целые числа. - person Yves Daoust; 24.12.2016
comment
Является ли результат целым? - person Mohsen Gorgani; 24.12.2016
comment
@MohsenGorgani: конечно. При необходимости вы можете эмулировать фиксированную точку. - person Yves Daoust; 24.12.2016
comment
Спасибо, Ив. позвольте мне проверить это, и я скажу вам о результате. - person Mohsen Gorgani; 24.12.2016