Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #4065 > unrolled thread

Infinity + Infinity (or NegInfinity - NegInfinity)

Back to article view | Back to comp.arch

Contents

  Infinity + Infinity (or NegInfinity - NegInfinity) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-08 02:54 +0200
    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Robert Myers <rbmyersusa@gmail.com> - 2011-10-07 18:40 -0700
      Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-07 22:39 -0400
    Re: Infinity + Infinity (or NegInfinity - NegInfinity) William Elliot <marsh@rdrop.com> - 2011-10-07 19:56 -0700
      Re: Infinity + Infinity (or NegInfinity - NegInfinity) Jasen Betts <jasen@xnet.co.nz> - 2011-10-08 06:45 +0000
        Re: Infinity + Infinity (or NegInfinity - NegInfinity) gordonb.eug6r@burditt.org (Gordon Burditt) - 2011-10-08 02:37 -0500
          Re: Infinity + Infinity (or NegInfinity - NegInfinity) William Elliot <marsh@rdrop.com> - 2011-10-08 21:40 -0700
            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Kaba <kaba@nowhere.com> - 2011-10-09 12:17 +0300
    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Jasen Betts <jasen@xnet.co.nz> - 2011-10-08 06:33 +0000
    Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-08 16:41 +0200
      Re: Infinity + Infinity (or NegInfinity - NegInfinity) kenney@cix.compulink.co.uk - 2011-10-09 04:01 -0500
    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Kaba <kaba@nowhere.com> - 2011-10-08 17:43 +0300
      Re: Infinity + Infinity (or NegInfinity - NegInfinity) "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-10-08 10:20 -0700
        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Kaba <kaba@nowhere.com> - 2011-10-08 22:35 +0300
      Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-08 18:55 +0100
        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Kaba <kaba@nowhere.com> - 2011-10-08 23:03 +0300
          Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-08 21:27 +0100
            Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-08 17:28 -0400
              Re: Infinity + Infinity (or NegInfinity - NegInfinity) Robert Myers <rbmyersusa@gmail.com> - 2011-10-08 18:15 -0400
              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-08 23:23 +0100
                Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-08 21:29 -0400
                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-09 10:01 +0100
                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Al Grant <algrant@myrealbox.com> - 2011-10-12 06:14 -0700
                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-12 15:25 +0100
                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-12 12:10 -0400
                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-12 18:41 +0100
                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-12 15:32 -0400
                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-12 20:44 +0100
                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) Robert Myers <rbmyersusa@gmail.com> - 2011-10-12 18:11 -0700
                                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-13 03:48 +0000
                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-12 23:15 -0700
                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-13 09:12 +0200
                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-13 00:49 -0700
                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-13 10:37 +0200
                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-13 11:04 -0400
                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-13 17:15 -0400
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-14 09:22 +0200
                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-14 13:37 -0400
                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-13 11:11 -0700
                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Al Grant <algrant@myrealbox.com> - 2011-10-14 01:04 -0700
                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-13 09:07 +0100
                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Al Grant <algrant@myrealbox.com> - 2011-10-13 07:00 -0700
                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Robert Myers <rbmyersusa@gmail.com> - 2011-10-14 10:54 -0700
                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-14 22:36 +0000
                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-15 09:26 +0200
                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-15 05:39 -0700
                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-15 14:56 +0200
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-17 08:37 +0100
                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-17 12:03 +0200
                                                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-17 11:13 +0100
                                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-17 22:30 +0200
                                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-17 14:47 -0700
                                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-18 11:33 +0200
                                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-18 10:21 +0100
                                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-18 08:16 +0100
                                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-18 14:26 +0200
                                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-18 13:32 +0100
                                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-18 17:47 +0200
                                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-18 17:51 +0100
                                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-19 10:37 +0200
                                                                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-19 09:36 +0100
                                                                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-19 11:46 +0200
                                                                      Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-19 10:45 +0100
                                                                        Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-19 13:11 +0200
                                                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-19 12:12 +0100
                                                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-19 16:22 +0200
                                                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-19 15:16 +0100
                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-15 20:16 +0000
                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Robert Myers <rbmyersusa@gmail.com> - 2011-10-15 16:26 -0700
                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-17 08:14 +0200
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) nmm1@cam.ac.uk - 2011-10-17 08:22 +0100
                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-17 11:39 +0200
                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) rpw3@rpw3.org (Rob Warnock) - 2011-10-17 21:00 -0500
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-18 05:44 +0200
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-17 21:35 -0700
                                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Jasen Betts <jasen@xnet.co.nz> - 2011-10-24 02:40 +0000
                                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-10-27 00:32 +0300
                                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-27 10:41 +0200
                                                Re: Infinity + Infinity (or NegInfinity - NegInfinity) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-10-27 13:10 +0300
                                                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-27 13:53 +0200
                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Keith Thompson <kst-u@mib.org> - 2011-10-12 12:34 -0700
                          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Al Grant <algrant@myrealbox.com> - 2011-10-13 06:39 -0700
                            Re: Infinity + Infinity (or NegInfinity - NegInfinity) James Kuyper <jameskuyper@verizon.net> - 2011-10-13 10:34 -0400
                              Re: Infinity + Infinity (or NegInfinity - NegInfinity) Al Grant <algrant@myrealbox.com> - 2011-10-14 00:54 -0700
              Re: Infinity + Infinity (or NegInfinity - NegInfinity) Larry Hewitt <larryhwtt@comporium.net> - 2011-10-09 21:35 -0400
                Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-10 04:37 +0200
                  Re: Infinity + Infinity (or NegInfinity - NegInfinity) Larry Hewitt <larryhwtt@comporium.net> - 2011-10-10 13:58 -0400
                    Re: Infinity + Infinity (or NegInfinity - NegInfinity) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-13 20:17 +0200
          Re: Infinity + Infinity (or NegInfinity - NegInfinity) Arivald <arivald_@AT_interia_DOT_.pl> - 2011-10-13 12:10 +0200

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#4258

