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 tscrim

1) was partially done in #11802 where slow_lucas() was deprecated for (the more general) BinaryRecurrenceSequence. (fast_lucas() is [deprecated and] now called lucas_q1()).

However something else that might be useful is a class attribute in BinaryRecurrenceSequence called lucas() or lucas_sequence(), which takes the usual Lucas sequence input and converts it into the appropriate BinaryRecurrenceSequence input.

+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.

Overall I think what's best is one function which has the algorithm and mod arguments and possibly redirects to these subroutines depending upon the input.

Best,
Travis

comment:2 Changed 6 years ago by zimmerma

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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 5 years ago by rws

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 5 years ago by rws

  • Cc rws added

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by rws

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: Changed 5 years ago by tscrim

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 5 years ago by tscrim

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 rws

Replying to tscrim:

Actually that's something with the interface between gap and Sage and not handling "large" numbers:

Which is now #16719

comment:11 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.