Opened 10 years ago

Last modified 5 years ago

#6941 needs_work defect

GCD, XGCD for polynomial rings with templating

Reported by: spancratz Owned by: tbd
Priority: minor Milestone: sage-6.4
Component: algebra Keywords:
Cc: rws, jpflori Merged in:
Authors: Sebastian Pancratz Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

GCD and XGCD methods should return *monic* greatest common divisors. However, at the moment these two methods in the template file sage/rings/polynomial/polynomial_template.pxi prevent this by enforcing that gcd(a,0) == a and gcd(0,b) == b.

I suggest that the code for these two methods in the template file should only refer to the corresponding celement_foo methods of the actual implementation. This way, all the logic is in the celement_foo methods, rather than being split between the two levels.

The patch for this should touch the template file as well as the two linkage files for GF2X and zmod polynomials.

Attachments (1)

trac_6941_monicgcd.patch​ (9.2 KB) - added by spancratz 10 years ago.

Download all attachments as: .zip

Change History (13)

Changed 10 years ago by spancratz

comment:1 follow-up: Changed 10 years ago by malb

  • Summary changed from GCD, XGCD for polynomial rings with templating to [with patch, needs review] GCD, XGCD for polynomial rings with templating

The patch looks good, applies cleanly and doctests pass. However, do we really need to mimic the old behaviour?

comment:2 in reply to: ↑ 1 Changed 10 years ago by spancratz

Replying to malb:

The patch looks good, applies cleanly and doctests pass. However, do we really need to mimic the old behaviour?

I assume you are referring to the hyperelliptic curves part? Yes, I think so. Otherwise, some doctests fail. I haven't tried to fully understand the mathematics of that part, but it seems to depend on the assumption gcd(a,0) == a.

Sebastian

comment:3 Changed 9 years ago by malb

Maybe we can ask the person who wrote that code?

comment:4 Changed 9 years ago by mhansen

  • Status changed from needs_review to needs_info

comment:5 Changed 9 years ago by AlexGhitza

  • Milestone set to sage-4.3
  • Summary changed from [with patch, needs review] GCD, XGCD for polynomial rings with templating to GCD, XGCD for polynomial rings with templating

comment:6 Changed 9 years ago by robertwb

  • Report Upstream set to N/A
  • Status changed from needs_info to needs_work

If we need to mimic the old xgcd behavior, it would be much better to abstract that out into its own function with a docstring and some tests.

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 5 years ago by rws

  • Cc rws added

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:10 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.