Opened 9 years ago

Closed 5 years ago

#10629 closed defect (invalid)

performance of checking if (c/d)^(a/b) is rational

Reported by: was Owned by: burcin
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: symbolics Keywords:
Cc: Merged in:
Authors: Reviewers: Ralf Stephan, Karl-Dieter Crisman
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

sage: f(z) = (((-2)^z + 3^z)/((-2)^z - 3^z))^(1/z)
sage: f(2)
sqrt(-13/5)
sage: f(10)
(-60073/58025)^(1/10)
sage: f(100)
(-515377520732011332304111729993850674198810727377/515377520732011329768810529537391871205404316625)^(1/100)

sage: f(100)
(-515377520732011332304111729993850674198810727377/515377520732011329768810529537391871205404316625)^(1/100)
sage: f(110)
(-30432527221704537087670067466163877438919371148942073/30432527221704537085073919036896463624654122984332025)^(1/110)
sage: f(120)
(-1797010299914431210414509057505389955604379434598131450977/1797010299914431210411850601513820123858571820477570761825)^(1/120)
sage: f(140)
(-6265787482177970379256225588138505240370640792793057315382192174577/6265787482177970379256222800545355424042748100828273234337003927025)^(1/140)
sage: f(160)
(-21847450052839212624230656504451736779897953023116436713529106968318864898177/21847450052839212624230656501528733505236147186709067048096540929006999812225)^(1/160)
sage: f(180)
(-76177348045866392339289727720617094245965667291253555071028716054140756082155221621777/76177348045866392339289727720614029254883935513536838376974415435773518603910854417425)^(1/180)

... and these start getting INSANELY SLOW. Why?

(This was found by Vladimir V. Bondarenko.)

Change History (11)

comment:1 Changed 9 years ago by was

Note the traceback:

/Users/wstein/sd27/sage-4.6.1.rc1/local/lib/python2.6/site-packages/sage/rings/arith.pyc in __factor_using_pari(n, int_, debug_level, proof)
   2140         pari.set_debug_level(debug_level)
   2141         
-> 2142     F = pari(n).factor(proof=proof)
   2143     B = F[0]
   2144     e = F[1]

...

so it is factoring.

comment:2 follow-up: Changed 9 years ago by ddrake

Looking briefly over this, it's not surprising that it's factoring:

sage: (2^6 * 7^6)^(1/3)
196
sage: parent(_)
Rational Field
sage: (2^6 * 7^5)^(1/3)
28*49^(1/3)
sage: parent(_)
Symbolic Ring

So we need to factor to decide if the result is in the rationals or not.

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 in reply to: ↑ 2 Changed 5 years ago by rws

Replying to ddrake:

So we need to factor to decide if the result is in the rationals or not.

Can someone explain this further? I mean technically, factoring is overkill for this---if the exponent is a rational a/b then it suffices to check if the base is a b-th power, doesn't it?

comment:8 Changed 5 years ago by rws

  • Summary changed from weird performance issue -- why is this SOOOO slow !? to performance of checking if (c/d)^(a/b) is rational

comment:9 Changed 5 years ago by rws

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

Ah ok, it's not so important to decide whether rational or not, but to get the "rational power parts" in order to get a simplified expression of form x*y^(a/b). Since there is no way out of factoring I propose to close the ticket.

comment:10 Changed 5 years ago by kcrisman

  • Reviewers set to Ralf Stephan, Karl-Dieter Crisman
  • Status changed from needs_review to positive_review

Hmm, but one could possibly ask for it not to do that simplified form, to just always go straight to the symbolic ring... but in this case I agree that unless William really complains, we can close this.

comment:11 Changed 5 years ago by vbraun

  • Resolution set to invalid
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.