VR roundoff error---integers?

In computer algebra, Maple, if I forced basic operations
to be with many digit integers,
as opposed to the arbitrary precision decimal stuff my version can do,
I get graphically convincing results
for a simulation Raman lasing without inversion.

This provided an interesting experience in my thesis where colleagues
were mirroring an abusive authoritative remark :
"There must be something wrong" when I smoothed the VR, er graphics.

I hammered back that they might be wrong and they should look
for a mistake too in their Fortran code so I be the only one risking
looking for a mistake that wasn't there forever and looking like an idiot.

We managed to wrest an analysis of the fortran code which I turned around
into a synthesis of maple code and found :
"On the other hand, there may be something right!"

So, VR may require another representation of numbers, even if someone
who has invested a lifetime, albeit much shorter than mine,
thinks there must be something wrong with that idea.

;-)

For my job one of the things that I ended up writing was a scheduling engine.  In this engine I was trying to allow people to schedule tasks of arbitrary time, so that if someone wanted to schedule somethng that was 0.3hrs long, they could do so.  I figured that as long as I could keep everything down to a couple decimal places, that everything would round out.

The issue of binary vs decimal counting is a much larger one than I expected; even simple numbers like 5.6 (not a real example) would cause significant roundoff issues the moment I'd assign it to a double, and quickly escalate to visibility after they had been subtracted and multiplied a couple times.  I don't think that a custom number system would be a terribly great requirement for a language that reaches down to the individual OpenGL calls running the entire system, but finding some way to get binary numbers act more like decimal numbers would really help when it comes to making arithmetic just work.