In article <ase2n8-151.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>>
>> Aargh!  You were assuming a hidden bit and I was assume that there
>> wasn't one!  If you don't have one, there is no point in all that
>> faffing around with temp1.
>
>First of all: Both float and double does have hidden bits...

Yes, but Intel format doesn't and, as I said, you absolutely HAVE
to use extended precision to emulate true probabilistic rounding.
You can emulate float using double, but need either Intel or
IEEE 754 128-bit for double.  Intel isn't very precise, but the
extra bits are enough for almost all purposes.

>Second, I really don't get how you would like your code to work, here is 
>my version:

That would work for float, but not double.  All it does is round up
with probability 0.5, which is NOT what is wanted.  That form isn't
interesting, as it has no major advantages over forcing the last bit
to one (a truly ancient method) and certainly none over rounding to
nearest.

What you are trying to do, logically, is to calculate the result in
infinite precision and then round up the result according to the
ignored excess (treated as a [0,1) number relative to the last bit).
And it is this excess-dependent probability that gives the method
its advantages.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4260

nmm1@cam.ac.uk wrote:
> In article<ase2n8-151.ln1@ntp6.tmsw.no>,
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>> Second, I really don't get how you would like your code to work, here is
>> my version:
>
> That would work for float, but not double.  All it does is round up
> with probability 0.5, which is NOT what is wanted.  That form isn't
> interesting, as it has no major advantages over forcing the last bit
> to one (a truly ancient method) and certainly none over rounding to
> nearest.
>
> What you are trying to do, logically, is to calculate the result in
> infinite precision and then round up the result according to the
> ignored excess (treated as a [0,1) number relative to the last bit).
> And it is this excess-dependent probability that gives the method
> its advantages.

Oh!

This is indeed a totally different idea, now I understand what you meant 
with probabilistic (vs random) rounding.

This is _rather_ more difficult than random, and in fact a lot harder 
than any current rounding mode.

So what kind of hw support would you like in order to provide this?

Extended precision is the easy answer, but if that isn't available (and 
it will never be so for extended precision itself) what is the minimum 
hw support that makes it feasible?

For multiplication I believe having a fused FMAC (with no internal 
rounding after the FMUL step) would work, you could first calculate the 
FMUL result, then do it once more with FMAC, subtracting the original 
result, in order to get access to the bits that was rounded away?

