Trajectories

[Colin Bartlett]

I can't find who first said this, but a quote I've used - with success - is:
"It is better to be approximately right than precisely wrong."
(Unfortunately I had *very* little success in persuading people to
replace figures like $10,563.27 with $10,563. And that was
deliberately limiting my intention knowing the likely resistance: what
I really wanted to get them to do was use $10,560 to make it clear
that the $10,563.27 was approximate, not exact.)

I don't know much about Numerical Analysis, but I do know enough to be
very wary about just increasing precision.

 

[Todd Benson]

The physical limitations imposed on arbitrary-precision decimal computation
by binary representation are something you should know *before* arguing that
one representation is better than another.

I think Marnen originally was suggesting that the imprecisions will
stack, like an arrow at a target going more and more off course during
its flight, of course depending on the application. For some apps,
it's totally reasonable to see something go chaotic because of these
things.

For a short and unimportant game I'm playing, I wouldn't be upset.
But, for a game that takes 10's of hours and have it ride my butt
later at a crucial moment, I might just call that a bug.

Does the imprecision in the calculation stack in ballistic calcs? A
virtual magic bullet as it were? I'm not sure, but I'm guessing it
doesn't to great effect.

Todd

 

[Eleanor McHugh]

I think Marnen originally was suggesting that the imprecisions will
stack, like an arrow at a target going more and more off course during
its flight, of course depending on the application. For some apps,
it's totally reasonable to see something go chaotic because of these
things.

This isn't an issue of chaotic behaviour (that has a very fixed =20
meaning mathematically) but of unnoticeable error. The difference =20
between 1e10-13 and 2e10-13 matters a lot when working on a system =20
which needs to be accurate to a resolution of 1e10-14 but not when =20
working to a resolution of 1e10-4. The additional nine decimal places =20=

tell us nothing meaningful in this latter case as we'll still end up =20
rounding the result to zero.

For a short and unimportant game I'm playing, I wouldn't be upset.
But, for a game that takes 10's of hours and have it ride my butt
later at a crucial moment, I might just call that a bug.

That's not a bug but a fundamental outcome of the nature of binary =20
coded non-integral numbers. Many rational non-integral numbers cannot =20=

be expressed accurately in binary representations, whilst binary coded =20=

decimal brings a whole host of other problems: lower information =20
density, higher memory usage, and heavier processing load. BCD also =20
does nothing to resolve the problem of how to represent irrational =20
numbers such as =CF=80.

Does the imprecision in the calculation stack in ballistic calcs? A
virtual magic bullet as it were? I'm not sure, but I'm guessing it
doesn't to great effect.

The imprecision can indeed stack for complex ballistics systems, =20
depending on the complexity of the forces involved. However to the =20
extent of the precision chosen for performing these calculations the =20
resultant inaccuracy is irrelevant.

http://en.wikipedia.org/wiki/Accuracy_and_precision explains all of =20
this in reasonable detail.


Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net

 

[Marnen Laibow-Koser]

The physical limitations imposed on arbitrary-precision decimal
computation by binary representation are something you should know
*before* arguing that one representation is better than another.

I am aware of the limitations. I believe I'm even fully aware of them.
What do you think I have failed to take into account?

Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net

Best,

 

[Marnen Laibow-Koser]

This isn't an issue of chaotic behaviour (that has a very fixed
meaning mathematically) but of unnoticeable error. The difference
between 1e10-13 and 2e10-13 matters a lot when working on a system
which needs to be accurate to a resolution of 1e10-14 but not when
working to a resolution of 1e10-4. The additional nine decimal places
tell us nothing meaningful in this latter case as we'll still end up
rounding the result to zero.


That's not a bug but a fundamental outcome of the nature of binary
coded non-integral numbers.

If it gives you the wrong answer, it's a bug. Period. If your
representation cannot give you the precision you need for the task at
hand, then you need a different representation. Period. The end user
doesn't care about your representation -- he cares about getting the
right answer.

[...]

