A simple sieve in Phobos?

[Marco Leise]

Am Sun, 30 Mar 2014 23:05:55 +0000
schrieb "safety0ff" <safety0ff.dev at gmail.com>:

> I think we need a solid integer math module more than anything on 
> this list.
> I find myself often reimplementing ilog2, isqrt, isPowerOf2, etc, 
> etc.

More or less real world stuff:

minMax(x, low, high)
  Returns x clamped the low and high boundary so that
  low <= x <= high.
setMax(x, high)
  Same but only clamps high values.
setMin(x, low)
  Same but only clamps low values.
isWithin(x, low, high)
  Checks if x is within a given range.
isPowerOfTwo(x)
  Basically checks if only one bit is set.
nextPowerOfTwo(x)
  Returns x rounded up to be a power of two.
bitMask(T)(T bitNum)
  Returns cast(T) 1 << x. The result is always the type of the
  parameter.
bitMaskRange(firstBitNum, bitCount)
  Generates a mask of consecutive set bits starting with
  'firstBitNum' and counting 'bitCount' bits.
log2(x)
  Returns the highest power of 2 in 'x'.
roundUp(x, multiple)
  Rounds 'x' up to the next multiple of 'multiple'.
  A version that works with pointers is also useful.
roundDown(x, multiple)
  Rounds 'x' down to the next multiple of 'multiple'.
roundUpDiv(x, divisor)
  Normal integer division rounds down. This version rounds up.
sqr(x)
  x*x
KiB(x)
  x*1024
MiB(x)
  x*1024*1024
isEven(x)
  !(x & 1)

From Project Euler solutions:

sum_1_to_n(n)
  Returns the sum of all integers [1 .. n] in O(1) time
  complexity.
sum_1_to_n_dividable_by(n, d)
  Same as above but counts only values dividable by 'd'.
generalized_pentagonal_number(n)
  Don't know what this is, but it is O(1) as well.
gcd(u, v)
  Greatest common divisor. Some copied&pasted algorithm, that
  works by comparing set bits in 'u' and 'v'. Very fast for
  being implemented in standard C without assembly hacks.
are_coprime(u, v)
  Returns true, iff the greatest common divisor of 'u' and 'v'
  is 1.
pascal_row(n)
  Returns the n-th row of Pascal's triangle. This gives you
  "n choose k" for a fixed 'n' and all k in 0<=k<=n.
  (This function allocates an integer array.)

Also there is a Pascal's triangle struct, that allows marching
through the triangle quickly using methods like 'rightUp' or
'left'. Pascal's triangle operations are useful in
combinatorics.

----------8<-------------

/**
 * The ultimate tool to move around in Pascal's triangle. Pascal(0, 0) is the
 * top of the triangle with the value of 1.
 */
struct Pascal
{
	this(ℕ n, ℕ k) {
		// internally we offset these by +1, to simplify the math
		++n; ++k;
		_n = n;
		if (k > n / 2) {
			_k = _n;
			left(_n - k);
		} else {
			right(k - 1);
		}
	}
	
	ℕ left(ℕ amount) {
		while (amount--) {
			_value *= --_k;
			_value /= _n - _k;
		}
		return _value;
	}
	
	ℕ right(ℕ amount) {
		while (amount--) {
			_value *= _n - _k;
			_value /= _k++;
		}
		return _value;
	}
	
	ℕ rightDown(ℕ amount) {
		while (amount--) {
			_value *= _n++;
			_value /= _k++;
		}
		return _value;
	}

	ℕ leftDown(ℕ amount) {
		while (amount--) {
			_value *= _n++;
			_value /= _n - _k;
		}
		return _value;
	}

	ℕ leftUp(ℕ amount) {
		while (amount--) {
			_value *= --_k;
			_value /= --_n;
		}
		return _value;
	}

	ℕ rightUp(ℕ amount) {
		while (amount--) {
			_value *= _n - _k;
			_value /= --_n;
		}
		return _value;
	}
	
	@property
	ℕ value() { return _value; }
	
	alias value this;
	
	private:
	
	ℕ _n = 1, _k = 1;
	ℕ _value = 1;
}

-- 
Marco