Opened 7 years ago

Closed 7 years ago

#16424 closed enhancement (fixed)

is_triangular_number() cleanup

Reported by: rws Owned by:
Priority: minor Milestone: sage-6.3
Component: quadratic forms Keywords:
Cc: Merged in:
Authors: Vincent Delecroix Reviewers: Ralf Stephan
Report Upstream: N/A Work issues:
Branch: 5894592 (Commits) Commit: 5894592f6d380138198c4100fa0d55d7e75f3eb2
Dependencies: Stopgaps:

Description

The name implies a boolean return value (contrary to the implementation), and used that way the function is way too slow:

sage: timeit('l=[n for n in range(1000) if is_square(8*(n)+1)]')
625 loops, best of 3: 909 µs per loop
sage: timeit('l=[n for n in range(1000) if is_triangular_number(n)]')
5 loops, best of 3: 200 ms per loop
sage: timeit('l=[n for n in range(1000) if is_square(8*(n)+1)]')
625 loops, best of 3: 903 µs per loop
sage: timeit('l=[n for n in range(1000) if is_triangular_number(n)]')
5 loops, best of 3: 195 ms per loop

The reason is that the simple boolean test used above is not performed before the more involved computation of the index.

Change History (8)

comment:1 Changed 7 years ago by rws

  • Branch set to u/rws/is_triangular_number___speed_up

comment:2 Changed 7 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to de05b593cb8497493ce92e742a7379bdc8bf8489
  • Status changed from new to needs_review

Now it's only 10x slower:

sage: timeit('l=[n for n in range(1000) if is_triangular_number(n)]')
25 loops, best of 3: 10.6 ms per loop
sage: timeit('l=[n for n in range(1000) if is_triangular_number(n)]')
25 loops, best of 3: 10.1 ms per loop

but that is because the function does more than it should, judging from the name.


New commits:

de05b5916424: test first if we have a triangular number at all

comment:3 follow-up: Changed 7 years ago by vdelecroix

Hi Ralf,

see my branch at public/16424

I rewrote the function as it can be done in a much cleaner/faster way. Moreover, a function called is_X must return a boolean. It makes no sense to have it return boolean or integer values. I decided to add an extra argument return_value that does the job. I also rewrite the doc which was very ugly.

Tell me what you think...

Anyway, I am not sure it is worth it to have a function which is just equivalent to

is_triangular = lambda n: (8*n+1).is_square()

Vincent

comment:4 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to needs_info

comment:5 in reply to: ↑ 3 Changed 7 years ago by rws

  • Authors changed from Ralf Stephan to Vincent Delecroix
  • Branch changed from u/rws/is_triangular_number___speed_up to public/16424
  • Commit changed from de05b593cb8497493ce92e742a7379bdc8bf8489 to 5894592f6d380138198c4100fa0d55d7e75f3eb2
  • Reviewers set to Ralf Stephan
  • Status changed from needs_info to needs_work
  • Summary changed from is_triangular_number() speed up to is_triangular_number() cleanup

Replying to vdelecroix:

see my branch at public/16424

I rewrote the function as it can be done in a much cleaner/faster way. Moreover, a function called is_X must return a boolean. It makes no sense to have it return boolean or integer values. I decided to add an extra argument return_value that does the job. I also rewrite the doc which was very ugly.

Tell me what you think...

Anyway, I am not sure it is worth it to have a function which is just equivalent to

is_triangular = lambda n: (8*n+1).is_square()

Hi Vincent, the branch is fine. I would agree that the function is not worth occupying one of the precious global slots. However, I think it is still good to have, so you can set positive if you also remove it from quadratic_forms/all.py.


New commits:

33a3e17trac #16424: merge sage.6.3.beta3
5894592trac #16424: revamp 'is_triangular_number'

comment:6 Changed 7 years ago by vdelecroix

Hi Ralf,

I have no problem removing it from the global namespace but then how the user would find it? The path is really unguessable!

sage: from sage.quadratic_forms.extra import is_triangular_number

Vincent

comment:7 Changed 7 years ago by rws

  • Status changed from needs_work to positive_review

I don't know. Searching the reference will turn up lots of other links. I don't think we should put more thought into it, so any outcome is fine with me, as is the branch. Another ticket will resolve the global namespace cleanup.

comment:8 Changed 7 years ago by vbraun

  • Branch changed from public/16424 to 5894592f6d380138198c4100fa0d55d7e75f3eb2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.