Opened 8 months ago

Closed 7 months ago

#31294 closed enhancement (fixed)

Implement fetch_int method for non-givaro finite fields

Reported by: slelievre Owned by:
Priority: major Milestone: sage-9.3
Component: finite rings Keywords:
Cc: Merged in:
Authors: Dave Morris Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 336fcd3 (Commits, GitHub, GitLab) Commit: 336fcd38c1a861410f091dfd59681468d9ae44ef
Dependencies: Stopgaps:

Status badges

Description

Finite fields in the givaro implementation have a fetch_int method, which is not present in the pari implementation.

Define a prime and a finite field:

sage: p = 4091
sage: F = GF(p^2, 'a')

Before this ticket:

sage: F.fetch_int(3*p + 2)
Traceback (most recent call last)
...
AttributeError: 'FiniteField_pari_ffelt_with_category' object has no attribute 'fetch_int'

After this ticket:

sage: F.fetch_int(3*4091 + 2)
3*a + 2

Requested at

Change History (12)

comment:1 Changed 8 months ago by gh-DaveWitteMorris

  • Branch set to public/31294

comment:2 Changed 8 months ago by gh-DaveWitteMorris

  • Authors set to Dave Morris
  • Commit set to a22dee6a063fac7266311454a26ff45fcfebd2ef
  • Status changed from new to needs_review

The PR adds the requested method (and doctests) to the base class. I don't think we should assume that we know how the element constructor acts on lists, so I did not use the elegant solution that is in the ask Sage question, although I did use the same idea.


New commits:

a22dee6trac 31294 fetch_int method

comment:3 Changed 8 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

I think this is good overall. Here are some changes that should increase the speed:

         n = Integer(n)
         if (n < 0) or (n >= self.order()):
             raise TypeError("n must be between 0 and self.order()")
         if n == 0:
-            return self(0)
+            return self.zero()
-        digs = n.digits(base=self.characteristic())
-        return sum(self(digs[i]) * self.gen()**i for i in range(len(digs)))
+        cdef list digs = n.digits(base=self.characteristic())
+        g = self.gen()
+        return self.sum(self(val) * g**i for val in digs if val)

Other than that LGTM.

comment:4 Changed 8 months ago by git

  • Commit changed from a22dee6a063fac7266311454a26ff45fcfebd2ef to 463b669c808f7bf7d92adb45c1e3611099da3b4d

Branch pushed to git repo; I updated commit sha1. New commits:

463b669reviewer suggestions

comment:5 Changed 8 months ago by gh-DaveWitteMorris

Thanks for the suggestions! I had to change the final line, because i is an undefined variable in (self(val) * g**i for val in digs if val).

comment:6 Changed 8 months ago by git

  • Commit changed from 463b669c808f7bf7d92adb45c1e3611099da3b4d to 15196af83a9fb82bfe79f9c8b5fff68c935d47ad

Branch pushed to git repo; I updated commit sha1. New commits:

15196afanother reviewer comment

comment:7 Changed 8 months ago by gh-DaveWitteMorris

I forgot to save the final edit to the file before the last commit, so the commit was missing one of the reviewer suggestions. My bad.

comment:8 Changed 8 months ago by tscrim

Ah, right, the i. This is marginally faster (at least, the last time I tested it):

return self.sum(self(val) * g**i for i, val in enumerate(digs) if val)

comment:9 Changed 8 months ago by git

  • Commit changed from 15196af83a9fb82bfe79f9c8b5fff68c935d47ad to 336fcd38c1a861410f091dfd59681468d9ae44ef

Branch pushed to git repo; I updated commit sha1. New commits:

336fcd3use enumerate

comment:10 Changed 8 months ago by gh-DaveWitteMorris

Thanks, that's better than what I had. It bothered me that I was accessing digs[i] twice, but I didn't know how to avoid that.

comment:11 Changed 8 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you.

comment:12 Changed 7 months ago by vbraun

  • Branch changed from public/31294 to 336fcd38c1a861410f091dfd59681468d9ae44ef
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.