discuss@lists.openscad.org

OpenSCAD general discussion

View all threads

Re: Module Disappears In Render

J
JimT
Sun, Sep 5, 2021 4:25 PM

I'm coming late to this discussion, and I can't see the past posts on
this topic in the forum because the forum is apparently broken, so I
apologize if I'm missing something. What you say about the difference
between adding successively versus multiplying is true for limited
precision floating point as it is implemented in hardware. But, as I
understand it, OpenSCAD uses CGAL which has unlimited precision
floating point implemented in software. This OpenSCAD code multiplies
100.1 times 5000, then uses recursion to add 100.1 to itself 5000
times, and echoes the answers. The answer in both cases is exactly the
integer 500500.

start = 100.1;
iterations = 5000;
echo(start, "multiplied by ", iterations, " =", start*iterations);
function add(n) = n == 0 ? start : add(n - 1) + start;
echo (start, "added ", iterations, "times =", add(iterations-1));

This generally works, but I have run into cases in OpenSCAD where two
calculations that should have given the same answer gave two slightly
different answers due to floating point roundoff errors.

The fact that CGAL uses software floating point instead of hardware
floating point is probably one of the reasons that OpenSCAD render is
slow. There's more about CGAL's Exact Computation Paradigm here:
https://www.cgal.org/exact.html
Here are a couple of quotes from that page,

"if CGAL is properly used, the issues of roundoff and its
combinatorial consequences completely disappear"

"Getting the underlying basics always right must obviously involve
something beyond native floating-point computations, and it indeed
does. The details are pretty complex, but what essentially happens is
that we increase the numerical precision of the computations, if
necessary, by using numbers that in principle allow arbitrary
precision."

From: "Doug Moen" doug@moens.org
Subject: [OpenSCAD] Re: Module Disappears In Render

On Fri, Sep 3, 2021, at 2:00 PM, Jordan Brown wrote:

Remember that while 0.1 cannot be represented precisely, it can be
represented repeatably.

If you made a stack of 0.1 cubes by successively adding 0.1, I'd expect
all to be well because the top Z values of the cubes would have been
calculated using the same values as the bottom Z values of the next cubes
up.

That's not true because of the representation of geometry in OpenSCAD. In
that stack of cubes, the height of each cube is not represented by the
number 0.1, it is represented by a difference in Z coordinates. OpenSCAD's
64 bit floating point numbers have a fixed number of bits of precision (53
bits), so as the magnitude of a number gets larger, bits of precision are
lost at the low end. There are more floating point numbers between 0.0 and
0.1 than there are between 10.0 and 10.1, so in the latter case, the
difference of 0.1 is represented by fewer bits of precision. 10.1 - 10.0 ==
0.09999999999999964, which is different from 0.1.

It's a little trickier if you made a stack of cubes by multiplying the
cube number by 0.1, but I think all would still be well, even without grid
snap.  All of the top Z values would have been calculated using the same
numbers, as would all of the bottom Z values.  Those top Z values would
either all be the same as the bottom Z values of the next layer, or would
all be different.  In either case, you're OK.

Multiplication will give you more accurate results than iterative addition
of 0.1.
10*0.1 == 1 while iteratively adding 0.1 ten times gives you a different
number, 0.9999999999999999

