সোমবার, ৬ জানুয়ারী, ২০১৪

Clever Programming Tricks


All of these tricks are intended to save a factor of at least two (and often ten or more) by local changes to code. Of course algorithmic improvement can provide much greater efficiency gains, so I am assuming that you have done all you can in this respect, BEFORE using these tricks.

Algorithmic Ideas

  • Use a lookup table instead of calculating things when needed. Nowadays tables of 10^6 entries are cheap; indeed tables of 10^8 entries can easily be stored on a CD. Example: Noughts and Crosses (Amer. Tic-Tac-Toe): It may be amusing to write a planner for this game, but for efficiency... Pre-compute a table of size at most 3^9 (9 squares holding 0,X or blank) Positions encode `who is to move' by counting 0's and X's. Mark completed games (wins/draws/losses) as 1/0/-1 (unreachable positions like `both sides have won' can be marked randomly, e.g. draw). Back-propagate to mark all positions (using min or max according to turn). This will mark initial position with result if both sides play as well as possible (i.e. draw for this game). Adding a `best move' entry to the table for each position can be done cheaply during back-propagation. Cost is at most 9*3^9 operations (up to 9 predecessors of each position) which is 177147 steps. Cost to play a move is 1 instruction.

Low level hacks

These are all coded in strictly conformant ANSI C; we use 'unsigned' arithmetic to ensure overflow is ignored. Numeric postfixes like `unsigned32' mean that *at least* 32 bits are required to make this work. (ANSI C guarantees `long' has at least 32 bits, but does not necessarily provide a type suitable for `int64' etc). General assumption. If a routine tests (e.g.) a 32-bit integer having a certain property then the actual argument is assumed to be zero-extended to the size of the container type.
  • Determine parity of a 8-bit byte (assumed zero padded). Really this should be done by a lookup-table, but the following idea (adapted from Digital's DEC-10 assembler manual) is pretty:
    int parity(unsigned8 x) {
      return (((x * 0x10101) & 011111111) * 011111111) >> 21 & 1;
      /* MULT makes 3 copies of x, then AND re-selects each bit in `x' only */
      /* once (separated).  MULT adds up all such in bit 21 (cf long        */
      /* multiplication); OK since there can be no carry in to bit 21.      */
    }
    
  • Determine if a 32-bit word has a zero (8-bit) byte (useful in strcpy/strcmp)
    int haszerobyte(unsigned32 x) {
      return ((x - 0x01010101) & (~x) & 0x80808080) != 0;
    }
    
  • Determine if a 64-bit word has a zero (8-bit) byte (useful in strcpy/strcmp)
    int haszerobyte(unsigned64 x) {
      return ((x - 0x010101010101010) & (~x) & 0x8080808080808080) != 0;
    }
    
  • Count the `1' bits in a 9-bit value:
    int count_ones(unsigned36 x) {
      return ((((x * 01001001001) & 0x111111111) % 15;
    }
    
  • if A is a 9 bit quantity, B gets number of 1's (Schroeppel)
            IMUL A,[1001001001]     ;4 copies
            AND A,[42104210421]     ;every 4th bit
            IDIVI A,17              ;casting out 15.'s in hexadecimal
    
    ;if A is 6 bit quantity, B gets 6 bits reversed (Schroeppel)
            IMUL A,[2020202]        ;4 copies shifted
            AND A,[104422010]       ;where bits coincide with reverse repeated base 2^8
            IDIVI A,377             ;casting out 2^8 - 1's
    
    ;reverse 7 bits (Schroeppel)
            IMUL A,[10004002001]    ;4 copies sep by 000's base 2 (may set arith. o'flow)
            AND A,[210210210010]    ;where bits coincide with reverse repeated base 2^8
            IDIVI A,377             ;casting out 377's
    
    ;reverse 8 bits (Schroeppel)
            MUL A,[100200401002]    ;5 copies in A and B
            AND B,[20420420020]     ;where bits coincide with reverse repeated base 2^10
            ANDI A,41               ;"
            DIVI A,1777             ;casting out 2^10 - 1's
    
References: (Search for hakmem on the web) e.g. http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html  section ofhttp://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html 

0 মন্তব্য(গুলি):

একটি মন্তব্য পোস্ট করুন