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;
}







0















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;
}









share|improve this question

























  • 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


















0















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;
}









share|improve this question

























  • 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














0












0








0








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;
}









share|improve this question
















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








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 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



















  • 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

















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












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
});


}
});














draft saved

draft discarded


















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
















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Biblatex bibliography style without URLs when DOI exists (in Overleaf with Zotero bibliography)

ComboBox Display Member on multiple fields

Is it possible to collect Nectar points via Trainline?