I'm coming late to this discussion, and I can't see the past posts on this topic in the forum because the forum is apparently broken, so I apologize if I'm missing something. What you say about the difference between adding successively versus multiplying is true for limited precision floating point as it is implemented in hardware. But, as I understand it, OpenSCAD uses CGAL which has unlimited precision floating point implemented in software. This OpenSCAD code multiplies 100.1 times 5000, then uses recursion to add 100.1 to itself 5000 times, and echoes the answers. The answer in both cases is exactly the integer 500500. start = 100.1; iterations = 5000; echo(start, "multiplied by ", iterations, " =", start*iterations); function add(n) = n == 0 ? start : add(n - 1) + start; echo (start, "added ", iterations, "times =", add(iterations-1)); This generally works, but I have run into cases in OpenSCAD where two calculations that should have given the same answer gave two slightly different answers due to floating point roundoff errors. The fact that CGAL uses software floating point instead of hardware floating point is probably one of the reasons that OpenSCAD render is slow. There's more about CGAL's Exact Computation Paradigm here: https://www.cgal.org/exact.html Here are a couple of quotes from that page, "if CGAL is properly used, the issues of roundoff and its combinatorial consequences completely disappear" "Getting the underlying basics always right must obviously involve something beyond native floating-point computations, and it indeed does. The details are pretty complex, but what essentially happens is that we increase the numerical precision of the computations, if necessary, by using numbers that in principle allow arbitrary precision." > From: "Doug Moen" <doug@moens.org> > Subject: [OpenSCAD] Re: Module Disappears In Render > > On Fri, Sep 3, 2021, at 2:00 PM, Jordan Brown wrote: >> Remember that while 0.1 cannot be represented *precisely*, it can be >> represented *repeatably*. >> >> If you made a stack of 0.1 cubes by successively adding 0.1, I'd expect >> all to be well because the top Z values of the cubes would have been >> calculated using the same values as the bottom Z values of the next cubes >> up. > > That's not true because of the representation of geometry in OpenSCAD. In > that stack of cubes, the height of each cube is not represented by the > number 0.1, it is represented by a difference in Z coordinates. OpenSCAD's > 64 bit floating point numbers have a fixed number of bits of precision (53 > bits), so as the magnitude of a number gets larger, bits of precision are > lost at the low end. There are more floating point numbers between 0.0 and > 0.1 than there are between 10.0 and 10.1, so in the latter case, the > difference of 0.1 is represented by fewer bits of precision. 10.1 - 10.0 == > 0.09999999999999964, which is different from 0.1. > >> It's a little trickier if you made a stack of cubes by multiplying the >> cube number by 0.1, but I think all would still be well, even without grid >> snap. All of the top Z values would have been calculated using the same >> numbers, as would all of the bottom Z values. Those top Z values would >> either all be the same as the bottom Z values of the next layer, or would >> all be different. In either case, you're OK. > > Multiplication will give you more accurate results than iterative addition > of 0.1. > 10*0.1 == 1 while iteratively adding 0.1 ten times gives you a different > number, 0.9999999999999999 >
DM
Doug Moen
Sun, Sep 5, 2021 5:28 PM

OpenSCAD uses 64 bit IEEE floating point for its arithmetic.
It does not use CGAL exact rational arithmetic.
CGAL is only used for boolean operations on meshes (union, etc).

When you repeatedly add 100.1 to itself 5000 times,
the answer computed by OpenSCAD is 500499.9999999553
The reason that it prints as 500500 is that OpenSCAD is
rounding the result to 6 significant digits before printing it.

If you want proof, modify your program to echo the
result of add(5000-1) - 500500.
The answer you get is -4.47035e-8

There is a fork of OpenSCAD that uses CGAL exact rational numbers
for its arithmetic: https://github.com/GilesBathgate/RapCAD

On Sun, Sep 5, 2021, at 12:25 PM, JimT wrote:

I'm coming late to this discussion, and I can't see the past posts on
this topic in the forum because the forum is apparently broken, so I
apologize if I'm missing something. What you say about the difference
between adding successively versus multiplying is true for limited
precision floating point as it is implemented in hardware. But, as I
understand it, OpenSCAD uses CGAL which has unlimited precision
floating point implemented in software. This OpenSCAD code multiplies
100.1 times 5000, then uses recursion to add 100.1 to itself 5000
times, and echoes the answers. The answer in both cases is exactly the
integer 500500.

start = 100.1;
iterations = 5000;
echo(start, "multiplied by ", iterations, " =", start*iterations);
function add(n) = n == 0 ? start : add(n - 1) + start;
echo (start, "added ", iterations, "times =", add(iterations-1));

This generally works, but I have run into cases in OpenSCAD where two
calculations that should have given the same answer gave two slightly
different answers due to floating point roundoff errors.

The fact that CGAL uses software floating point instead of hardware
floating point is probably one of the reasons that OpenSCAD render is
slow. There's more about CGAL's Exact Computation Paradigm here:
https://www.cgal.org/exact.html
Here are a couple of quotes from that page,

"if CGAL is properly used, the issues of roundoff and its
combinatorial consequences completely disappear"

"Getting the underlying basics always right must obviously involve
something beyond native floating-point computations, and it indeed
does. The details are pretty complex, but what essentially happens is
that we increase the numerical precision of the computations, if
necessary, by using numbers that in principle allow arbitrary
precision."

