#31294 closed enhancement (fixed)

Implement fetch_int method for non-givaro finite fields

Reported by: Samuel Lelièvre 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 20 months ago by Dave Morris

Branch: public/31294

comment:2 Changed 20 months ago by Dave Morris

Authors: Dave Morris
Commit: a22dee6a063fac7266311454a26ff45fcfebd2ef
Status: newneeds_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 20 months ago by Travis Scrimshaw

Reviewers: 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 20 months ago by git

Commit: a22dee6a063fac7266311454a26ff45fcfebd2ef463b669c808f7bf7d92adb45c1e3611099da3b4d

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

463b669reviewer suggestions

comment:5 Changed 20 months ago by Dave Morris

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 20 months ago by git

Commit: 463b669c808f7bf7d92adb45c1e3611099da3b4d15196af83a9fb82bfe79f9c8b5fff68c935d47ad

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

15196afanother reviewer comment

comment:7 Changed 20 months ago by Dave Morris

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 20 months ago by Travis Scrimshaw

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 20 months ago by git

Commit: 15196af83a9fb82bfe79f9c8b5fff68c935d47ad336fcd38c1a861410f091dfd59681468d9ae44ef

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

336fcd3use enumerate

comment:10 Changed 20 months ago by Dave Morris

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 20 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Thank you.

comment:12 Changed 19 months ago by Volker Braun

Branch: public/31294336fcd38c1a861410f091dfd59681468d9ae44ef
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.