Changes between Initial Version and Version 1 of Ticket #19301


Ignore:
Timestamp:
09/28/15 18:29:21 (4 years ago)
Author:
ncohen
Comment:

New commits:

f6b88edtrac #19301: Cleanup in dense_graph.pyx
548b8f0trac #19301: complement()

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #19301

    • Property Status changed from new to needs_review
    • Property Commit changed from to 548b8f012647c1fae0ab8d080f2f27a382c39d51
    • Property Branch changed from to u/ncohen/19301
  • Ticket #19301 – Description

    initial v1  
    33With this, the computation of the complement is done on a dense graph, as it should.
    44
     5Before
     6{{{
     7sage: g=graphs.PaleyGraph(1009)
     8sage: %time g.complement()
     9CPU times: user 2.14 s, sys: 64 ms, total: 2.2 s
     10Wall time: 2.14 s
     11complement(Paley graph with parameter 1009): Graph on 1009 vertices
     12}}}
     13
     14After
     15{{{
     16sage: %time g.complement()
     17CPU times: user 164 ms, sys: 12 ms, total: 176 ms
     18Wall time: 160 ms
     19complement(Paley graph with parameter 1009): Graph on 1009 vertices
     20}}}
     21
     22In dense_graph.pyx, this branch mostly does the following:
     23- Turn 'radix' and radix_mod_mask' into module variables (they do not depend on the instance)
     24- remove 'radix_div_shift'. This variable is meant to turn a division by radix into a shift. As radix is determined at compile-time, the compiler already does this simplification (for free)
     25- Turn multiplication/division by powers of two from 'shift' to multiplication/division. The code is easier to read, and the compiled binary is the same anyway.
     26- Uses calloc (instead of malloc) to initialize memory. This is slightly wasteful, and the code is much cleaner as a result.
     27
    528Nathann