Opened 11 years ago

Closed 7 years ago

#7656 closed enhancement (duplicate)

Bitset tricks

Reported by: jason Owned by: tbd
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: misc Keywords:
Cc: Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mvngu)

There are some extra tricks in here: http://www.jjj.de/fxt/#fxtbook

in the first chapter for doing bitset operations that ought to be applied to our Bitset class. For example, there is a trick that allows you to count the number of bits in log time instead of linear time.

More bitset tricks can be found at:

The project on this ticket can be divided up into the following sub-projects:

  1. #10287 memleak in bitset_realloc()
  2. #10093 clean up documentation of sage/misc/bitset.pyx
  3. #10269 clean up documentation of sage/misc/bitset_pxd.pxi
  4. #10245 clean up documentation of sage/misc/bitset.pxi

Change History (14)

comment:1 Changed 11 years ago by jason

  • Milestone changed from sage-4.4.2 to sage-wishlist
  • Priority changed from major to minor

comment:2 Changed 11 years ago by mvngu

  • Description modified (diff)

comment:3 Changed 11 years ago by mvngu

  • Description modified (diff)

comment:4 Changed 10 years ago by mvngu

  • Description modified (diff)

comment:5 Changed 10 years ago by mvngu

  • Description modified (diff)

comment:6 Changed 10 years ago by mvngu

  • Description modified (diff)

comment:7 Changed 10 years ago by ncohen

This FXTBook is the best book in the universe. I'm *EAGER* to read it.

About the counting trick : there is a builtin gcc command called builtin_popcount which may do wonders. It does count the bits in general (though I haven't found the corresponding code) -- it may well be the logarithmic way (+very nice trick btw), and in case the popcnt instruction is available on the processor, it is directly called.

And I assure you for having compared the two that it does.... WONDERS :-D

Nathann

comment:8 Changed 10 years ago by jason

If we can guarantee that gcc is used to compile the file, then great! I think we can assume that for now, but it may not be true in the future. Is there a preprocessor check we can put in or something?

comment:9 Changed 10 years ago by ncohen

I'd say "test for GNUC with the preprocessor". Though on these aspects I'd ask David first :-D

http://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html

Nathann

comment:10 Changed 10 years ago by ncohen

Oh. Actually I already did and he advised to use this very piece of code

#ifdef __GNUC__
 /* Make use of GCC extensions here. */
#else
/* Add portable version here */
#endif

Give to Caesar .. :-)

Nathann

comment:11 Changed 7 years ago by jdemeyer

This ticket is very vague. It should either be made more concrete (like, what do you want to do with bitsets) or closed as "invalid".

comment:12 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

...and it's probably superseded by #16937 also.

comment:13 Changed 7 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:14 Changed 7 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.