This is just an idea that needs testing.

When working with probabilities, there are several representations:

• Integers, between 0 and the maximum value (8 bit / 16 bit / 32 bit).
• Floating point numbers, usually between 0.0 and 1.0 (wasteful, needs FPU).
• Fractions.

I won't be discussing floating point numbers.

Fractions are represented by an integer numerator and integer denominator.

The mathematical operations on probabilities (0 <= p <= 1) are:

• Addition
• Subtraction (especially 1-p)
• Multiplication
• Division
• Comparision (>, <, =)

Addition and subtraction:

• With integers, this is trivial; 1 operation.
• With fractions, the denominators need to be the same. There are many operations: multiply denominators, multiply numerators and add numberators. This is expensive.

Multiplication:

• With integers, we need to keep in mind that the integer is actually representing the value n/MAX_VALUE.  This means that the numerators need to be multiplied, and then divided by MAX_VAL.
• With fractions, this is two operations, one for each numerator and denominator.

Division:

• With integers, precision is lost. This may be 1 operation depending on hardware support. ARM didn't originally have a division operation and it had to be done in software.
• With fractions, no hardware division operation is needed. The divisor is inverted (usually 3 operations unless there is a "swap" operation) and 2 more operations are used for multiplying. With hardware support, the inversion could be done with clever wiring and it would become a single operation.

Comparison:

• Same as addition and subtraction.

Reduction might be nice but a common divisor must be found, which can be an expensive operation. Fractions can be lossy. If the numerator or denominator gets too large, they can just be bit-shifted right (i.e. divide numerator and denominator by 2). This will lose the fraction some accuracy but the fraction will still be approximately correct. As an optimisation, numerator and denominator could be bit-shifted right without loss of precision if the lowest bits are the same.

Fractions may be faster if:

• Hardware has no floating point unit.
• Hardware has no fast division operator.
• Hardware has support for fraction operations: fractions are stored in 32 bits with single-cycle operations.

With custom hardware, this can become very fast. With existing hardware, it shouldn't matter too much as the hardware supports lots of fast operations.