For FADD I guess you take the sum and subtract the larger (in magnitude) 
of the inputs, then the smaller: The result is an indication of what got 
rounded away isn't it?

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4262

In article <fti2n8-t91.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>>
>> What you are trying to do, logically, is to calculate the result in
>> infinite precision and then round up the result according to the
>> ignored excess (treated as a [0,1) number relative to the last bit).
>> And it is this excess-dependent probability that gives the method
>> its advantages.
>
>This is indeed a totally different idea, now I understand what you meant 
>with probabilistic (vs random) rounding.
>
>This is _rather_ more difficult than random, and in fact a lot harder 
>than any current rounding mode.

Actually, no, it isn't - not if designed into the architecture.
The point is that operations can cut the calculation of the extra
bits short as soon as the comparator with the bit sequence gives
a definite answer.

>So what kind of hw support would you like in order to provide this?
>
>Extended precision is the easy answer, but if that isn't available (and 
>it will never be so for extended precision itself) what is the minimum 
>hw support that makes it feasible?

For emulation, all you need is some decent support for multiple
precision calculations, which has a LOT of other uses.  Addition
etc. are easy; division is best done by Newton-Raphson (and the
above design helps a lot with optimising that); and multiplication
needs only a facility to do the four (N/2)x(N/2)=>N products
separately.

For efficient implementation in hardware, all it needs is to be
designed in - which would involve a preliminary brain transplant
for most architects who have come up through modern 'computer
science' courses.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4263

nmm1@cam.ac.uk wrote:
> In article<fti2n8-t91.ln1@ntp6.tmsw.no>,
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>> This is _rather_ more difficult than random, and in fact a lot harder
>> than any current rounding mode.
>
> Actually, no, it isn't - not if designed into the architecture.
> The point is that operations can cut the calculation of the extra
> bits short as soon as the comparator with the bit sequence gives
> a definite answer.

The current standard requires the hw to carry around 3 extra bits, where 
the last bit is the 'sticky bit', it will be set if there are any set 
bits at all at or below this position, right?

For true probabilistic rounding you would need to replace this with 50 
or so bits, i.e. the full double-width result of a multiplication.

OTOH, you would also need a source of the same amount of random bits, so 
I suspect you could get effectively the same results while limiting the 
HW to something like 16-32 extra bits per operation.

>
>> So what kind of hw support would you like in order to provide this?
>>
>> Extended precision is the easy answer, but if that isn't available (and
>> it will never be so for extended precision itself) what is the minimum
>> hw support that makes it feasible?
>
> For emulation, all you need is some decent support for multiple
> precision calculations, which has a LOT of other uses.  Addition

I agree, this is definitely useful.

When I wrote my 128-bit fp library in 386 asm, I used integer only code 
simply because it was so much easier to get right.

> etc. are easy; division is best done by Newton-Raphson (and the
> above design helps a lot with optimising that); and multiplication
> needs only a facility to do the four (N/2)x(N/2)=>N products
> separately.

Agreed.
>
> For efficient implementation in hardware, all it needs is to be
> designed in - which would involve a preliminary brain transplant
> for most architects who have come up through modern 'computer
> science' courses.

It seems like 128-bit FP is getting some real support these days...

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4264

In article <dsn2n8-vf1.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>
>>> This is _rather_ more difficult than random, and in fact a lot harder
>>> than any current rounding mode.
>>
>> Actually, no, it isn't - not if designed into the architecture.
>> The point is that operations can cut the calculation of the extra
>> bits short as soon as the comparator with the bit sequence gives
>> a definite answer.
>
>The current standard requires the hw to carry around 3 extra bits, where 
>the last bit is the 'sticky bit', it will be set if there are any set 
>bits at all at or below this position, right?

Not 'carry around' - calculate.

>For true probabilistic rounding you would need to replace this with 50 
>or so bits, i.e. the full double-width result of a multiplication.

NO!!!  The probability of needing N bits is only 2^(1-N).  For all
operations up to the complexity of multiplication, the extra bits
come for free.  And, with multiplication, you have to do 90% of the
work to get those three bits EXACTLY right.  That is why NxN=>N
multiplication is normally VERY little slower than NxN=>N, when
it is provided.  And that leaves division, where Newton-Raphson
gives you exactly the increasing precision that is needed for
optimisation!

