swlpc Git

123 lines (104 with data), 2.6 kB

/*
 * Integer maths shit - G.
 *
 * Only add functions here that are (a) implemented very efficiently 
 * (for what they do), and (b) take more than 4 lines.  i.e. no sqare() 
 * function. Also - MAIL ME ABOUT THEM.  I want to vet any additions to 
 * this file - G.
 *
 * All functions round down.
 */

int MAXINT = (1<<30) - 1;

reset() { return 0; }

int sqrt(int n) {	/* integer square root - G. */
    if (n < 0)
	throw "sqrt: negative argument";

/* bitwise search for root.  Max 15 iterations. */

    int x = 14;			/* 32 bit ints; (2^14)*2^(14) is top */
				/* bit of sqrt(maxint) */
    int y = 0;
    do {
	int z = y | (1 << x);
	if (z * z <= n)
	    y = z;
	x--;
	} while (x >= 0);
    return y;
}

/*
 * Log base 2, rounded down (effectively, returns the index of the
 * top bit set in an integer).  If logN turns out faster, we'll
 * use its algorithm.
 */

int log2(int n) {
    if (n <= 0)
	throw "log2: zero or negative argument";

/* similar to sqrt.  Effectively a bit search.  We go from 0 upwards because most numbers are < 64K. */
    int x = (-1);
    while ((++x) < 30)
	if ((1 << x) > n)
	    return (x-1);
    return x;
}

/*
 * Log base N.  The same, maybe faster - G :)
 */

int logN(int n, int base) {
    if (n <= 0)
	throw "logN: zero or negative argument";
    if (base < 2)
	throw "logN: log base < 2 : " + base;

    int x = 0, y = 1, z = n / base;

    while (y <= z) {
	y *= base;
	x++;
	}
    return x;
}

/*
 * Exponential - G.
 * Most times, it's simpler to write x*x*x*x for x^4 (and
 * will run somewhat faster for small indices - saves call overhead, etc).
 * Since we're rounding down, x^y = 0 if y < 0.
 * Running time logarithmic in the size of the index.
 */

int exp(x, y) {
    if (y < 0)
	return 0;

/*
 * log-time exp (logarithmic in y).  x ^ y = (x^(y/2))^2 * (x ^ (y mod 2)).
 * So a recursive version could carve the exponent in half each iteration.
 * To make it iterative, we work bottom up - squaring x and halving y at
 * each iteration.  Max 31 iters, though the max useful exponent before
 * overflow is itself 31 (so in real use, max iterations should be 5 or less).
 * Break-even point between this and a simple loop is at about x^4.
 */

     int res = 1;
     while (y) {
	 if (y & 1) res *= x;
	 x *= x;
	 y >>= 1;
	 }
    return res;
}

/*
 * GCD, iterative, positive numbers only.  G.
 * Returns 0 if any input numbers are out of range.
 */

int gcd(a, b) {
    int tmp;
    if (a <= 0 || b <= 0)
	return 0;
    if (a < b) {
	tmp = a;
	a = b;
	b = tmp;
	}
    tmp = a % b;
    while (tmp != 0) {
	a = b;
	b = tmp;
	tmp = a % b;
	}
    return b;
    }