BCD also
does nothing to resolve the problem of how to represent irrational
numbers such as π.

No, becuase that's impossible to do with a finite representation AFAIK.
If I'm wrong, I would love to know how this can be done.

[...]

Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net

Best,

 

[Paul Smith]

This isn't an issue of chaotic behaviour (that has a very fixed
meaning mathematically) but of unnoticeable error. The difference
between 1e10-13 and 2e10-13 matters a lot when working on a system
which needs to be accurate to a resolution of 1e10-14 but not when
working to a resolution of 1e10-4. The additional nine decimal places
tell us nothing meaningful in this latter case as we'll still end up
rounding the result to zero.


That's not a bug but a fundamental outcome of the nature of binary
coded non-integral numbers.

If it gives you the wrong answer, it's a bug. =A0Period. =A0 If your
representation cannot give you the precision you need for the task at
hand, then you need a different representation. =A0Period. =A0The end use= r
doesn't care about your representation -- he cares about getting the
right answer.

[...]

BCD also
does nothing to resolve the problem of how to represent irrational
numbers such as =F0.

No, becuase that's impossible to do with a finite representation AFAIK.
If I'm wrong, I would love to know how this can be done.

Your above two points appear to be in conflict with each other.

[...]

Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net

Best,

--=20
Paul Smith
http://www.nomadicfun.co.uk

(e-mail address removed)

 

[Marnen Laibow-Koser]

Your above two points appear to be in conflict with each other.

Well, they're not "my" two points -- Eleanor wrote the first line, and I
think you missed the "if" on the second one.

 

[Paul Smith]

Well, they're not "my" two points -- Eleanor wrote the first line, and I
think you missed the "if" on the second one.

No, I really mean your two points.

On the one hand, you say "If it gives you the wrong answer, it's a
bug. Period. If your representation cannot give you the precision
you need for the task at hand, then you need a different
representation. Period."

Then you say "No, becuase [representing irrational numbers is]
impossible to do with a finite representation AFAIK. If I'm wrong, I
would love to know how this can be done."

 

[Marnen Laibow-Koser]

Paul Smith wrote:
[...]

No, I really mean your two points.

On the one hand, you say "If it gives you the wrong answer, it's a
bug. Period. If your representation cannot give you the precision
you need for the task at hand, then you need a different
representation. Period."

Then you say "No, becuase [representing irrational numbers is]
impossible to do with a finite representation AFAIK. If I'm wrong, I
would love to know how this can be done."

Interesting question. I don't think that's a contradiction so much as
an acknowledgement of the fundamental limitations of digital computing.
With data structures like BigDecimal and Rational, we can exactly
represent any rational number we like in a finite amount of storage.

Irrational numbers are different. We could represent them exactly on an
analog computer such as a slide rule, but there is no general method
that I am aware of for doing so in a finite amount of digital storage.
Certain numbers, such as square roots, can be represented with tricks
like quadratic equations to which they are the root, but that won't work
for transcendental numbers like e or π. We can calculate those numbers
to millions of decimal places if we need to -- but unlike rational
numbers, we can never store them exactly.

So we do the best we can. Since rational numbers can be represented
exactly, it makes sense to do so. Since (many) irrational numbers
cannot be represented exactly, we get as close as we can.

--
Paul Smith
http://www.nomadicfun.co.uk

(e-mail address removed)

Best,

 

[Caleb Clausen]

Certain numbers, such as square roots, can be represented with tricks
like quadratic equations to which they are the root, but that won't work
for transcendental numbers like e or =F0. We can calculate those numbers
to millions of decimal places if we need to -- but unlike rational
numbers, we can never store them exactly.

transcendentals can also be represented exactly by formulae with a
finite number of bits:

pi/4 =3D 1 - 1/3 + 1/5 - 1/7 + ....
#that might not be the exact right formula, but you get the idea

this can also be represented by a (fairly short) program:

def pi_over_4
result=3D0
sign=3D1
for i in 0..Infinity do
result+=3D Rational.new(sign,2*i+1)
sign=3D-sign
end
return result
end