I did say that a brain transplant was often needed - you just need
to think in a different direction :-)

>OTOH, you would also need a source of the same amount of random bits, so 
>I suspect you could get effectively the same results while limiting the 
>HW to something like 16-32 extra bits per operation.

Yes.  Provided that you disambiguate randomly, even 16 bits gives
almost all of the advantages of infinite precision.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4266

nmm1@cam.ac.uk wrote:
> In article<dsn2n8-vf1.ln1@ntp6.tmsw.no>,
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>> The current standard requires the hw to carry around 3 extra bits, where
>> the last bit is the 'sticky bit', it will be set if there are any set
>> bits at all at or below this position, right?
>
> Not 'carry around' - calculate.

Sure, I though that was obvious? The hw has to merge all the lower bits 
in order to end up with those three bits (of which the first is the ulp 
bit, so only two extra really) that (together with the current rounding 
mode) directly determine the rounding direction.
>
>> For true probabilistic rounding you would need to replace this with 50
>> or so bits, i.e. the full double-width result of a multiplication.
>
> NO!!!  The probability of needing N bits is only 2^(1-N).  For all
> operations up to the complexity of multiplication, the extra bits
> come for free.  And, with multiplication, you have to do 90% of the
> work to get those three bits EXACTLY right.  That is why NxN=>N
> multiplication is normally VERY little slower than NxN=>N, when

Here you meant NxN->2N right?