From: "Doug Moen" doug@moens.org
Subject: [OpenSCAD] Re: Module Disappears In Render

On Fri, Sep 3, 2021, at 2:00 PM, Jordan Brown wrote:

Remember that while 0.1 cannot be represented precisely, it can be
represented repeatably.

If you made a stack of 0.1 cubes by successively adding 0.1, I'd expect
all to be well because the top Z values of the cubes would have been
calculated using the same values as the bottom Z values of the next cubes
up.

That's not true because of the representation of geometry in OpenSCAD. In
that stack of cubes, the height of each cube is not represented by the
number 0.1, it is represented by a difference in Z coordinates. OpenSCAD's
64 bit floating point numbers have a fixed number of bits of precision (53
bits), so as the magnitude of a number gets larger, bits of precision are
lost at the low end. There are more floating point numbers between 0.0 and
0.1 than there are between 10.0 and 10.1, so in the latter case, the
difference of 0.1 is represented by fewer bits of precision. 10.1 - 10.0 ==
0.09999999999999964, which is different from 0.1.

It's a little trickier if you made a stack of cubes by multiplying the
cube number by 0.1, but I think all would still be well, even without grid
snap.  All of the top Z values would have been calculated using the same
numbers, as would all of the bottom Z values.  Those top Z values would
either all be the same as the bottom Z values of the next layer, or would
all be different.  In either case, you're OK.

Multiplication will give you more accurate results than iterative addition
of 0.1.
10*0.1 == 1 while iteratively adding 0.1 ten times gives you a different
number, 0.9999999999999999


OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org

OpenSCAD uses 64 bit IEEE floating point for its arithmetic. It does not use CGAL exact rational arithmetic. CGAL is only used for boolean operations on meshes (union, etc). When you repeatedly add 100.1 to itself 5000 times, the answer computed by OpenSCAD is 500499.9999999553 The reason that it prints as 500500 is that OpenSCAD is rounding the result to 6 significant digits before printing it. If you want proof, modify your program to echo the result of add(5000-1) - 500500. The answer you get is -4.47035e-8 There is a fork of OpenSCAD that uses CGAL exact rational numbers for its arithmetic: https://github.com/GilesBathgate/RapCAD On Sun, Sep 5, 2021, at 12:25 PM, JimT wrote: > I'm coming late to this discussion, and I can't see the past posts on > this topic in the forum because the forum is apparently broken, so I > apologize if I'm missing something. What you say about the difference > between adding successively versus multiplying is true for limited > precision floating point as it is implemented in hardware. But, as I > understand it, OpenSCAD uses CGAL which has unlimited precision > floating point implemented in software. This OpenSCAD code multiplies > 100.1 times 5000, then uses recursion to add 100.1 to itself 5000 > times, and echoes the answers. The answer in both cases is exactly the > integer 500500. > > start = 100.1; > iterations = 5000; > echo(start, "multiplied by ", iterations, " =", start*iterations); > function add(n) = n == 0 ? start : add(n - 1) + start; > echo (start, "added ", iterations, "times =", add(iterations-1)); > > This generally works, but I have run into cases in OpenSCAD where two > calculations that should have given the same answer gave two slightly > different answers due to floating point roundoff errors. > > The fact that CGAL uses software floating point instead of hardware > floating point is probably one of the reasons that OpenSCAD render is > slow. There's more about CGAL's Exact Computation Paradigm here: > https://www.cgal.org/exact.html > Here are a couple of quotes from that page, > > "if CGAL is properly used, the issues of roundoff and its > combinatorial consequences completely disappear" > > "Getting the underlying basics always right must obviously involve > something beyond native floating-point computations, and it indeed > does. The details are pretty complex, but what essentially happens is > that we increase the numerical precision of the computations, if > necessary, by using numbers that in principle allow arbitrary > precision." > > > > From: "Doug Moen" <doug@moens.org> > > Subject: [OpenSCAD] Re: Module Disappears In Render > > > > On Fri, Sep 3, 2021, at 2:00 PM, Jordan Brown wrote: > >> Remember that while 0.1 cannot be represented *precisely*, it can be > >> represented *repeatably*. > >> > >> If you made a stack of 0.1 cubes by successively adding 0.1, I'd expect > >> all to be well because the top Z values of the cubes would have been > >> calculated using the same values as the bottom Z values of the next cubes > >> up. > > > > That's not true because of the representation of geometry in OpenSCAD. In > > that stack of cubes, the height of each cube is not represented by the > > number 0.1, it is represented by a difference in Z coordinates. OpenSCAD's > > 64 bit floating point numbers have a fixed number of bits of precision (53 > > bits), so as the magnitude of a number gets larger, bits of precision are > > lost at the low end. There are more floating point numbers between 0.0 and > > 0.1 than there are between 10.0 and 10.1, so in the latter case, the > > difference of 0.1 is represented by fewer bits of precision. 10.1 - 10.0 == > > 0.09999999999999964, which is different from 0.1. > > > >> It's a little trickier if you made a stack of cubes by multiplying the > >> cube number by 0.1, but I think all would still be well, even without grid > >> snap. All of the top Z values would have been calculated using the same > >> numbers, as would all of the bottom Z values. Those top Z values would > >> either all be the same as the bottom Z values of the next layer, or would > >> all be different. In either case, you're OK. > > > > Multiplication will give you more accurate results than iterative addition > > of 0.1. > > 10*0.1 == 1 while iteratively adding 0.1 ten times gives you a different > > number, 0.9999999999999999 > > > > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to discuss-leave@lists.openscad.org >
JB
Jordan Brown
Sun, Sep 5, 2021 6:00 PM

