Re: Information
Richard,
Firstly, let me apologize for my comments to Professor Kulich's last discussion: put it down to trying to work through a poorly-defined (proposed) standard for fix point arithmetic for embedded C. I have found that document quite frustrating, and I'd like to express my apologies to Ulrich for any offence caused.
Let us see if I can answer your questions:
On 6 Sep 2013, at 04:24, Richard Fateman wrote:
> Is it possible to get a response to Baker's questions? In order to discourage further discursive
> description in which the answer may or may not be present, Let me try to rephrase as
> yes/no questions:
>
> Given a two vectors A,B of length n , will there be a difference in any bit in the answer
> between double_correctly_rounded_dot_product(A,B,n)
> and reduce_to_double(exact_dot_product(A,B,n))?
>
> yes or no?
Yes.
Suppose A, and B are of dimension 3, with a_1*b_1 = 10e350, a_2*b_2 = -10e350,
and a_3*b_3 = 1e-350.
(Substitute an alternative to 350 in the above if I've got the wrong exponent.)
The exact dot product will get 1e-350.
Depending on how it's implemented double_correctly_rounded_dot_product might get any number of
answers, but 0 is quite likely --- even if quad precision is used internally.
>
> Does the requirement of the exact dot product require a new representation consisting of an
> array of a certain length d of base b numbers?
>
> yes or no?
Internally yes. Externally no.
Internally we will need to hold an integer base b of length 2 * 2^max_exponent. Whatever that is in quad precision.
>
> I add the question: if the previous answer is yes, are we now involved with proposing
> the definition , standardization, and a complete repertoire of heretofore new operations
> in the interval standard, operations which in general do not have interval arguments or interval results?
>
> yes or no?
>
Yes. Indeed I'd go further and say that by itself EDP is merely one part of an interval DP, since we will of necessity have to represent the two end points of the interval enclosing the dot product.
> I would be happy to share programs to compute exact as well as correctly rounded
> dot products which do not use complete arithmetic (CA). Therefore
> it is certainly not the case that CA is required for EDP.
If I were implementing EDP on a GPU, I'd be looking at smearing the representation over multiple pipelines to improve the exploitation of parallelism, and improve throughput.
> Sparse representations
> have advantages, and the whole idea is somewhat redundant in a language that
> has as a base type exact rational and integer arithmetic.
Which is almost all of the ones I work with these days.
>
> In the interest of producing a standard document and at least one reference implementation
> before the IEEE deadline,
I see this as absolutely essential. Without a reference implementation, implementers will find themselves in exactly the same situation I am currently in when working from the fix-point "standards" document: "what does _that_ mean?"
> I think other issues which might need discussion should be raised.
> Or is everything set and this is the last area that needs discussion?
>
> um, yes or no?
I fear the answer is a resounding "no"!
Dave.
>
> Thanks
>
> RJF
>
>
>
> On 9/5/2013 12:27 PM, Ulrich Kulisch wrote:
>> Am 05.09.2013 13:59, schrieb Ralph Baker Kearfott:
>>> Can someone please clarify or confirm to me how we view
>>> the EDP? In particular, the only practical difference I see
>>> between the EDP and a correctly rounded dot product
>>> (the present state of P-1788's plan) is that a possible
>>> EDP operation must return some representation of
>>> the exact result (not a standard floating point number),
>>> whereas the correctly rounded dot product must return
>>> a floating point number the same AS IF the dot product
>>> were first computed exactly, then rounded according to
>>> the rounding mode in effect.
>>>
>>> Thus, if my interpretation is right, the only additional requirement
>>> of the EDP over the correctly rounded DP is that a representation
>>> from which the exact result can be recovered be available. Wouldn't
>>> whether or not that result is subsequently rounded into a floating point
>>> number then be up to the programmer or user?
>>>
>>> Baker
>>>
>>>
>>>
>>>
>> Baker,
>>
>>
>> Let R = R(b, l, e1, e2) be the floating-point system, b the base, l the number of matissa digits.
>> A variable of type "complete" would be a fixed-point variable with d = t + 2•e2+2l+|2•e1| digits of base b. For n<= bt , every sum of n floating-point products can be represented as a variable of type complete. Moreover, every such sum can be computed in a (local) store (or register) of length d without loss of information.
>> If A is a variable of type complete and x and y are floating-point numbers, the function call
>> dotadd(A, x, y) or the assignment A := A + x•y adds the double length product x•y to the variable A exactly. The EDP of two vectors x = x[i] and y = y[i] is now easily implemented with a variable A of type complete as follows:
>>
>> A := 0;
>> for i:= 1 to n do dotadd( A, x[i], y[i]);
>> z := ○(A);
>>
>> The last statement then rounds the value of type complete (to nearest, upward, downward, or to the least including interval depending on the rounding symbol o) to the type of z. Here z could be of any higher precision.
>>
>> For example the method of defect correction requires highly accurate computation of expressions of the form
>> a•b + c•d + e•f with vectors a, b, c, d, e, f. The result involving 3n multiplications and 3n -1 additions is produced with no roundings after the additions and multiplications. Digit cancellations as in a conventional floating-point computation do no occur here. Then the exact result can be rounded to a desired precision.
>>
>> Best regards
>> Ulrich
>>
>> P.S.: I shall be out of town for a couple of days.
>>
>>
>> --
>> Karlsruher Institut für Technologie (KIT)
>> Institut für Angewandte und Numerische Mathematik
>> D-76128 Karlsruhe, Germany
>> Prof. Ulrich Kulisch
>>
>> Telefon: +49 721 608-42680
>> Fax: +49 721 608-46679
>> E-Mail:
>> ulrich.kulisch@xxxxxxx
>> www.kit.edu
>> www.math.kit.edu/ianm2/~kulisch/
>>
>>
>> KIT - Universität des Landes Baden-Württemberg
>> und nationales Großforschungszentrum in der
>> Helmholtz-Gesellschaft
>>
>