On Wed, 2007-05-16 at 13:39 -0800, [hidden email] wrote:
In the original Apple ][, with integer basic installed, there was
nothing to the right of the decimal point, as all calculations resulted
in an integer. For graphics it was fast... 7 times faster than AppleSoft
Floating Point Basic. If you are plotting to a finite point on the
screen, using whole numbers, then there is no need to consider floating
point at all. Woz came up with that, as he did everything else. IMHO he
still should be the guiding light at Apple. Ric
 
--

There's a number-representation choice that is muddied by deciding what to do
about the result of operations such as the composition of matrices.

Here are some choices:

1. Rational (infinite precision) storage and arithmetic. Do everything as
bignums and ratios of bignums.  Can be quite slow.

2. Integer storage and truncated arithmetic. Scale the numbers to be integers,
but after division, just keep the integer.

3. Double precision.

I know that some engineering CAD systems in the '80's did (2), but it I'm not
certain that there is any advantage to this over (3) on today's machines. (There
may be. I just don't know.)

Note that we're really talking about the geometry model here, not rendering. The
Croquet architecture makes a very nice distinction between the two: the geometry
that must be bit-identical between participants is that which is serialized in
the one-time sync (join) operation (or in media managers for immutable data).
Rendering must not store any results within the model, and can use whatever is
fastest or most convenient, and merely has to be "accurate enough." Because
results are not stored in the model, there's no accumulation of error there.

For geometry, the difference between (1) vs. (2)/(3) comes into play when trying
to compute results of movement or composition. I think in principle, one could
TRY to avoid this by deferring all arithmetic until needed (e.g., for
rendering).  For example, wrt composition, one could store as integers only the
local coordinates or dimensions of each object in the scene graph. But this is
the road to hell. I don't recall ever seeing a successful CAD system use
anything except model coordinates as the internal representation. Not only would
you have to lazily compute composition all the time, but you would have to
compose the object's event history all the time. Yuck.


Ric Moore wrote:
--
Howard Stearns
University of Wisconsin - Madison
Division of Information Technology
mailto:[hidden email]
office:+1-608-262-3724
mobile:+1-608-658-2419

Hi, Howard,
    I agree that doubles are probably the path to ultimate success.  While they are big (each number is 8 bytes), Modern processors almost all use a floating point unit internally which does its calculations in long doubles with one or two guardbits, so there is no calculation penalty.  Storing each double does encounter some time loss on 32 bit systems, requiring two writes to enter the data into memory.  For 3 axis coordinates, this translates to 6 memory writes for each node in the structure, perhaps more depending on how the structure is defined.
This is offset by the better results that are obtained, yielding greater undistorted range, finer resolution to things like gravity, friction and so forth (maybe field calculations in the future).

    Another impact occurs when a structure exceeds the cache memory size, and for modern processors this is a two stage hit, from the internal cache, to the external cache and from the external cache to main memory.  There is a rather famous algorithm on the internet right now that suffers great degradation when each of these cache limits is exceeded.  The main memory one is the big one, because it causes a "Page Miss" and cache flush and load.  If the objects are simple, the nodes are few and this won't happen.  But as objects grow in size and complexity, these cache misses will occur with greater regularity.  However there is no workaround, other than some form of purging unneeded elements from the calculation.  I believe this was touched on earlier in the discussion. 
   
    With multiple processors, some offloadig of the calculations could occur if the VM were configured to take advantage of this capability.  This would have a very high impact on processing, because not only does another processor become involved, but with some (perhaps most) processors, there is local cache allocated to each processor, which would have the effect of permitting more calculations before a cache miss occured, and of course the multiple processor calculation benefit.  The remaining issue becomes memory bandwidth, which is limited by the system design as well as the memory technology employed.

    To sum it up, I think double precision is the preferred resolution for math, and that the VM should support parallel processing to the maximum extent possible.  However the loadsharing algorithm must be really efficient to make this economically feasible on consumer systems.  I also want to emphasize that while this may seem like a "super system" now, it is becomming the standard, as more and more manufacturers realize the benefits of 64 bit parallel processors as a reasonable means to obtain higher throughput.

Regards,
Les H
On Thu, 2007-05-17 at 11:58 -0500, Howard Stearns wrote:

There's a number-representation choice that is muddied by deciding what to do 
about the result of operations such as the composition of matrices.

Here are some choices:

1. Rational (infinite precision) storage and arithmetic. Do everything as 
bignums and ratios of bignums.  Can be quite slow.

2. Integer storage and truncated arithmetic. Scale the numbers to be integers, 
but after division, just keep the integer.

3. Double precision.

I know that some engineering CAD systems in the '80's did (2), but it I'm not 
certain that there is any advantage to this over (3) on today's machines. (There 
may be. I just don't know.)

Note that we're really talking about the geometry model here, not rendering. The 
Croquet architecture makes a very nice distinction between the two: the geometry 
that must be bit-identical between participants is that which is serialized in 
the one-time sync (join) operation (or in media managers for immutable data). 
Rendering must not store any results within the model, and can use whatever is 
fastest or most convenient, and merely has to be "accurate enough." Because 
results are not stored in the model, there's no accumulation of error there.

For geometry, the difference between (1) vs. (2)/(3) comes into play when trying 
to compute results of movement or composition. I think in principle, one could 
TRY to avoid this by deferring all arithmetic until needed (e.g., for 
rendering).  For example, wrt composition, one could store as integers only the 
local coordinates or dimensions of each object in the scene graph. But this is 
the road to hell. I don't recall ever seeing a successful CAD system use 
anything except model coordinates as the internal representation. Not only would 
you have to lazily compute composition all the time, but you would have to 
compose the object's event history all the time. Yuck.


Ric Moore wrote:
> On Wed, 2007-05-16 at 13:39 -0800, [hidden email] wrote:
>> In computer algebra, Maple, if I forced basic operations 
>> to be with many digit integers, 
>> as opposed to the arbitrary precision decimal stuff my version can do, 
>> I get graphically convincing results 
>> for a simulation Raman lasing without inversion.
>>
>> This provided an interesting experience in my thesis where colleagues
>> were mirroring an abusive authoritative remark :
>> "There must be something wrong" when I smoothed the VR, er graphics.
>>
>> I hammered back that they might be wrong and they should look 
>> for a mistake too in their Fortran code so I be the only one risking
>> looking for a mistake that wasn't there forever and looking like an idiot.
>>
>> We managed to wrest an analysis of the fortran code which I turned around
>> into a synthesis of maple code and found :
>> "On the other hand, there may be something right!"
>>
>> So, VR may require another representation of numbers, even if someone
>> who has invested a lifetime, albeit much shorter than mine,
>> thinks there must be something wrong with that idea.
> 
> In the original Apple ][, with integer basic installed, there was
> nothing to the right of the decimal point, as all calculations resulted
> in an integer. For graphics it was fast... 7 times faster than AppleSoft
> Floating Point Basic. If you are plotting to a finite point on the
> screen, using whole numbers, then there is no need to consider floating
> point at all. Woz came up with that, as he did everything else. IMHO he
> still should be the guiding light at Apple. Ric
>  

Sorry for the double reply (pun definitely not intended!)

    In rendering the textures, if including any surface dimensionality, I believe they would have to be handled as doubles as well.  But I am willing to
be proven wrong.  I am after all, more engineer than artist or graphics specialist.

Regards,
Les H
On Thu, 2007-05-17 at 11:58 -0500, Howard Stearns wrote:

There's a number-representation choice that is muddied by deciding what to do 
about the result of operations such as the composition of matrices.

Here are some choices:

1. Rational (infinite precision) storage and arithmetic. Do everything as 
bignums and ratios of bignums.  Can be quite slow.

2. Integer storage and truncated arithmetic. Scale the numbers to be integers, 
but after division, just keep the integer.

3. Double precision.

I know that some engineering CAD systems in the '80's did (2), but it I'm not 
certain that there is any advantage to this over (3) on today's machines. (There 
may be. I just don't know.)

Note that we're really talking about the geometry model here, not rendering. The 
Croquet architecture makes a very nice distinction between the two: the geometry 
that must be bit-identical between participants is that which is serialized in 
the one-time sync (join) operation (or in media managers for immutable data). 
Rendering must not store any results within the model, and can use whatever is 
fastest or most convenient, and merely has to be "accurate enough." Because 
results are not stored in the model, there's no accumulation of error there.

For geometry, the difference between (1) vs. (2)/(3) comes into play when trying 
to compute results of movement or composition. I think in principle, one could 
TRY to avoid this by deferring all arithmetic until needed (e.g., for 
rendering).  For example, wrt composition, one could store as integers only the 
local coordinates or dimensions of each object in the scene graph. But this is 
the road to hell. I don't recall ever seeing a successful CAD system use 
anything except model coordinates as the internal representation. Not only would 
you have to lazily compute composition all the time, but you would have to 
compose the object's event history all the time. Yuck.


Ric Moore wrote:
> On Wed, 2007-05-16 at 13:39 -0800, [hidden email] wrote:
>> In computer algebra, Maple, if I forced basic operations 
>> to be with many digit integers, 
>> as opposed to the arbitrary precision decimal stuff my version can do, 
>> I get graphically convincing results 
>> for a simulation Raman lasing without inversion.
>>
>> This provided an interesting experience in my thesis where colleagues
>> were mirroring an abusive authoritative remark :
>> "There must be something wrong" when I smoothed the VR, er graphics.
>>
>> I hammered back that they might be wrong and they should look 
>> for a mistake too in their Fortran code so I be the only one risking
>> looking for a mistake that wasn't there forever and looking like an idiot.
>>
>> We managed to wrest an analysis of the fortran code which I turned around
>> into a synthesis of maple code and found :
>> "On the other hand, there may be something right!"
>>
>> So, VR may require another representation of numbers, even if someone
>> who has invested a lifetime, albeit much shorter than mine,
>> thinks there must be something wrong with that idea.
> 
> In the original Apple ][, with integer basic installed, there was
> nothing to the right of the decimal point, as all calculations resulted
> in an integer. For graphics it was fast... 7 times faster than AppleSoft
> Floating Point Basic. If you are plotting to a finite point on the
> screen, using whole numbers, then there is no need to consider floating
> point at all. Woz came up with that, as he did everything else. IMHO he
> still should be the guiding light at Apple. Ric
>