On 9/5/2021 9:25 AM, JimT wrote:

I can't see the past posts on this topic in the forum because the
forum is apparently broken,

But, as I understand it, OpenSCAD uses CGAL which has unlimited
precision floating point implemented in software.

It uses CGAL for some geometry calculations.  It doesn't use CGAL for
ordinary arithmetic.

This OpenSCAD code multiplies 100.1 times 5000, then uses recursion to
add 100.1 to itself 5000 times, and echoes the answers. The answer in
both cases is exactly the integer 500500.

No, it's not.  It rounds to 500500 for display.  Try this variation:

start = 100.1;
iterations = 5000;
echo(start, "multiplied by ", iterations, " =", start*iterations);
function add(n) = n == 0 ? start : add(n - 1) + start;
echo (start, "added ", iterations, "times =", add(iterations-1));

a = start * iterations;
b = add(iterations-1);
echo (a=a, b=b, a-b);

The output is:

ECHO: 100.1, "multiplied by ", 5000, " =", 500500
ECHO: 100.1, "added ", 5000, "times =", 500500
ECHO: a = 500500, b = 500500, 4.47035e-8 

Output seems to round to 6 significant digits:

echo(1.00001);
echo(1.000001);
echo(100001);
echo(1000001);

yields

ECHO: 1.00001
ECHO: 1
ECHO: 100001
ECHO: 1e+6
On 9/5/2021 9:25 AM, JimT wrote: > > I can't see the past posts on this topic in the forum because the > forum is apparently broken, > You can see them in the archive at https://lists.openscad.org/empathy/thread/LBDOUNUZ3ATDZHZAVJCV2SR4X7SY3O3Z . > But, as I understand it, OpenSCAD uses CGAL which has unlimited > precision floating point implemented in software. > It uses CGAL for some geometry calculations.  It doesn't use CGAL for ordinary arithmetic. > This OpenSCAD code multiplies 100.1 times 5000, then uses recursion to > add 100.1 to itself 5000 times, and echoes the answers. The answer in > both cases is exactly the integer 500500. > No, it's not.  It rounds to 500500 for display.  Try this variation: start = 100.1; iterations = 5000; echo(start, "multiplied by ", iterations, " =", start*iterations); function add(n) = n == 0 ? start : add(n - 1) + start; echo (start, "added ", iterations, "times =", add(iterations-1)); a = start * iterations; b = add(iterations-1); echo (a=a, b=b, a-b); The output is: ECHO: 100.1, "multiplied by ", 5000, " =", 500500 ECHO: 100.1, "added ", 5000, "times =", 500500 ECHO: a = 500500, b = 500500, 4.47035e-8 Output seems to round to 6 significant digits: echo(1.00001); echo(1.000001); echo(100001); echo(1000001); yields ECHO: 1.00001 ECHO: 1 ECHO: 100001 ECHO: 1e+6