Correct way of operating on exact numbers in CGAL
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
Consider the following minimal example:
#include <stdlib.h>
#include "CGALExact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::FT NumberType;
int main()
{
int numberOfIterations = 4000;
NumberType sum = 0;
for (int i = 0; i < numberOfIterations; i++)
{
sum += 1;
}
std::cout << "Sum = " << sum << std::endl;
getchar();
return 0;
}
All seems to work fine if the numberOfIterations
parameter assumes small values.
However, when it is set to a value greater than some thousands, the program outputs the correct value for sum
, but gives a Stack overflow error (parameters: 0x0000000000000001, 0x000000C4D2EF3FF8) when deleting the memory (I suppose).
I read the CGAL documentation on Number Types, but it is not clear to me the reason why this happens. What should I do to perform operations on exact numbers in a correct way?
Here is a more complicated example (as requested in the comments below), strictly related to my original problem:
#include <stdlib.h>
#include <CGAL/number_utils.h>
#include "CGAL/Exact_predicates_exact_constructions_kernel_with_sqrt.h"
#include "CGAL/Polyhedron_3.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;
typedef Kernel::FT NumberType;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Direction_3 Direction_3;
Direction_3 sampleFunction(std::vector<Vector_3> vectors)
{
NumberType denominator = 0;
NumberType numeratorX = 0;
NumberType numeratorY = 0;
NumberType numeratorZ = 0;
for (int vf = 0; vf < vectors.size(); vf++)
{
Vector_3 vectorF = vectors.at(vf);
numeratorX += vectorF.x();
numeratorY += vectorF.y();
numeratorZ += vectorF.z();
for (int vg = 0; vg < vectors.size(); vg++)
{
Vector_3 vectorG = vectors.at(vg);
denominator += CGAL::scalar_product(vectorF, vectorG);
}
}
NumberType lambda = CGAL::sqrt(denominator);
NumberType x = numeratorX / lambda;
NumberType y = numeratorY / lambda;
NumberType z = numeratorZ / lambda;
Vector_3 result(x, y, z);
return result.direction();
}
int main()
{
int numberOfVectors = 100;
std::vector<Vector_3> vectors;
srand(0);
for (int i = 0; i < numberOfVectors; i++)
{
Vector_3 newVector(rand() % 100 - 50, rand() % 100 - 50, rand() % 100 - 50);
newVector /= CGAL::sqrt(newVector.squared_length());
vectors.push_back(newVector);
}
Direction_3 direction = sampleFunction(vectors);
std::cout << direction.dx() << " " << direction.dy() << " " << direction.dz() << " " << std::endl;
return 0;
}
c++ stack-overflow cgal paradigms
|
show 5 more comments
Consider the following minimal example:
#include <stdlib.h>
#include "CGALExact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::FT NumberType;
int main()
{
int numberOfIterations = 4000;
NumberType sum = 0;
for (int i = 0; i < numberOfIterations; i++)
{
sum += 1;
}
std::cout << "Sum = " << sum << std::endl;
getchar();
return 0;
}
All seems to work fine if the numberOfIterations
parameter assumes small values.
However, when it is set to a value greater than some thousands, the program outputs the correct value for sum
, but gives a Stack overflow error (parameters: 0x0000000000000001, 0x000000C4D2EF3FF8) when deleting the memory (I suppose).
I read the CGAL documentation on Number Types, but it is not clear to me the reason why this happens. What should I do to perform operations on exact numbers in a correct way?
Here is a more complicated example (as requested in the comments below), strictly related to my original problem:
#include <stdlib.h>
#include <CGAL/number_utils.h>
#include "CGAL/Exact_predicates_exact_constructions_kernel_with_sqrt.h"
#include "CGAL/Polyhedron_3.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;
typedef Kernel::FT NumberType;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Direction_3 Direction_3;
Direction_3 sampleFunction(std::vector<Vector_3> vectors)
{
NumberType denominator = 0;
NumberType numeratorX = 0;
NumberType numeratorY = 0;
NumberType numeratorZ = 0;
for (int vf = 0; vf < vectors.size(); vf++)
{
Vector_3 vectorF = vectors.at(vf);
numeratorX += vectorF.x();
numeratorY += vectorF.y();
numeratorZ += vectorF.z();
for (int vg = 0; vg < vectors.size(); vg++)
{
Vector_3 vectorG = vectors.at(vg);
denominator += CGAL::scalar_product(vectorF, vectorG);
}
}
NumberType lambda = CGAL::sqrt(denominator);
NumberType x = numeratorX / lambda;
NumberType y = numeratorY / lambda;
NumberType z = numeratorZ / lambda;
Vector_3 result(x, y, z);
return result.direction();
}
int main()
{
int numberOfVectors = 100;
std::vector<Vector_3> vectors;
srand(0);
for (int i = 0; i < numberOfVectors; i++)
{
Vector_3 newVector(rand() % 100 - 50, rand() % 100 - 50, rand() % 100 - 50);
newVector /= CGAL::sqrt(newVector.squared_length());
vectors.push_back(newVector);
}
Direction_3 direction = sampleFunction(vectors);
std::cout << direction.dx() << " " << direction.dy() << " " << direction.dz() << " " << std::endl;
return 0;
}
c++ stack-overflow cgal paradigms
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
Thanks for the explanation and the links. Let's see if I understood: (1) the value ofsum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?
– simonet
Nov 23 '18 at 13:41
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29
|
show 5 more comments
Consider the following minimal example:
#include <stdlib.h>
#include "CGALExact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::FT NumberType;
int main()
{
int numberOfIterations = 4000;
NumberType sum = 0;
for (int i = 0; i < numberOfIterations; i++)
{
sum += 1;
}
std::cout << "Sum = " << sum << std::endl;
getchar();
return 0;
}
All seems to work fine if the numberOfIterations
parameter assumes small values.
However, when it is set to a value greater than some thousands, the program outputs the correct value for sum
, but gives a Stack overflow error (parameters: 0x0000000000000001, 0x000000C4D2EF3FF8) when deleting the memory (I suppose).
I read the CGAL documentation on Number Types, but it is not clear to me the reason why this happens. What should I do to perform operations on exact numbers in a correct way?
Here is a more complicated example (as requested in the comments below), strictly related to my original problem:
#include <stdlib.h>
#include <CGAL/number_utils.h>
#include "CGAL/Exact_predicates_exact_constructions_kernel_with_sqrt.h"
#include "CGAL/Polyhedron_3.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;
typedef Kernel::FT NumberType;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Direction_3 Direction_3;
Direction_3 sampleFunction(std::vector<Vector_3> vectors)
{
NumberType denominator = 0;
NumberType numeratorX = 0;
NumberType numeratorY = 0;
NumberType numeratorZ = 0;
for (int vf = 0; vf < vectors.size(); vf++)
{
Vector_3 vectorF = vectors.at(vf);
numeratorX += vectorF.x();
numeratorY += vectorF.y();
numeratorZ += vectorF.z();
for (int vg = 0; vg < vectors.size(); vg++)
{
Vector_3 vectorG = vectors.at(vg);
denominator += CGAL::scalar_product(vectorF, vectorG);
}
}
NumberType lambda = CGAL::sqrt(denominator);
NumberType x = numeratorX / lambda;
NumberType y = numeratorY / lambda;
NumberType z = numeratorZ / lambda;
Vector_3 result(x, y, z);
return result.direction();
}
int main()
{
int numberOfVectors = 100;
std::vector<Vector_3> vectors;
srand(0);
for (int i = 0; i < numberOfVectors; i++)
{
Vector_3 newVector(rand() % 100 - 50, rand() % 100 - 50, rand() % 100 - 50);
newVector /= CGAL::sqrt(newVector.squared_length());
vectors.push_back(newVector);
}
Direction_3 direction = sampleFunction(vectors);
std::cout << direction.dx() << " " << direction.dy() << " " << direction.dz() << " " << std::endl;
return 0;
}
c++ stack-overflow cgal paradigms
Consider the following minimal example:
#include <stdlib.h>
#include "CGALExact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::FT NumberType;
int main()
{
int numberOfIterations = 4000;
NumberType sum = 0;
for (int i = 0; i < numberOfIterations; i++)
{
sum += 1;
}
std::cout << "Sum = " << sum << std::endl;
getchar();
return 0;
}
All seems to work fine if the numberOfIterations
parameter assumes small values.
However, when it is set to a value greater than some thousands, the program outputs the correct value for sum
, but gives a Stack overflow error (parameters: 0x0000000000000001, 0x000000C4D2EF3FF8) when deleting the memory (I suppose).
I read the CGAL documentation on Number Types, but it is not clear to me the reason why this happens. What should I do to perform operations on exact numbers in a correct way?
Here is a more complicated example (as requested in the comments below), strictly related to my original problem:
#include <stdlib.h>
#include <CGAL/number_utils.h>
#include "CGAL/Exact_predicates_exact_constructions_kernel_with_sqrt.h"
#include "CGAL/Polyhedron_3.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;
typedef Kernel::FT NumberType;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Direction_3 Direction_3;
Direction_3 sampleFunction(std::vector<Vector_3> vectors)
{
NumberType denominator = 0;
NumberType numeratorX = 0;
NumberType numeratorY = 0;
NumberType numeratorZ = 0;
for (int vf = 0; vf < vectors.size(); vf++)
{
Vector_3 vectorF = vectors.at(vf);
numeratorX += vectorF.x();
numeratorY += vectorF.y();
numeratorZ += vectorF.z();
for (int vg = 0; vg < vectors.size(); vg++)
{
Vector_3 vectorG = vectors.at(vg);
denominator += CGAL::scalar_product(vectorF, vectorG);
}
}
NumberType lambda = CGAL::sqrt(denominator);
NumberType x = numeratorX / lambda;
NumberType y = numeratorY / lambda;
NumberType z = numeratorZ / lambda;
Vector_3 result(x, y, z);
return result.direction();
}
int main()
{
int numberOfVectors = 100;
std::vector<Vector_3> vectors;
srand(0);
for (int i = 0; i < numberOfVectors; i++)
{
Vector_3 newVector(rand() % 100 - 50, rand() % 100 - 50, rand() % 100 - 50);
newVector /= CGAL::sqrt(newVector.squared_length());
vectors.push_back(newVector);
}
Direction_3 direction = sampleFunction(vectors);
std::cout << direction.dx() << " " << direction.dy() << " " << direction.dz() << " " << std::endl;
return 0;
}
c++ stack-overflow cgal paradigms
c++ stack-overflow cgal paradigms
edited Nov 26 '18 at 11:51
Vadim Kotov
4,83863549
4,83863549
asked Nov 22 '18 at 9:45
simonetsimonet
12310
12310
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
Thanks for the explanation and the links. Let's see if I understood: (1) the value ofsum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?
– simonet
Nov 23 '18 at 13:41
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29
|
show 5 more comments
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
Thanks for the explanation and the links. Let's see if I understood: (1) the value ofsum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?
– simonet
Nov 23 '18 at 13:41
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
Thanks for the explanation and the links. Let's see if I understood: (1) the value of
sum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?– simonet
Nov 23 '18 at 13:41
Thanks for the explanation and the links. Let's see if I understood: (1) the value of
sum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?– simonet
Nov 23 '18 at 13:41
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29
|
show 5 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53428007%2fcorrect-way-of-operating-on-exact-numbers-in-cgal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53428007%2fcorrect-way-of-operating-on-exact-numbers-in-cgal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
With your configuration, FT is probably Lazy_exact_nt, which builds a tree that remembers all the operations performed on it. Sometimes evaluation has to go through this tree using a recursive function, which requires a large stack. So does destruction (though I thought I saw either an issue or a pull request about that).
– Marc Glisse
Nov 22 '18 at 11:47
github.com/CGAL/cgal/issues/1118 . Something like this branch could also help: github.com/mglisse/cgal/tree/Number_types-lazy-glisse .
– Marc Glisse
Nov 22 '18 at 11:48
Thanks for the explanation and the links. Let's see if I understood: (1) the value of
sum
that is printed is only an approximated value (otherwise the computation would lead to a stack overflow already there). (2) there is no way (at the moment) for doing a large number of operations on exact numbers (except by downloading/installing/linking to the branch you have provided). Am I right?– simonet
Nov 23 '18 at 13:41
(1) yes but as long as it fits in double the approximation is perfect. (2) you can call sum.exact() once in a while to collapse the tree, or better use a non-lazy type. You can also increase the size of the stack (there are many questions on this site explaining how on various systems).
– Marc Glisse
Nov 23 '18 at 15:03
Your example code is too simple to be useful. There is a category of computations, iterated/cascaded computations, for which this CGAL number type is not appropriate in general, even though it can be tweaked to make it work for your particular simple case, as Marc Glisse mentions. Do you have a more "real world" example of thing you would like to do, for which this is failing as well ?
– Sylvain Pion
Nov 23 '18 at 15:29