of course, this would take an infinite amount of time to execute, and
require an infinite amount of memory to store the result, but in a
lazy functional language like haskell, that would not be true. also,
in a functional language, I _believe_ you can manipulate programs like
the one above as if they were numbers. how often is that capability
really needed? maybe mathematica actually works this way, but it's
probably the only one.

on the other hand, there is another class of (real) numbers, the
incomputables, beyond the transcendentals, for which there is no
(finite length) formula or program possible.... but how often do you
need to write a program which deals with (an exact representation of)
those?

 

[Marnen Laibow-Koser]

transcendentals can also be represented exactly by formulae with a
finite number of bits:

pi/4 = 1 - 1/3 + 1/5 - 1/7 + ....
#that might not be the exact right formula, but you get the idea

Oh, good point. Hadn't thought about that.

this can also be represented by a (fairly short) program:

def pi_over_4
result=0
sign=1
for i in 0..Infinity do
result+= Rational.new(sign,2*i+1)
sign=-sign
end
return result
end

of course, this would take an infinite amount of time to execute, and
require an infinite amount of memory to store the result, but in a
lazy functional language like haskell, that would not be true. also,
in a functional language, I _believe_ you can manipulate programs like
the one above as if they were numbers.

To some extent, you can do that in Ruby. Proc and Method are
first-class objects.

how often is that capability
really needed?

Which capability? Functional programming? It can be useful.

maybe mathematica actually works this way, but it's
probably the only one.

I'm not sure.

on the other hand, there is another class of (real) numbers, the
incomputables, beyond the transcendentals, for which there is no
(finite length) formula or program possible.... but how often do you
need to write a program which deals with (an exact representation of)
those?

I don't know. Are any important constants incomputable?

Best,

 

[Colin Bartlett]

... transcendentals can also be represented exactly by formulae with a
finite number of bits:

Doesn't that depend on the transcendental?

... on the other hand, there is another class of (real) numbers, the
incomputables, beyond the transcendentals, for which there is no
(finite length) formula or program possible.... but how often do you
need to write a program which deals with (an exact representation of)
those?

"Most" real numbers are both transcendental and non computable.
http://en.wikipedia.org/wiki/Transcendental_number
... almost all real and complex numbers are transcendental ...
http://en.wikipedia.org/wiki/Computable_number
... almost all real numbers are not computable ...

... Are any important constants incomputable?

An interesting question. There are, for example Chaitin's constants:
http://en.wikipedia.org/wiki/Chaitin's_constant
http://mathworld.wolfram.com/ChaitinsConstant.html
which are (I assume) important in computation theory
but (very?) unlikely to be useful in normal problems!
(Although it's slightly risky to make that statement
about anything: even obscure mathematics
sometimes turns out to have "real world" importance.)

Returning to the original question(s) in this thread:

* From years ago I recall Fractint being written using integers
for speed (and possibly also for precision). But now:
http://en.wikipedia.org/wiki/Fractint
"... the first versions of it computed fractals by using only
integer arithmetic (also known as fixed-point arithmetic),
which led to much faster rendering on x86 computers
without math coprocessors. Since then, floating-point arithmetic
and "arbitrary-precision" modes have been added,
the latter of which emulates an arbitrarily large mantissa in RAM.
The arbitrary-precision mode is slow even on modern computers. ..."

* Depending on the problem, inherent uncertainty in the data
may make the notion of an "exact" number misleading.
I'm not arguing against using "precise" representations,
I'm just saying that before using more precise representations
one should ask whether what that gives (and costs,
in terms of performance) is worth having. There may well
be "wrong" answers without there being unique "right" answers,
just degrees of "rightness".

