Какая операция превращает числа с плавающей запятой в «группу»? - PullRequest
Новая
       32

Какая операция превращает числа с плавающей запятой в «группу»?

1 голос
/ 27 февраля 2009

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

То есть, учитывая любые два числа с плавающей запятой ("double a, b"), какая последовательность операций, включая умножение, превратит это в другое действительное число с плавающей запятой? (Допустимое число с плавающей запятой - это все, что нормализуется 1, исключая NaN, denormals и -0.0).

Чтобы поставить этот грубый код: 

double a = drand();
while ( forever ) 
{
    double b = drand();
    a = GROUP_OPERATION(a,b); 
    //invariant - a is a valid floating point number
}

Просто умножение само по себе не работает из-за NaN. В идеале это был бы прямолинейный подход (избегая формулировок «если выше X, разделите на Y»).

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

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

Ответы [ 5 ]

3 голосов
/ 01 марта 2009

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

Целые числа по модулю 2 ^ N не образуют группу - какое целое число, умноженное на 2, дает 1? Чтобы целые числа были группой при умножении, вы должны быть по модулю простого числа. (например, Z mod 7, 2 * 4 = 1, поэтому 2 и 4 являются инверсиями друг друга)

Для значений с плавающей запятой простое умножение или сложение насыщается до +/- Бесконечность, и нет значений, которые являются инверсиями бесконечности, поэтому либо набор не является закрытым, либо ему не хватает обратимости.

Если, с другой стороны, вы хотите что-то похожее на целочисленное умножение по модулю степени 2, тогда умножение подойдет - есть элементы без инверсии, так что это не группа, но она закрыта - вы всегда получаете плавающую точку значение обратно. Для подмножеств поплавков, которые являются истинной группой, смотрите ответ Лакшманараджа.

1 голос
/ 27 февраля 2009

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

Не уверен, что это очень полезно. 

/* You have to find the integer type whose size correspond to your double */
typedef double float_t;
typedef long long int_t;

float_t group_operation(float_t a, float_t b)
{
  int_t *ia, *ib, c;
  assert(sizeof(float_t) == sizeof(int_t));
  ia = &a;
  ib = &b;
  c = *ia * *ib;
  return (float_t)c;
}
1 голос
/ 27 февраля 2009

Числа с плавающей точкой никогда не образуют группу в том смысле, о котором вы говорите, из-за ошибок округления. Рассмотрим любой из этих ужасных примеров из класса числового анализа, например, тот факт, что 0.1 нельзя представить точно в двоичном виде.

Но тогда даже вычислительные числа не образуют группу в этом смысле, поскольку они также не замкнуты при умножении. (Доказательство: вычислите результат while true do x = x*x. В какой-то момент вы превысите размер слова, исчерпаете ресурсы для BIGNUM или чего-то еще.)

обновление для @UnderAchievementAward:

- добавлено здесь, чтобы я мог получить форматирование, в отличие от комментариев

Так как я начинаю с плавающей запятой (вместо «реальных» чисел), не могу ли я избежать каких-либо проблем с представлением 0,1? Проблема "x = x * x" заключается в том, что для сохранения результата в допустимом диапазоне необходимы дополнительные операции.

Хорошо, но тогда вы столкнетесь с ситуацией, когда будут существовать x, y st 0 & le; x, y <<em> max , где xy <0. Или что-то такое же неинтуитивное. </p>

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

0 голосов
/ 01 марта 2009

Целые числа не образуют группу при умножении - 0 не имеет обратный.

0 голосов
/ 27 февраля 2009

Если групповая операция является умножением, то если n - старший бит, то r1 = 1 / мощность (2, n-1) - это наименьшее десятичное число, которое вы можете использовать, и [r1,2 * r1,4 * r1,8 * r1 ... 1] union [-r1, -2 * r1, -4 * r1, ....- 1] union [0] будет группой, которая вы ожидаете. Для целого числа [1,0, -1] - группа.

если групповая операция может быть чем-то другим, затем сформировать набор допустимых групп,

A (r) = cos (2 * Pi * r / n) от r = 0 до n-1

и групповая операция

COS (COSINV (А1) + COSINV (А2))

Я не знаю, хотите ли вы этого .....

или если вы хотите, чтобы INFINITY была установлена ​​в качестве допустимой группы, тогда

простой ответ: ГРУППОВАЯ ОПЕРАЦИЯ = AVG (A1, A2) = (A1 + A2) / 2

или существует некоторая функция F, которая имеет FINV как обратное, а затем FINV (F (A1) + F (A2) / 2) Примером F является Log, обратный, квадрат и т. Д. 

 double a = drand();
while ( forever ) 
{
    double b = drand();
    a = (a+b)/2
  //invariant - a is a valid floating point number
}

или если вы хотите, чтобы INFINITY установил ЦИФРОВОЙ формат в качестве допустимой группы, тогда Пусть L будет самым низким числом с плавающей точкой, а H будет самым большим числом с плавающей точкой

, затем ГРУППОВАЯ ОПЕРАЦИЯ = AVG (A1, A2, L, H) = (A1 + A2 + L + H) / 4

эта операция всегда будет в пределах L & H для всех положительных чисел.

Для практических целей вы можете взять L в четыре раза меньше самого низкого десятичного числа и H в качестве (наибольшего десятичного числа / 4). 

double l = (0.0000000000000000000000000//1) * 4
double h = (0xFFFFFFFFFFFFFFFFFFFFFF///F) / 4
double a = abs(drand()) / 4;

while ( forever ) 
{
    double b = abs(drand()) / 4;
    a = (a+b+l+h)/4
//invariant - a is a valid floating point number
}

это подмножество всех возможных чисел с плавающей точкой / 4.

...