Even for FMUL, the hw (as you've said) pretty much has to calculate all 
2N bits, in order to handle borderline cases exactly.

> it is provided.  And that leaves division, where Newton-Raphson
> gives you exactly the increasing precision that is needed for
> optimisation!

NR is actually better for division here, because you don't have to 
provide exact results, just _very_ very good, before the comparison with 
the random bitsource and actual rounding.

I'm assuming that what you intend is to have N excess bits (E) after the 
fp operation, then grab N random bits (R):

As long as E is >= R, you round up, otherwise down, right?

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4267

In article <o133n8-gs1.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>>
>>> For true probabilistic rounding you would need to replace this with 50
>>> or so bits, i.e. the full double-width result of a multiplication.
>>
>> NO!!!  The probability of needing N bits is only 2^(1-N).  For all
>> operations up to the complexity of multiplication, the extra bits
>> come for free.  And, with multiplication, you have to do 90% of the
>> work to get those three bits EXACTLY right.  That is why NxN=>N
>> multiplication is normally VERY little slower than NxN=>N, when
>
>Here you meant NxN->2N right?

Yes - the first one should be that.

>Even for FMUL, the hw (as you've said) pretty much has to calculate all 
>2N bits, in order to handle borderline cases exactly.
>
>> it is provided.  And that leaves division, where Newton-Raphson
>> gives you exactly the increasing precision that is needed for
>> optimisation!
>
>NR is actually better for division here, because you don't have to 
>provide exact results, just _very_ very good, before the comparison with 
>the random bitsource and actual rounding.

Precisely.

>I'm assuming that what you intend is to have N excess bits (E) after the 
>fp operation, then grab N random bits (R):
>
>As long as E is >= R, you round up, otherwise down, right?

Right.  Both the calculation and random number generation can be
streamed, and stop as soon as there is a clear decision.  I.e.
stop as soon as E != R.

I am not a hardware person, but my understanding is that this would
all be entirely straightforward, as fast as IEEE 754 rounding, and
use no more logic.  Of course, it would be a very different design
and could not be done that efficiently starting from an existing
one!

I am not expecting to see it, because it is thoroughly heretical
nowadays, and it would make debugging 'interesting', but it would
be interesting to experiment with a good emulation on complete,
real applications.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4210

On Sat, 15 Oct 2011 09:26:28 +0200, Terje Mathisen wrote:
> I would in fact be much _more_ useful to have a mode where rounding was
> arbitrary/random, and could even impact one or more extra low bits.

I would like one of those, myself, at least as a debugging alternative.

> I.e. if your code doesn't produce effectively the same results under
> such a regime, your algorithms are almost certainly broken.

Not necessarily (depending on your definition of "effectively"): anything 
that involves classification into discrete sets, or comparisons against 
thresholds, or quantization is eventually going to come across an example 
that could reasonably go either way, and then suddenly an insignificant 
floating point difference becomes a significant integer difference.  Yes, 
there is a sense in which these are "effectively" the same, but these 
sorts of thing are quite difficult to build reliable unit or compliance 
tests for.  I do understand the impulse to bit-exactness, but I know it's 
not the right answer...

Cheers,

-- 
Andrew

[toc] | [prev] | [next] | [standalone]

#4211

On Oct 15, 4:16 pm, Andrew Reilly <areilly...@bigpond.net.au> wrote:

>
> Not necessarily (depending on your definition of "effectively"): anything
> that involves classification into discrete sets, or comparisons against
> thresholds, or quantization is eventually going to come across an example
> that could reasonably go either way, and then suddenly an insignificant
> floating point difference becomes a significant integer difference.

We could hope that the stock market and lots of other things aren't
being run by software with such characteristics, but, I am fairly
certain that the hope is in vain.

Robert.

[toc] | [prev] | [next] | [standalone]

#4215

Andrew Reilly wrote:
> On Sat, 15 Oct 2011 09:26:28 +0200, Terje Mathisen wrote:
>> I would in fact be much _more_ useful to have a mode where rounding was
>> arbitrary/random, and could even impact one or more extra low bits.
>
> I would like one of those, myself, at least as a debugging alternative.
>
>> I.e. if your code doesn't produce effectively the same results under
>> such a regime, your algorithms are almost certainly broken.
>
> Not necessarily (depending on your definition of "effectively"): anything
> that involves classification into discrete sets, or comparisons against
> thresholds, or quantization is eventually going to come across an example
> that could reasonably go either way, and then suddenly an insignificant
> floating point difference becomes a significant integer difference.  Yes,
> there is a sense in which these are "effectively" the same, but these
> sorts of thing are quite difficult to build reliable unit or compliance
> tests for.  I do understand the impulse to bit-exactness, but I know it's
> not the right answer...

The need isn't really to be bit-exact, but to be bit-repeatable:

There are several important algorithms that depend on knowing that two 
independent calculations with the same inputs will result in the same 
exact result, i.e. to cover every single pixel in a triangle-tesselated 
world description.

Mike Abrash tells a fun story about how they wasted a week or so looking 
for a glitch in the Quake sw 3D pipeline, where they would very 
occasionally spot a momentary glitch giving a single pixel error.

They finally discovered that they had been sold a machine with a fake 
100 MHz cpu: It was really only 90 MHz but tested by the white box 
manufacturer to be "totally solid at 100 MHz, so we'll save a few bucks".

It turned out that running at 100 Mhz it would not always manage to 
finalize all the low order bits of all fp operations, effectively 
resulting in spurious loss of precision.

So, at least for this particular code, having really random rounding 
would not be good.:-(

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4218

In article <ontsm8-5jq2.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>Andrew Reilly wrote:
>> On Sat, 15 Oct 2011 09:26:28 +0200, Terje Mathisen wrote:
>>> I would in fact be much _more_ useful to have a mode where rounding was
>>> arbitrary/random, and could even impact one or more extra low bits.
>>
>> I would like one of those, myself, at least as a debugging alternative.
>>
>>> I.e. if your code doesn't produce effectively the same results under
>>> such a regime, your algorithms are almost certainly broken.
>>
>> Not necessarily (depending on your definition of "effectively"): anything
>> that involves classification into discrete sets, or comparisons against
>> thresholds, or quantization is eventually going to come across an example
>> that could reasonably go either way, and then suddenly an insignificant
>> floating point difference becomes a significant integer difference.  Yes,
>> there is a sense in which these are "effectively" the same, but these
>> sorts of thing are quite difficult to build reliable unit or compliance
>> tests for.  I do understand the impulse to bit-exactness, but I know it's
>> not the right answer...
>
>The need isn't really to be bit-exact, but to be bit-repeatable:
>
> [ Example of low bit variations omitted. ]

Yes, but much of that is due to the deficiencies of programming
languages.  In Algol 68, you had dynamic constants, and so could
calculate an expression once if you needed its value to be the
same everywhere you used it later.  This is exactly what we used
to do with variables in Fortran and Algol 60 to defend ourselves
against the CDC's and similar variations.

There is a modern computer science dogma that this is implicit in
various specifications (especially C and its derivations), but
that is complete nonsense.  Even a mere 20 years ago, the usual
interpretation was that it was not a requirement.  My position is
that, if you need it, you should specify it!


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4221

nmm1@cam.ac.uk wrote:
> Yes, but much of that is due to the deficiencies of programming
> languages.  In Algol 68, you had dynamic constants, and so could
> calculate an expression once if you needed its value to be the
> same everywhere you used it later.  This is exactly what we used
> to do with variables in Fortran and Algol 60 to defend ourselves
> against the CDC's and similar variations.
>
> There is a modern computer science dogma that this is implicit in
> various specifications (especially C and its derivations), but
> that is complete nonsense.  Even a mere 20 years ago, the usual
> interpretation was that it was not a requirement.  My position is
> that, if you need it, you should specify it!

I agree with you Nick, I just had to write about the Quake example 
because it shows some of the traps bit-repeatable fp have led to.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4234

<nmm1@cam.ac.uk> wrote:
+---------------
| Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
| >The need isn't really to be bit-exact, but to be bit-repeatable:
...
| Yes, but much of that is due to the deficiencies of programming
| languages.  In Algol 68, you had dynamic constants, and so could
| calculate an expression once if you needed its value to be the
| same everywhere you used it later.  This is exactly what we used
| to do with variables in Fortran and Algol 60 to defend ourselves
| against the CDC's and similar variations.
+---------------

Common Lisp has the LOAD-TIME-VALUE special form specifically to
provide such "dynamic" constants:

    http://www.lispworks.com/documentation/HyperSpec/Body/s_ld_tim.htm
    Special Operator LOAD-TIME-VALUE

    Syntax:
    load-time-value form &optional read-only-p => object
    ...
    Description:
    LOAD-TIME-VALUE provides a mechanism for delaying evaluation of FORM
    until the expression is in the run-time environment; see Section 3.2
    (Compilation).

    READ-ONLY-P designates whether the result can be considered a
    "constant object". If T, the result is a read-only quantity that can,
    if appropriate to the implementation, be copied into read-only space
    and/or coalesced with similar constant objects from other programs.
    If NIL (the default), the result must be neither copied nor coalesced;
    it must be considered to be potentially modifiable data.
    ...

The point is that you can bury a LOAD-TIME-VALUE expression deep in
some larger expression with the assurance that it will be evaluated
only once, when the program loads.[1]


-Rob

[1] I'm slightly oversimplifying here. See the referenced URL for the
    full details of the semantics. In particular, note the first example
    [caveat: CLHS examples are non-normative]:

      ;;; The function INCR1 always returns the same value, even in different images.
      ;;; The function INCR2 always returns the same value in a given image, 
      ;;; but the value it returns might vary from image to image.
      (defun incr1 (x) (+ x #.(random 17)))
      (defun incr2 (x) (+ x (load-time-value (random 17))))

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [next] | [standalone]

#4240

Now that you mentioned quake I wonder what would happen to the Quake 3 (and 
RTCW ?) engine where there is supposed to be a rounding error which could 
lead to slightly higher and slightly further jumps because of favorable 
rounding errors from floating point (to integers ?) at certain frames per 
second, at least sometime like that... ;)

Would a variable rounding solve this "exploit" or not ? ;) :)

Bye,
  Skybuck.

[toc] | [prev] | [next] | [standalone]

#4242

On 10/16/2011 11:14 PM, Terje Mathisen wrote:
> Andrew Reilly wrote:
>> On Sat, 15 Oct 2011 09:26:28 +0200, Terje Mathisen wrote:
>>> I would in fact be much _more_ useful to have a mode where rounding was
>>> arbitrary/random, and could even impact one or more extra low bits.
>>
>> I would like one of those, myself, at least as a debugging alternative.
>>
>>> I.e. if your code doesn't produce effectively the same results under
>>> such a regime, your algorithms are almost certainly broken.
>>
>> Not necessarily (depending on your definition of "effectively"): anything
>> that involves classification into discrete sets, or comparisons against
>> thresholds, or quantization is eventually going to come across an example
>> that could reasonably go either way, and then suddenly an insignificant
>> floating point difference becomes a significant integer difference. Yes,
>> there is a sense in which these are "effectively" the same, but these
>> sorts of thing are quite difficult to build reliable unit or compliance
>> tests for. I do understand the impulse to bit-exactness, but I know it's
>> not the right answer...
>
> The need isn't really to be bit-exact, but to be bit-repeatable:
>
> There are several important algorithms that depend on knowing that two
> independent calculations with the same inputs will result in the same
> exact result, i.e. to cover every single pixel in a triangle-tesselated
> world description.
>
> Mike Abrash tells a fun story about how they wasted a week or so looking
> for a glitch in the Quake sw 3D pipeline, where they would very
> occasionally spot a momentary glitch giving a single pixel error.
>
> They finally discovered that they had been sold a machine with a fake
> 100 MHz cpu: It was really only 90 MHz but tested by the white box
> manufacturer to be "totally solid at 100 MHz, so we'll save a few bucks".
>
> It turned out that running at 100 Mhz it would not always manage to
> finalize all the low order bits of all fp operations, effectively
> resulting in spurious loss of precision.
>
> So, at least for this particular code, having really random rounding
> would not be good.:-(
>
> Terje

I remember when Mike and John found this bug.  I think it was in an 
early P6 or P5.We were preparing for a tiger team effort, when they came 
back and told us they had an overclocked CPU.

[toc] | [prev] | [next] | [standalone]

#4381

On 2011-10-15, Terje Mathisen <"terje.mathisen at tmsw.no"> wrote:

> I would in fact be much _more_ useful to have a mode where rounding was 
> arbitrary/random, and could even impact one or more extra low bits.

Intel tried something like that in the 90s :^)

-- 
⚂⚃ 100% natural

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

#4418

Jasen Betts <jasen@xnet.co.nz> writes:
> On 2011-10-15, Terje Mathisen <"terje.mathisen at tmsw.no"> wrote:
> > I would in fact be much _more_ useful to have a mode where rounding was 
> > arbitrary/random, and could even impact one or more extra low bits.
> 
> Intel tried something like that in the 90s :^)

Until Terje himself broke the feature!

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#4431

Phil Carmody wrote:
> Jasen Betts<jasen@xnet.co.nz>  writes:
>> On 2011-10-15, Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>>> I would in fact be much _more_ useful to have a mode where rounding was
>>> arbitrary/random, and could even impact one or more extra low bits.
>>
>> Intel tried something like that in the 90s :^)
>
> Until Terje himself broke the feature!