For example, using 22/7 for pi is an error of about 0.04%.
(Using Ruby Math:I = 3.14159265358979 as an approximation to pi.)
Using 355/113 is an error of less than (10 ** -7)%.
The circumference of the Earth is about 40,000 km, and depending on
where and how you measure it, the "actual" figure is +/- about 75 km.
Using 22/7 instead of pi for the circumference gives an "error" of 16 km,
which may be "reasonable" given the inherent "uncertainty"
in the circumference (depending on what you want to do).
Using 355/113 instead of pi gives an "error" of about 4 metres,
which for most(?) purposes is insignificant compared with
the inherent "uncertainty" in the circumference.

I'm to some extent guilty of not following my own precepts:
for financial calculations I mostly use double precision floats,
and I suspect that for much of those calculations
using single precision floats would be sufficiently accurate.
I don't do that because double precision floats are fast,
and with double precision I don't need to worry so much
about "rounding errors". But I do try to present the results
in ways which do not give an impression of "spurious accuracy".

 

[Caleb Clausen]

... transcendentals can also be represented exactly by formulae with a
finite number of bits:

Doesn't that depend on the transcendental? [snip]
"Most" real numbers are both transcendental and non computable.
http://en.wikipedia.org/wiki/Transcendental_number
... almost all real and complex numbers are transcendental ...
http://en.wikipedia.org/wiki/Computable_number
... almost all real numbers are not computable ...

When I said 'transcendental', I meant a transcendental which is not
incomputable. Just as when Marnen said 'irrational', he meant an
irrational which is not transcendental.

 

[Caleb Clausen]

To some extent, you can do that in Ruby. Proc and Method are
first-class objects.

Yeah, but you can't manipulate their results when they return one if
they ever do as if they were numbers.

Which capability? Functional programming? It can be useful.

The capability to represent transcendental numbers exactly. I mean,
how much precision do you really need?

 

[Marnen Laibow-Koser]

Caleb Clausen wrote:
[...]

Yeah, but you can't manipulate their results when they return one if
they ever do as if they were numbers.

Of course you can, unless I'm totally misunderstanding. Got a concrete
example

The capability to represent transcendental numbers exactly. I mean,
how much precision do you really need?

Depends on the task. I suspect a couple hundred decimals would be the
most you'd ever really need, and a couple of decades of decimals would
probably suffice for most cases.


Best,

 

[Caleb Clausen]

Of course you can, unless I'm totally misunderstanding. Got a concrete
example

The pi_over_4 method I posted earlier is a good one. You can't
manipulate the _future_ result of that as if it were a number, because
(among other things) it never returns. Need a lazy functional language
for that kind of thing. (If that even suffices....)

_Maybe_ you could write a futures library and implement the pi_over_4
formula within that in some kind of useful way, but idunno.... I kind
of think you need laziness built into the core language for something
like that to be useful.

 

[Marnen Laibow-Koser]

The pi_over_4 method I posted earlier is a good one. You can't
manipulate the _future_ result of that as if it were a number, because
(among other things) it never returns. Need a lazy functional language
for that kind of thing. (If that even suffices....)

You can't manipulate the future in any language that I'm aware of --
it's not there to manipulate yet! Are you thinking of lisp's
tail-recursion optimization?

 

[Aldric Giacomoni]

The pi_over_4 method I posted earlier is a good one. You can't
manipulate the _future_ result of that as if it were a number, because
(among other things) it never returns. Need a lazy functional language
for that kind of thing. (If that even suffices....)

_Maybe_ you could write a futures library and implement the pi_over_4
formula within that in some kind of useful way, but idunno.... I kind
of think you need laziness built into the core language for something
like that to be useful.

Well, we -can- make laziness work.. Look at this:
http://innig.net/software/ruby/closures-in-ruby.rb
Do a search for 'fibonacci' and check out the lazy implementation.

 

[Eleanor McHugh]

You can't manipulate the future in any language that I'm aware of --
it's not there to manipulate yet! Are you thinking of lisp's
tail-recursion optimization?

Yes you can: http://en.wikipedia.org/wiki/Futures_and_promises


Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net

 

[Aldric Giacomoni]

Yes you can: http://en.wikipedia.org/wiki/Futures_and_promises

Looks like there's no gem for this.
Yet.