Revision history [back]

This should not be a difficult computation. It takes me half a minute with the "naive" QQbar implementation in Pygrim (https://github.com/fredrik-johansson/fungrim/)

fredrik@agm:~/Desktop$ time python3 verifysqrt.py 
True

real     0m29,350s
user     0m29,331s
sys      0m0,017s

Content of the script verifysqrt.py:

from pygrim import alg

def sqrt(x):
    return alg(x).sqrt()

N = ...        # copy of expression, with x/y and ^ replaced by alg(x)/y and x^y for pure python compatibility
I = alg.i()
M = ...        # as with N = ...
print(-(1 - abs(M)**2)**2 == N)

As Samuel said, Calcium (http://fredrikj.net/calcium/) is meant to let you do this kind of computation easily.

First of all, there is a "naive" QQbar implementation (qqbar_t) which is essentially a cleaned-up and slightly optimized C reimplementation of the Pygrim code. This module is already complete and if someone wanted to write a Sage interface, it should be possible today :-)

Second, the actual goal of Calcium is to have a more efficient type (ca_t) based on fast field arithmetic and relative extensions (and supporting not only algebraics but also transcendental numbers). This will potentially be more efficient for this kind of problem -- in fact, it's a very nice benchmark problem, and I'm happy that you shared it. I will save it for testing purposes :-)

The reason there is no public release of Calcium yet is that the ca_t type is far from finished (in fact, I need to rewrite a lot of the existing code...). This could take a few months.

This should not be a difficult computation. It takes me half a minute with the "naive" QQbar implementation in Pygrim (https://github.com/fredrik-johansson/fungrim/)

fredrik@agm:~/Desktop$ time python3 verifysqrt.py 
True

real     0m29,350s
user     0m29,331s
sys      0m0,017s

Content of the script verifysqrt.py:

from pygrim import alg

def sqrt(x):
    return alg(x).sqrt()

N = ...        # copy of expression, with x/y and ^ replaced by alg(x)/y and x^y for pure python compatibility
I = alg.i()
M = ...        # as with N = ...
print(-(1 - abs(M)**2)**2 == N)

As Samuel said, Calcium (http://fredrikj.net/calcium/) is meant to let you do this kind of computation easily.

First of all, there is a "naive" QQbar implementation (qqbar_t) which is essentially a cleaned-up and slightly optimized C reimplementation of the Pygrim code. This module is already complete and if someone wanted to write a Sage interface, it should be possible today :-)

Second, the actual goal of Calcium is to have a more efficient type (ca_t) based on fast field arithmetic and relative extensions (and supporting not only algebraics but also transcendental numbers). This will potentially be more efficient for this kind of problem -- in fact, it's a very nice benchmark problem, and I'm happy that you shared it. I will save it for testing purposes :-)

The reason there is no public release of Calcium yet (with easy-to-install packages and installation documentation) is that the ca_t type is far from finished (in fact, I need to rewrite a lot of the existing code...). This could take a few months.

This should not be a difficult computation. It takes me half a minute with the "naive" QQbar implementation in Pygrim (https://github.com/fredrik-johansson/fungrim/)

fredrik@agm:~/Desktop$ time python3 verifysqrt.py 
True

real     0m29,350s
user     0m29,331s
sys      0m0,017s

Content of the script verifysqrt.py:

from pygrim import alg

def sqrt(x):
    return alg(x).sqrt()

N = ...        # copy of expression, with x/y and ^ replaced by alg(x)/y and x^y for pure python compatibility
I = alg.i()
M = ...        # as with N = ...
print(-(1 - abs(M)**2)**2 == N)

As Samuel said, Calcium (http://fredrikj.net/calcium/) is meant to let you do this kind of computation easily.

First of all, there is a "naive" QQbar implementation (qqbar_t) which is essentially a cleaned-up and slightly optimized C reimplementation of the Pygrim code. This module is already complete and if someone wanted to write a Sage interface, it should be possible today :-)

Second, the actual goal of Calcium is to have a more efficient type (ca_t) based on fast field arithmetic and relative extensions (and supporting not only algebraics but also transcendental numbers). This will potentially be more efficient for this kind of problem -- in fact, it's a very nice benchmark problem, and I'm happy that you shared it. I will save it for testing purposes :-)

The reason there is no public release of Calcium yet (with easy-to-install packages and installation documentation) is that the ca_t type is far from finished (in fact, I need to rewrite a lot of the existing code...). This could take a few months.

