Opened 6 years ago
Last modified 5 years ago
#15625 new enhancement
Refactor Lucas sequence code
Reported by: | jpflori | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | basic arithmetic | Keywords: | lucas sequence |
Cc: | tscrim, zimmerma, rws | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As pointed by Paul Zimmerman in ticket:11802#comment:16, the Lucas sequence which has been finally sped up and generalized in #11802, needs serious refactoring:
1) it makes no sense to have a slow_lucas
and a fast_lucas
function. The philosophy in Sage is to use algorithm='recurrence'
or algorithm='matrix_exponentiation'
instead (for example).
2) I don't see why the case Q<>1 could not be implemented either by the recurrence or the matrix exponentiation.
3) instead of separate functions for ZZ and IntegerModRing?(n), it would be nicer to have a single function with an option ring=ZZ
(default) and ring=IntegerModRing(15)
.
Change History (11)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
Travis,
+1 for 3) with perhaps a minor variation: call the argument something like mod which takes an integer or None and creates the corresponding ring.
I proposed ring
in analogy to the roots
function. I'm not sure mod
is general enough,
for example one might want to use ring=RIF
if one wants to compute the first digits of the 1000th Lucas number.
Paul
comment:3 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:4 Changed 6 years ago by
A more general handling for BinaryRecurrence
, lucas
and fibonacci
is in #15714 where matrix exponentiation is used. A third method would be to expand the respective power series and read off the exponent.
comment:5 Changed 6 years ago by
- Cc rws added
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 6 years ago by
Actually, both lucas_number1
and lucas_number2
are broken:
sage: lucas_number1(100000,1,-1) File "<string>", line 1 <integer 259Ellipsis875 (Integer(20899) digits)> ^ SyntaxError: invalid syntax
Both are 2.5x slower than the general CFiniteSequence
(#15714), so could now easily replaced by that. Using lucas
fails at the moment with
sage: lucas(10,1,-1)[0] --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-60-18e5b8011bbf> in <module>() ----> 1 lucas(Integer(10),Integer(1),-Integer(1))[Integer(0)] /home/ralf/sage/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod.so in sage.rings.finite_rings.integer_mod.lucas (sage/rings/finite_rings/integer_mod.c:34263)() ValueError:
which is a bit odd because there is no reason why it shouldn't work.
comment:8 follow-up: ↓ 10 Changed 6 years ago by
Actually that's something with the interface between gap and Sage and not handling "large" numbers:
sage: ans=gap.eval("Lucas(%s,%s,%s)[1]"%(1,-1,100)) sage: ans '354224848179261915075' sage: ans=gap.eval("Lucas(%s,%s,%s)[1]"%(1,-1,100000)) sage: ans '<integer 259...875 (20899 digits)>'
comment:9 Changed 6 years ago by
Also for the second one, it's in rings.integer_mod
and there it (tries to) converts the P
and Q
input to a modular number.
comment:10 in reply to: ↑ 8 Changed 5 years ago by
comment:11 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
1) was partially done in #11802 where
slow_lucas()
was deprecated for (the more general)BinaryRecurrenceSequence
. (fast_lucas()
is [deprecated and] now calledlucas_q1()
).However something else that might be useful is a class attribute in
BinaryRecurrenceSequence
calledlucas()
orlucas_sequence()
, which takes the usual Lucas sequence input and converts it into the appropriateBinaryRecurrenceSequence
input.+1 for 3) with perhaps a minor variation: call the argument something like
mod
which takes an integer orNone
and creates the corresponding ring.Overall I think what's best is one function which has the
algorithm
andmod
arguments and possibly redirects to these subroutines depending upon the input.Best,
Travis