Fixed-point numbers can be used in place of floating-point numbers. Regarding fixed-point numbers:
Addition and subtraction of two fixed-point numbers is done normally, using + and - operators.
Multiplying a fixed-point number by an integer is done normally, using the * operator. The result is a fixed-point number.
Dividing a fixed-point number by an integer (the fixed-point number is the
numerator, and the integer is the denominator) is done normally, using the /
operator. The result is a fixed-point number.
*/
public class CoreMath {
public static final int FRACTION_BITS = 16;
public static final int FRACTION_MASK = (1 << FRACTION_BITS) - 1;
public static final int ONE = (1 << FRACTION_BITS);
public static final int ONE_HALF = ONE >> 1;
public static final int PI = (int)Math.round(Math.PI * ONE);
public static final int TWO_PI = (int)Math.round(2 * Math.PI * ONE);
public static final int ONE_HALF_PI = (int)Math.round(.5 * Math.PI * ONE);
public static final int E = (int)Math.round(Math.E * ONE);
public static final int MAX_VALUE = (1 << 31) - 1;
public static final int MIN_VALUE = -(1 << 31);
/** The maximum integer value that a 32-bit fixed-point value can represent. */
public static final int MAX_INT_VALUE = (1 << (31 - FRACTION_BITS)) - 1;
/** The minumum integer value that a 32-bit fixed-point value can represent. */
public static final int MIN_INT_VALUE = -(1 << (31 - FRACTION_BITS));
/** The maximum 32-bit floating-point value that a 32-bit fixed-point value can represent. */
// Math.round(MAX_FLOAT_VALUE * ONE) = MAX_VALUE
public static final float MAX_FLOAT_VALUE = 32768f;
/** The minumum 32-bit floating-point value that a 32-bit fixed-point value can represent. */
public static final float MIN_FLOAT_VALUE = -32768f;
/** The maximum 64-bit floating-point value that a 32-bit fixed-point value can represent. */
// Found this by trial and error
// Math.round(MAX_DOUBLE_VALUE * ONE) = MAX_VALUE
public static final double MAX_DOUBLE_VALUE = 32767.999992370602;
/** The minumum 64-bit floating-point value that a 32-bit fixed-point value can represent. */
public static final double MIN_DOUBLE_VALUE = -32768.0;
// For more accurate results for sine/cosine. This number was found by trial and error.
private static final int TWO_PI_ERROR_FACTOR = 6;
//private static final int TWO_PI_ERROR = -11;
private static final int TWO_PI_ERROR =
(int)Math.round((2*Math.PI*(1 << TWO_PI_ERROR_FACTOR) -
(double)(TWO_PI << TWO_PI_ERROR_FACTOR) / ONE) * ONE);
/** Number of fractional bits used for some internal calculations */
private static final int INTERNAL_BITS = 24;
// Prevent instantiation
private CoreMath() { }
/**
Converts an integer to a fixed-point value.
*/
public static final int toFixed(int n) {
if (n > MAX_INT_VALUE) {
return MAX_VALUE;
}
else if (n < MIN_INT_VALUE) {
return MIN_VALUE;
}
else {
return n << FRACTION_BITS;
}
}
/**
Converts a float to a fixed-point value.
*/
public static final int toFixed(float n) {
if (n > MAX_FLOAT_VALUE) {
return MAX_VALUE;
}
else if (n < MIN_FLOAT_VALUE) {
return MIN_VALUE;
}
else {
return Math.round(n * ONE);
}
}
/**
Converts a double-percsion float to a fixed-point value.
*/
public static final int toFixed(double n) {
if (n > MAX_DOUBLE_VALUE) {
return MAX_VALUE;
}
else if (n < MIN_DOUBLE_VALUE) {
return MIN_VALUE;
}
else {
return (int)Math.round(n * ONE);
}
}
/**
Converts a String representing a double-percsion float into a fixed-point value.
@throws NumberFormatException if the string does not contain a parsable number.
*/
public static final int toFixed(String n) throws NumberFormatException {
return toFixed(Double.valueOf(n).doubleValue());
}
/**
Converts a fixed-point value to a float.
*/
public static final float toFloat(int f) {
return (float)f / ONE;
}
/**
Converts a fixed-point value to a double.
*/
public static final double toDouble(int f) {
return (double)f / ONE;
}
/**
Converts a fixed-point value to an integer. Same behavior as casting
a float to an int.
*/
public static final int toInt(int f) {
if (f < 0) {
return toIntCeil(f);
}
else {
return toIntFloor(f);
}
}
/**
Converts a fixed-point value to an integer.
*/
public static final int toIntFloor(int f) {
return f >> FRACTION_BITS;
}
/**
Converts a fixed-point value to an integer.
*/
public static final int toIntRound(int f) {
return toIntFloor(f + ONE_HALF);
}
/**
Converts a fixed-point value to an integer.
*/
public static final int toIntCeil(int f) {
return -toIntFloor(-f);
}
/**
Returns the fractional part of a fixed-point value (removes the
integer part).
*/
public static final int fracPart(int f) {
return abs(f) & FRACTION_MASK;
}
/**
Returns the floor of a fixed-point value (removes the
fractional part).
*/
public static final int floor(int f) {
return f & ~FRACTION_MASK;
}
/**
Returns the ceil of a fixed-point value.
*/
public static final int ceil(int f) {
return -floor(-f);
}
/**
Returns the fixed-point value rounded to the nearest integer location.
*/
public static final int round(int f) {
return floor(f + ONE_HALF);
}
/**
Converts a fixed-point number to a base-10 string representation.
*/
public static final String toString(int f) {
return formatNumber(
abs(toInt(f)),
fracPart(f) << (32 - FRACTION_BITS), (f < 0),
1, 7, false);
}
/**
Converts a fixed-point number to a base-10 string representation using
the specified number of fractional digits.
*/
public static final String toString(int f, int numFractionalDigits) {
return formatNumber(
abs(toInt(f)),
fracPart(f) << (32 - FRACTION_BITS), (f < 0),
numFractionalDigits, numFractionalDigits, false);
}
/**
Converts a fixed-point number to a base-10 string representation.
@param f the fixed-point number
@param minFracDigits the minimum number of digits to show after
the decimal point.
@param maxFracDigits the maximum number of digits to show after
the decimal point.
@param grouping if (true, uses the grouping character (',')
to seperate groups in the integer portion of the number.
*/
public static String toString(int f,
int minFracDigits, int maxFracDigits, boolean grouping)
{
return formatNumber(
abs(toInt(f)),
fracPart(f) << (32 - FRACTION_BITS), (f < 0),
minFracDigits, maxFracDigits, grouping);
}
/**
Converts an integer to a base-10 string representation.
*/
public static final String intToString(int n) {
return formatNumber(abs(n), 0, (n < 0), 0, 0, false);
}
/**
Converts a integer to a base-10 string representation using
the specified number of fractional digits.
*/
public static final String intToString(int n, int numFractionalDigits) {
return formatNumber(abs(n), 0, (n < 0),
numFractionalDigits, numFractionalDigits, false);
}
/**
Converts an integer to a base-10 string representation.
@param n the integer
@param minFracDigits the minimum number of digits to show after
the decimal point.
@param maxFracDigits the maximum number of digits to show after
the decimal point.
@param grouping if (true, uses the grouping character (',')
to seperate groups in the integer portion of the number.
*/
public static String intToString(int n,
int minFracDigits, int maxFracDigits, boolean grouping)
{
return formatNumber(abs(n), 0, (n < 0),
minFracDigits, maxFracDigits, grouping);
}
/**
Converts a number to a base-10 string representation.
@param intPart the integer part of the number
@param fracPart the fractional part, a 32-bit fixed point value.
@param minFracDigits the minimum number of digits to show after
the decimal point.
@param maxFracDigits the maximum number of digits to show after
the decimal point.
@param intPartGrouping if (true, uses the groupong character (',')
to seperate groups in the integer portion of the number.
*/
private static String formatNumber(int intPart, int fracPart, boolean negative,
int minFracDigits, int maxFracDigits, boolean intPartGrouping)
{
StringBuffer buffer = new StringBuffer();
long one = 1L << 32;
long mask = one - 1;
long frac = ((long)fracPart) & mask;
// Round up if needed
if (maxFracDigits < 10) {
long place = 1;
for (int i = 0; i < maxFracDigits; i++) {
place *= 10;
}
frac += (1L << 31) / place;
if (frac >= one) {
intPart++;
}
}
// Convert integer part
if (!intPartGrouping || intPart == 0) {
if (negative) {
buffer.append('-');
}
buffer.append(intPart);
}
else {
int i = 0;
while (intPart > 0) {
if (i == 3) {
buffer.insert(0, ',');
i = 0;
}
char ch = (char)((intPart % 10) + '0');
buffer.insert(0, ch);
intPart /= 10;
i++;
}
if (negative) {
buffer.insert(0, '-');
}
}
if (maxFracDigits == 0 || (fracPart == 0 && minFracDigits == 0)) {
return buffer.toString();
}
buffer.append('.');
// Convert fractional part
int numFracDigits = 0;
while (true) {
frac = (frac & mask) * 10L;
if (frac == 0) {
buffer.append('0');
}
else {
buffer.append((char)('0' + ((frac >>> 32) % 10)));
}
numFracDigits++;
if (numFracDigits == maxFracDigits || (frac == 0 && numFracDigits >= minFracDigits)) {
break;
}
}
// Remove uneeded trailing zeros
if (numFracDigits > minFracDigits) {
int len = numFracDigits - minFracDigits;
for (int i = 0; i < len; i++) {
if (buffer.charAt(buffer.length() - 1) == '0') {
buffer.setLength(buffer.length() - 1);
}
else {
break;
}
}
}
return buffer.toString();
}
//
// Bit manipulation
//
/**
Returns true if the number (greater than 1) is a power of two.
*/
public static final boolean isPowerOfTwo(int n) {
return (n & (n - 1)) == 0;
}
/**
Counts the number of "on" bits in an integer.
*/
public static final int countBits(int n) {
/*
int count = 0;
while (n > 0) {
count += (n & 1);
n >>= 1;
}
return count;
*/
int count = n;
count = ((count >> 1) & 0x55555555) + (count & 0x55555555);
count = ((count >> 2) & 0x33333333) + (count & 0x33333333);
count = ((count >> 4) & 0x0F0F0F0F) + (count & 0x0F0F0F0F);
count = ((count >> 8) & 0x00FF00FF) + (count & 0x00FF00FF);
count = ((count >> 16) & 0x0000FFFF) + (count & 0x0000FFFF);
return count;
}
/**
Returns the log base 2 of an integer greater than 0. The returned value
is equal to {@code Math.floor(Math.log(n) / Math.log(2))}.
*/
public static final int log2(int n) {
//if (n <= 1) {
// throw new ArithmeticException("NaN");
//}
int count = 0;
while (true) {
n >>= 1;
if (n == 0) {
return count;
}
count++;
}
/*
int count = 0;
if ((n & 0xFFFF0000) != 0) {
n >>= 16;
count = 16;
}
if ((n & 0xFF00) != 0) {
n >>= 8;
count |= 8;
}
if ((n & 0xF0) != 0) {
n >>= 4;
count |= 4;
}
if ((n & 0xC) != 0) {
n >>= 2;
count |= 2;
}
if ((n & 0x2) != 0) {
//n >>= 1;
count |= 1;
}
return count;
*/
}
//
// Integer math
//
/**
Clamps a number between two values. If the number <= min returns min; if the number >= max
returns max; otherwise returns the number.
*/
public static final int clamp(int n, int min, int max) {
if (n <= min) {
return min;
}
else if (n >= max) {
return max;
}
else {
return n;
}
}
/**
Clamps a number between two values. If the number <= min returns min; if the number >= max
returns max; otherwise returns the number.
*/
public static final float clamp(float n, float min, float max) {
if (n <= min) {
return min;
}
else if (n >= max) {
return max;
}
else {
return n;
}
}
/**
Clamps a number between two values. If the number <= min returns min; if the number >= max
returns max; otherwise returns the number.
*/
public static final double clamp(double n, double min, double max) {
if (n <= min) {
return min;
}
else if (n >= max) {
return max;
}
else {
return n;
}
}
/**
Returns the sign of a number.
*/
public static final int sign(int n) {
return (n > 0)?1:((n < 0)?-1:0);
}
/**
Returns the sign of a number.
*/
public static final int sign(double n) {
return (n > 0)?1:((n < 0)?-1:0);
}
/**
Returns the absolute value of a number.
*/
public static final int abs(int n) {
return (n >= 0)?n:-n;
//return (n ^ (n >> 31)) - (n >> 31);
}
/**
Divides the number, n, by the divisor, d, rounding the result to the
nearest integer.
*/
public static final int intDivRound(int n, int d) {
if ((d > 0) ^ (n > 0)) {
return (n - (d >> 1)) / d;
}
else {
return (n + (d >> 1)) / d;
}
}
/**
Divides the number, n, by the divisor, d, returning the nearest integer
less than or equal to the result.
*/
public static final int intDivFloor(int n, int d) {
if (d > 0) {
if (n < 0) {
return (n - d + 1) / d;
}
else {
return n / d;
}
}
else if (d < 0) {
if (n > 0) {
return (n - d - 1) / d;
}
else {
return n / d;
}
}
else {
// d == 0 throws ArithmeticException
return n / d;
}
}
/**
Divides the number, n, by the divisor, d, returning the nearest integer
greater than or equal to the result.
*/
public static final int intDivCeil(int n, int d) {
return -intDivFloor(-n, d);
}
//
// Fixed-point math
//
/**
Multiplies two fixed-point numbers together.
*/
public static final int mul(int f1, int f2) {
return (int)(((long)f1 * f2) >> FRACTION_BITS);
}
/**
Multiplies two fixed-point numbers together.
*/
public static final long mul(long f1, long f2) {
return (f1 * f2) >> FRACTION_BITS;
}
/**
Divides the first fixed-point number by the second fixed-point number.
*/
public static final int div(int f1, int f2) {
return (int)(((long)f1 << FRACTION_BITS) / f2);
}
/**
Divides the first fixed-point number by the second fixed-point number.
*/
public static final long div(long f1, long f2) {
return (f1 << FRACTION_BITS) / f2;
}
/**
Multiplies the first two fixed-point numbers together, then divides by
the third fixed-point number.
*/
public static final int mulDiv(int f1, int f2, int f3) {
return (int)((long)f1 * f2 / f3);
}
/**
Multiplies the first two fixed-point numbers together, then divides by
the third fixed-point number.
*/
public static final long mulDiv(long f1, long f2, long f3) {
return f1 * f2 / f3;
}
//
// Logs and powers
//
public static final int sqrt(int fx) {
if (fx < 0) {
throw new ArithmeticException("NaN");
}
if (fx == 0 || fx == ONE) {
return fx;
}
// invert numbers less than one (if they aren't too small)
boolean invert = false;
if (fx < ONE && fx > 6) {
invert = true;
fx = div(ONE, fx);
}
int iterations = 16;
if (fx > ONE) {
// number of iterations == (number of bits in number) / 2
int s = fx;
iterations = 0;
while (s > 0) {
s >>=2;
iterations++;
}
}
// Newton's iteration
int l = (fx >> 1) + 1;
for (int i=1; i