This should not be a difficult computation. It takes me half a minute with the "naive" QQbar implementation in Pygrim (https://github.com/fredrik-johansson/fungrim/)

fredrik@agm:~/Desktop$ time python3 verifysqrt.py 
True

real     0m29,350s
user     0m29,331s
sys      0m0,017s

Content of the script verifysqrt.py:

from pygrim import alg

def sqrt(x):
    return alg(x).sqrt()

N = ...        # copy of expression, with x/y and ^ x^y replaced by alg(x)/y and x^y x**y for pure python compatibility
I = alg.i()
M = ...        # as with N = ...
print(-(1 - abs(M)**2)**2 == N)

As Samuel said, Calcium (http://fredrikj.net/calcium/) is meant to let you do this kind of computation easily.

First of all, there is a "naive" QQbar implementation (qqbar_t) which is essentially a cleaned-up and slightly optimized C reimplementation of the Pygrim code. This module is already complete and if someone wanted to write a Sage interface, it should be possible today :-)

Second, the actual goal of Calcium is to have a more efficient type (ca_t) based on fast field arithmetic and relative extensions (and supporting not only algebraics but also transcendental numbers). This will potentially be more efficient for this kind of problem -- in fact, it's a very nice benchmark problem, and I'm happy that you shared it. I will save it for testing purposes :-)

The reason there is no public release of Calcium yet (with easy-to-install packages and installation documentation) is that the ca_t type is far from finished (in fact, I need to rewrite a lot of the existing code...). This could take a few months.

This Updated answer on 2020-08-23:

This is now possible with Calcium (http://fredrikj.net/calcium/). I have added an example program called huge_expr.c that performs this computation in two different ways (the C file was auto-generated from the Sage expression, since I do not yet have an expression parser in Calcium itself).

The example program is documented here: http://fredrikj.net/calcium/examples.html#huge-expr-c

By default, the program runs the computation using qqbar_t arithmetic. This takes half a minute:

> build/examples/huge_expr
Evaluating N...
cpu/wall(s): 18.279 18.279
Evaluating M...
cpu/wall(s): 6.049 6.051
Evaluating E = -(1-|M|^2)^2...
cpu/wall(s): 0.595 0.595
N ~ -0.16190853053311203695842869991458578203473645660641
E ~ -0.16190853053311203695842869991458578203473645660641
Testing E = N...
cpu/wall(s): 0 0

Equal = T_TRUE

Total: cpu/wall(s): 24.927 24.93
virt/peak/res/peak(MB): 56.61 68.64 28.73 40.70

To run the computation using ca_t arithmetic instead, pass the -ca flag. This currently takes longer (three minutes), but at least it works:

> build/examples/huge_expr -ca
Evaluating N...
cpu/wall(s): 2.116 2.116
Evaluating M...
cpu/wall(s): 0.068 0.068
Evaluating E = -(1-|M|^2)^2...
cpu/wall(s): 0.043 0.043
N ~ -0.16190853053311203695842869991458578203473645660641
E ~ -0.16190853053311203695842869991458578203473645660641
Testing E = N...
cpu/wall(s): 176.235 176.242

Equal = T_TRUE

Total: cpu/wall(s): 178.465 178.472
virt/peak/res/peak(MB): 55.92 67.88 29.80 41.76

It should not be possible to improve the ca_t arithmetic so that is competitive with the qqbar_t version (hopefully even faster, if it can be done using suitable number field operations). This example program will remain in Calcium as a difficult computation. It nice test/benchmark case :-)

Old answer: this takes me half a minute with the "naive" QQbar implementation in Pygrim (https://github.com/fredrik-johansson/fungrim/)

fredrik@agm:~/Desktop$ time python3 verifysqrt.py 
True

real     0m29,350s
user     0m29,331s
sys      0m0,017s

Content of the script verifysqrt.py:

from pygrim import alg

def sqrt(x):
    return alg(x).sqrt()

N = ...        # copy of expression, with x/y and x^y replaced by alg(x)/y and x**y for pure python compatibility
I = alg.i()
M = ...        # as with N = ...
print(-(1 - abs(M)**2)**2 == N)

As Samuel said, Calcium (http://fredrikj.net/calcium/) is meant to let you do this kind of computation easily.

First of all, there is a "naive" QQbar implementation (qqbar_t) which is essentially a cleaned-up and slightly optimized C reimplementation of the Pygrim code. This module is already complete and if someone wanted to write a Sage interface, it should be possible today :-)

Second, the actual goal of Calcium is to have a more efficient type (ca_t) based on fast field arithmetic and relative extensions (and supporting not only algebraics but also transcendental numbers). This will potentially be more efficient for this kind of problem -- in fact, it's a very nice benchmark problem, and I'm happy that you shared it. I will save it for testing purposes :-)

The reason there is no public release of Calcium yet (with easy-to-install packages and installation documentation) is that the ca_t type is far from finished (in fact, I need to rewrite a lot of the existing code...). This could take a few months.