1
votes

Might anyone be famiiar with tricks and techniques to coerce the set of valid floating point numbers to be a group under a multiplication based operation?

That is, given any two floating point numbers ("double a,b"), what sequence of operations, including multiply, will turn this into another valid floating point number? (A valid floating point number is anything 1-normalized, excluding NaN, denormals and -0.0).

To put this rough code:

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

Just multiply by itself doesn't work, because of NaNs. Ideally this would be a straight-line approach (avoiding "if above X, divide by Y" formulations).

If this can't work for all valid floating point numbers, is there a subset for which such an operation is available?

(The model I'm looking for is akin to integer multiplication in C - no matter what two integers get multiplied together, you always get an integer back).

5
for eg) [-1,0,1] is a set where in their mulitplicaitons will stay in the same set. This is what you want or Some operations over [A1..AN] will lie in the same set. For examples 2's compliment of A1 named as A1' and then set [A1, A1'] is a group with operation of 2's compliment. What do you want? - lakshmanaraj
Given the set of normal doubles, and the operation I'm asking for, I want the result to be in the set of normal doubles. So, closer to [-1,0,1] example. - Underachievementaward
@Underachieventaward: In that case you are not looking for a "group," since "group" implies that each element has a unique inverse. Because of rounding error, there is often more than 1 y for which xy == z is true, so you would need to severely restrict the set to guarantee uniqueness. - j_random_hacker
Maybe I asked for the wrong thing then.. I thought z = f(x,y) where x and y are members, then z must also be a member would be a group. Is there a better term ? - Underachievementaward

5 Answers

3
votes

(The model I'm looking for is akin to integer multiplication in C - no matter what two integers get multiplied together, you always get an integer back).

Integers modulo 2^N do not form a group - what integer multiplied by 2 gives 1? For integers to be a group under multiplication, you have to be modulo a prime number. (eg Z mod 7, 2*4 = 1, so 2 and 4 are each other's inverses)

For floating point values, simple multiplication or addition saturates to +/- Infinity, and there are no values which are the inverses of infinity, so either the set is not closed, or it lacks invertibility.

If on the other hand you want something similar to integer multiplication modulo a power of 2, then multiplication will do - there are elements without an inverse, so it's not a group, but it is closed - you always get a floating point value back. For subsets of floats which are a true group, see lakshmanaraj's answer.

1
votes

Floating point numbers are backed by bits. That means that you can use the integer arithmetic on the integer representation of your floating point values and you will get a group.

Not sure this is very usefull though.

/* 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
votes

Floating point numbers never form a group in the sense you are talking about, because of rounding errors. Consider any of those horrible examples from numerical analysis class, like the fact that 0.1 can't be represented exactly in binary.

But then even computational ints don't form a group in that sense, since they're not closed under multiplication either. (Proof: compute the result of while true do x = x*x. At some point you'll exceed the word size, run out of resources for a BIGNUM, or something.)

update for @UnderAchievementAward:

-- added here so I can get formatting, unlike comments

Since I start with floating point (instead of "real" numbers), can't I avoid any of the 0.1 representational issues? The "x = x*x" problem is why additional operations are needed to keep the result in the valid range.

Okay, but then you're going to run into a situation where there will exist some x,y st 0 ≤ x,y < max where xy < 0. Or something equally non-intuitive.

The point is that you can certainly define a collection of operations that will look like a group on a finite representation set, but it's going to do weird things if you try to use it as the normal arithmetic operations.

0
votes

If group operation is multiplication then if n is the highest bit, then r1=1/power(2,n-1) is the least decimal that you can operate and the set [r1,2 * r1,4 * r1,8 * r1...1] union [-r1, -2 * r1, -4 * r1,....-1] union [0] will be the group that you are expecting. For integer [1,0,-1] is the group.

if Group operation can be any thing else, then to form n set of valid groups,

A(r)=cos(2*Pi*r/n) from r=0 to n-1

and group operation is

COS(COSINV(A1)+COSINV(A2))

I don't know whether you want this.....

or if you want INFINITY set as a valid group then

simple answer : GROUP OPERATION = AVG(A1,A2) = (A1+A2)/2

or some functions exists F which has FINV as it's inverse and then FINV(F(A1)+F(A2)/2) Example of F is Log, inverse, square etc ..

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

or if you want INFINITY set of DIGITAL format as a valid group then Let L be the lowest float number and H be highest float number

then GROUP OPERATION = AVG(A1,A2, L, H) = (A1+A2+L+H)/4

this operation will always be within L & H for all Positive numbers.

You can take L as four times the lowest decimal number and H as the (highest decimal number /4) for practical purpose.

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
}

this has a subset of all possitive float number / 4.

-1
votes

The integers don't form a group under multiplication -- 0 doesn't have an inverse.