Opened 5 years ago

Closed 5 years ago

#22630 closed defect (fixed)

Fix mutation of list in lcm

Reported by: tscrim Owned by:
Priority: major Milestone: sage-8.0
Component: basic arithmetic Keywords: days85
Cc: jdemeyer Merged in:
Authors: Travis Scrimshaw Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 40e2b08 (Commits, GitHub, GitLab) Commit: 40e2b0835e257b55aa013d5583ef0f1121111ba1
Dependencies: Stopgaps:

Status badges

Description

The current LCM_list will mutate the list when it contains int's (and possibly Sage integers and long):

sage: L = [int(1), int(2)]
sage: lcm(L)
2
sage: type(L[0])
<type 'sage.rings.integer.Integer'>

Change History (15)

comment:1 Changed 5 years ago by tscrim

  • Branch set to public/arith/fix_lcm-22630
  • Cc jdemeyer added
  • Commit set to ad2189cbf2c051d3628ffeb988c231f6a7e3e45d
  • Status changed from new to needs_review

New timings:

sage: L = [1 for _ in range(1000)]
sage: from sage.rings.integer import LCM_list
sage: %timeit [LCM_list(L) for _ in range(100)]
100 loops, best of 3: 2.25 ms per loop
sage: %timeit [LCM_list([1,2,3,4,5]) for _ in range(100)]
10000 loops, best of 3: 62.4 µs per loop
sage: %timeit [LCM_list([1,2]) for _ in range(100)]
10000 loops, best of 3: 36.1 µs per loop
sage: %timeit [LCM_list([2]) for _ in range(100)]
10000 loops, best of 3: 26.4 µs per loop
sage: %timeit [LCM_list([1]) for _ in range(100)]
10000 loops, best of 3: 26.5 µs per loop
sage: %timeit [LCM_list([]) for _ in range(100)]
100000 loops, best of 3: 13.3 µs per loop
sage: L.append(polygen(ZZ, 'x'))
sage: %timeit [lcm(L) for _ in range(100)]
100 loops, best of 3: 2.87 ms per loop
sage: L = [1 for _ in range(1000)]
sage: L.insert(0, polygen(ZZ, 'x'))
sage: %timeit [lcm(L) for _ in range(100)]
1 loop, best of 3: 363 ms per loop

Old timings:

sage: %timeit [LCM_list(L) for _ in range(100)]
100 loops, best of 3: 2.43 ms per loop
sage: %timeit [LCM_list([1,2,3,4,5]) for _ in range(100)]
10000 loops, best of 3: 56.5 µs per loop
sage: %timeit [LCM_list([1,2]) for _ in range(100)]
10000 loops, best of 3: 30.1 µs per loop
sage: %timeit [LCM_list([2]) for _ in range(100)]
10000 loops, best of 3: 24.5 µs per loop
sage: %timeit [LCM_list([1]) for _ in range(100)]
10000 loops, best of 3: 24.6 µs per loop
sage: %timeit [LCM_list([]) for _ in range(100)]
100000 loops, best of 3: 7.25 µs per loop
sage: L.append(polygen(ZZ, 'x'))
sage: %timeit [lcm(L) for _ in range(100)]
100 loops, best of 3: 2.87 ms per loop
sage: %timeit [lcm(L) for _ in range(100)]
1 loop, best of 3: 395 ms per loop
sage: L = [1 for _ in range(1000)]
sage: L.insert(0, polygen(ZZ, 'x'))
sage: %timeit [lcm(L) for _ in range(100)]
1 loop, best of 3: 394 ms per loop

So this does have a constant time slowdown when looping over (Sage) integer lists of about 6/100 µs or 60 ns per call. I think this is acceptable in comparison to how much we gain for a mixed list, fixing the bug at hand, and consolidating things into a single function.


New commits:

ad2189cFixing bug in LCM_list and combining with __LCM_sequence.

comment:2 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

First of all, do not put Python code inside sig_on().

comment:3 Changed 5 years ago by jdemeyer

If LCM_list and LCM_sequence handle non-integers now, they should be moved outside of src/sage/rings/integer.pyx.

comment:4 Changed 5 years ago by jdemeyer

No need to deprecate __LCM_sequence since it was private already.

comment:5 Changed 5 years ago by git

  • Commit changed from ad2189cbf2c051d3628ffeb988c231f6a7e3e45d to 9066ab4d06169ee7dfd0806d6208f9a8728718e3

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

7b20915Use sig_check instead of sig_on/sig_off.
9066ab4Moving LCM_list to new file arith/functions.pyx.

comment:6 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

I'm going to be paranoid and leave in the deprecation of __LCM_sequence since someone might be using it for speed reasons (although I doubt it).

comment:7 Changed 5 years ago by git

  • Commit changed from 9066ab4d06169ee7dfd0806d6208f9a8728718e3 to 7603fe056c0230608dfb2a7e6b7adffbfea88b66

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

7603fe0Implementing Jeroen's (in person) comments.

comment:8 Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer

comment:9 Changed 5 years ago by git

  • Commit changed from 7603fe056c0230608dfb2a7e6b7adffbfea88b66 to b7e2e5d604e7d15acf3d3bf666da17308efca79e

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

b7e2e5dMinor fixes to lcm()

comment:10 Changed 5 years ago by jdemeyer

Minor changes, needs review.

comment:11 Changed 5 years ago by tscrim

If all tests pass, then positive review.

comment:12 Changed 5 years ago by git

  • Commit changed from b7e2e5d604e7d15acf3d3bf666da17308efca79e to 40e2b0835e257b55aa013d5583ef0f1121111ba1

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

ffa9c6eCorrect import of lcm
40e2b08Make doctest compatible with Python 3

comment:13 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to positive_review

I make 2 very small corrections which were needed for the patchbot.

comment:14 Changed 5 years ago by tscrim

Thank you for the review.

comment:15 Changed 5 years ago by vbraun

  • Branch changed from public/arith/fix_lcm-22630 to 40e2b0835e257b55aa013d5583ef0f1121111ba1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.