calc/calc/jump.h

   1 /*
   2  * jump - trivial prime jump table
   3  *
   4  * Copyright (C) 1999  Landon Curt Noll
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
  19  *
  20  * @(#) $Revision$
  21  * @(#) $Id$
  22  * @(#) $Source$
  23  *
  24  * Under source code control:   1994/06/29 04:03:55
  25  * File existed as early as:    1994
  26  *
  27  * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  28  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  29  */
  30
  31 /*
  32  * If x is divisible by a trivial prime (2,3,5,7,11), then:
  33  *
  34  *              x + jmpindx[ (x>>1)%JMPMOD ]
  35  *
  36  * is the value of the smallest value > x that is not divisible by a
  37  * trivial prime.  JMPMOD is the product of the odd trivial primes.
  38  *
  39  * This table is useful for skipping values that are obviously not prime
  40  * by skipping values that are a multiple of trivial prime.
  41  *
  42  * If x is not divisible by a trivial prime, then:
  43  *
  44  *              x + jmp[ -jmpindx[(x>>1)%JMPMOD] ]
  45  *
  46  * is the value of the smallest value > x that is not divisible by a
  47  * trivial prime.
  48  *
  49  * If jmpindx[y] > 0 (y = x mod JMPMOD*2), then it refers to an 'x' that
  50  * is divisible by a trivial prime and jmpindx[y] is the offset to the next
  51  * value that is not divisible.
  52  *
  53  * If jmpindx[y] <= 0, then 'x' is not divisible by a trivial prime and
  54  * the negative of jmpindx[y] is the index into the jmp[] table.  We use
  55  * successive values from jmp[] (wrapping around to the beginning when
  56  * we move off the end of jmp[]) to move to higher and higher values
  57  * that are not divisible by trivial primes.
  58  *
  59  * Instead of testing successive odd values, this system allows us to
  60  * skip odd values divisible by trivial primes.  This is process on the
  61  * average reduces the values we need to test by a factor of at least 2.4.
  62  */
  63
  64
  65 #if !defined(__JUMP_H__)
  66 #define __JUMP_H__
  67
  68
  69 #if defined(CALC_SRC)   /* if we are building from the calc source tree */
  70 # include "calc/have_const.h"
  71 #else
  72 # include <calc/have_const.h>
  73 #endif
  74
  75
  76 /*
  77  * trivial prime CONSTants
  78  */
  79 #define JMPMOD (3*5*7*11)       /* product of odd trivial primes */
  80 #define JMPSIZE (2*4*6*10)      /* ints mod JMPMOD not div by trivial primes */
  81 #define JPRIME (prime+4)        /* pointer to first non-trivial prime */
  82
  83 /* given x, return the index within jmpindx that applies */
  84 #define jmpmod(x) (((x)>>1)%JMPMOD)
  85
  86 /* jmpindx table value */
  87 #define jmpindxval(x) (jmpindx[jmpmod(x)])
  88
  89 /* return the smallest value >= x not divisible by a trivial prime */
  90 #define firstjmp(x,tmp) ((tmp) = jmpindxval(x), ((tmp) > 0) ? ((x)+(tmp)) : (x))
  91
  92 /* given x not divisible by a trivial prime, return jmp[] index */
  93 #define jmpptr(x) (-jmpindxval(x))
  94
  95 /* given a jmp pointer, return current jump increment and bump the pointer */
  96 #define nxtjmp(p) ( *( ((p)<lastjmp) ? ((p)++) : (((p)=jmp),lastjmp) ) )
  97
  98 /* given a jmp pointer, return dec pointer and return previous jump increment */
  99 #define prevjmp(p) ( *( ((p)>jmp) ? (--(p)) : ((p)=lastjmp) ) )
 100
 101 /*
 102  * external jump tables
 103  */
 104 extern CONST short jmpindx[];
 105 extern CONST unsigned char jmp[];
 106 extern CONST unsigned char *CONST lastjmp;
 107
 108 #endif /* !__JUMP_H__ */