Rather fixed it again:

I did write most of the sw workaround for the FDIV (and FPATAN) bug on 
the Pentium.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4434

Terje Mathisen <"terje.mathisen at tmsw.no"> writes:
> Phil Carmody wrote:
> > Jasen Betts<jasen@xnet.co.nz>  writes:
> >> On 2011-10-15, Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
> >>> I would in fact be much _more_ useful to have a mode where rounding was
> >>> arbitrary/random, and could even impact one or more extra low bits.
> >>
> >> Intel tried something like that in the 90s :^)
> >
> > Until Terje himself broke the feature!
> 
> Rather fixed it again:
> 
> I did write most of the sw workaround for the FDIV (and FPATAN) bug on
> the Pentium.

That's what I was trying to imply. If we're pretending the bug was 
feature, then your fix 'broke' it. (I was assuming FDIV was what was
being refered to.)

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#4437

Phil Carmody wrote:
> Terje Mathisen<"terje.mathisen at tmsw.no">  writes:
>> I did write most of the sw workaround for the FDIV (and FPATAN) bug on
>> the Pentium.
>
> That's what I was trying to imply. If we're pretending the bug was
> feature, then your fix 'broke' it. (I was assuming FDIV was what was
> being refered to.)

OK, sorry for being particularly dense today.

FDIV did provide one sample point that was relevant though: It showed 
that pretty close to zero applications and their users noticed anything 
wrong even though divisions would drop 0 to 45 bits when the divisor hit 
one of those 5 in 1024 leading mantissa bit patterns.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.arch

csiph-web