Fixed-point arithmetic library

[Tom Anderson]

Evening all,

I would quite like to represent some numbers in fixed point, and do
arithmetic with them.

These numbers will mostly not be more than a bilion, and will probably
never be more than a hundred billion. Some of them, i will need to
represent to eight decimal places. I'd like to be able to multiply two
large numbers, but i suspect will not need to multiply three. 11 * 2 + 8 =
30 decimal digits; that's about 100 bits, so 128 bits would be big enough
(about 5 decimal digits of headroom).

Can anyone suggest an existing library for doing fixed-point arithmetic
which would cover this?

I have googled, but not found anything. There are a few fixed-precision
libraries aimed at J2ME (i assume because old phones didn't have
floating-point units?). There's something called jExigo, but it's 64-bit
and the code doesn't look great.

It's quite possible that there is no such library. But i thought it
prudent to ask before writing one myself.

Thanks,
tom

 

[Jan Burse]

If a decimal scale suits you, you could use:

http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html

Decimal scale means your numbers would be represented as:

mantissa * 10 ^ -scale

Bye

 

[Robert Klemme]

Evening all,

I would quite like to represent some numbers in fixed point, and do
arithmetic with them.

Fixed point math is susceptible to precision issues which can be more
severe than those of float and double: 0.01 * 0.2 -> 0.00

http://en.wikipedia.org/wiki/Fixed_point_arithmetic#Precision_loss_and_overflow

Out of curiosity: What do you want to do with that?

These numbers will mostly not be more than a bilion, and will probably
never be more than a hundred billion. Some of them, i will need to
represent to eight decimal places. I'd like to be able to multiply two
large numbers, but i suspect will not need to multiply three. 11 * 2 + 8
= 30 decimal digits; that's about 100 bits, so 128 bits would be big
enough (about 5 decimal digits of headroom).

Can anyone suggest an existing library for doing fixed-point arithmetic
which would cover this?

I have googled, but not found anything. There are a few fixed-precision
libraries aimed at J2ME (i assume because old phones didn't have
floating-point units?). There's something called jExigo, but it's 64-bit
and the code doesn't look great.

It's quite possible that there is no such library. But i thought it
prudent to ask before writing one myself.

What about BigDecimal?
http://docs.oracle.com/javase/6/docs/api/java/math/BigDecimal.html

You could either add the precision loss after operations or just apply
it for output.

package math;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class FixedPointMath {

public static void main(String[] args) {
BigDecimal bd1 = new BigDecimal("0.01");
BigDecimal bd2 = new BigDecimal("0.2");
BigDecimal bd3 = bd1.multiply(bd2);
BigDecimal bd4 = bd3.setScale(2, RoundingMode.HALF_UP);
System.out.println(bd1 + " * " + bd2 + " -> " + bd3 + " -> " +
bd4);
}

}

Alternatively you could use BigInteger and add the scaling logic
yourself when cooking your fixed math lib.

http://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html

Kind regards

robert

 

[Gene Wirchenko]

Fixed point math is susceptible to precision issues which can be more
severe than those of float and double: 0.01 * 0.2 -> 0.00

Only if the target precision does not have enough decimal places.

I have been working with fixed-point arithmetic in JavaScript so
that I can add dollar amounts exactly. Maybe OP has something similar
in mind, though with the number of digits of precision that he wants
before the decimal point, I hope it is not currency-related.

[snip]

Sincerely,

Gene Wirchenko

 

[Martin Gregorie]

Only if the target precision does not have enough decimal places.

I have been working with fixed-point arithmetic in JavaScript so
that I can add dollar amounts exactly. Maybe OP has something similar
in mind, though with the number of digits of precision that he wants
before the decimal point, I hope it is not currency-related.

Not necessarily. BigDecimal has few surprises, but then its not fixed
decimal. The only fixed decimal arithmetic I've done in anger was in
Cobol, which will merrily do the following (Identification and
Environment divisions omitted for brevity).

DATA DIVISION.
WORKING-STORAGE.
01 FIXED-DECIMAL-FIELDS.
05 FD-VALUE PIC S9(6)v9(6) COMP SYNC.
05 FD-DIVISOR PIC S9(6)v9(6) COMP SYNC.
05 FD-RESULT PIC S9(6)v9(6) COMP SYNC.
05 FD-REMAINDER PIC S9(6)V9(6) COMP SYNC.

01 DISPLAY-LINE.
05 DL-VALUE PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " / ".
05 DL-DIVISOR PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " = ".
05 DL-RESULT PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " REMAINDER ".
05 DL-REMAINDER PIC -(6)V.9(6).

PROCEDURE DIVISION.
MAIN SECTION.
M-1.
MOVE 0.8 TO FD-VALUE DL-VALUE.
MOVE 2.0 TO FD-DIVISOR DL-DIVISOR.
DIVIDE FD-VALUE BY FD-DIVISOR GIVING FD-RESULT REMAINDER FD-REMAINDER.
MOVE FD-RESULT TO DL-RESULT.
MOVE FD-REMAINDER TO DL-REMAINDER.
DISPLAY DISPLAY-LINE.
STOP RUN.


This would display

" 0.800000 / 2.000000 = 0.000000 REMAINDER 0.800000"

because, of course, it is exactly equivalent to dividing 800000 by
2000000 and then adding decimal points in their correct fixed positions.
Is that what you want or is BigDecimal doing the right thing for your
problem space?

Apologies for not showing a Cobol SSCE, but I don't have a COBOL compiler
available to check it.

 

[Tom Anderson]

If a decimal scale suits you, you could use:

http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html

Decimal would be fine. BigDecimal might actually be okay too.

I've actually misrepresented the context for this question slightly. My
current place of work does a few calculations, and we currently use a
fixed-point implementation of our own. However, it doesn't quite meet all
our needs. My choice is really between extending it, and replacing it with
something else. Being lazy, i would rather take advantage of someone
else's hard work than do any myself.

Now, we wrote this fixed-point implementation having previously used
BigDecimal, because we had some serious performance problems with that.
This was before my time, so i'm very hazy on the details. I had already
dismissed BigDecimal out of hand on the basis of that, but it might
actually be worth looking at again.

I'd still be interested in any existing fixed-point libraries, as another
option to consider.

tom

 

[Tom Anderson]

Only if the target precision does not have enough decimal places.

I have been working with fixed-point arithmetic in JavaScript so
that I can add dollar amounts exactly. Maybe OP has something similar
in mind, though with the number of digits of precision that he wants
before the decimal point, I hope it is not currency-related.

It is currency-related. What's wrong with that?

tom

 

[Tom Anderson]

The only fixed decimal arithmetic I've done in anger was in Cobol, which
will merrily do the following (Identification and Environment divisions
omitted for brevity).

DATA DIVISION.
WORKING-STORAGE.
01 FIXED-DECIMAL-FIELDS.
05 FD-VALUE PIC S9(6)v9(6) COMP SYNC.
05 FD-DIVISOR PIC S9(6)v9(6) COMP SYNC.
05 FD-RESULT PIC S9(6)v9(6) COMP SYNC.
05 FD-REMAINDER PIC S9(6)V9(6) COMP SYNC.

01 DISPLAY-LINE.
05 DL-VALUE PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " / ".
05 DL-DIVISOR PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " = ".
05 DL-RESULT PIC -(6)V.9(6).
05 FILLER PIC X() VALUE " REMAINDER ".
05 DL-REMAINDER PIC -(6)V.9(6).

PROCEDURE DIVISION.
MAIN SECTION.
M-1.
MOVE 0.8 TO FD-VALUE DL-VALUE.
MOVE 2.0 TO FD-DIVISOR DL-DIVISOR.
DIVIDE FD-VALUE BY FD-DIVISOR GIVING FD-RESULT REMAINDER FD-REMAINDER.
MOVE FD-RESULT TO DL-RESULT.
MOVE FD-REMAINDER TO DL-REMAINDER.
DISPLAY DISPLAY-LINE.
STOP RUN.


This would display

" 0.800000 / 2.000000 = 0.000000 REMAINDER 0.800000"

because, of course, it is exactly equivalent to dividing 800000 by
2000000 and then adding decimal points in their correct fixed positions.

.... right. Yes, this is indeed not great. But i don't think this is a
correct implementation of fixed-point; what you actually have here is
essentially integers which are being printed with a format with dots in,
right? A fixed-point implementation of multiplication or division needs to
do some scaling to get the right answers.

Is that what you want or is BigDecimal doing the right thing for your
problem space?

I don't want what the COBOL does. I need to be able to divide by 2.

tom

 

[Gene Wirchenko]

[snipped COBOL code]

... right. Yes, this is indeed not great. But i don't think this is a

If you need exact decimal representation, it is good.

correct implementation of fixed-point; what you actually have here is
essentially integers which are being printed with a format with dots in,
right? A fixed-point implementation of multiplication or division needs to

Well, yes, that is about what fixed-point is. Certainly, it is a
common implementation of it.

do some scaling to get the right answers.

COBOL handles the scaling automatically.

I don't want what the COBOL does. I need to be able to divide by 2.

You can do that with COBOL. Why do you think that you can not?

Sincerely,

Gene Wirchenko

 

[markspace]

...we currently use a
fixed-point implementation of our own. However, it doesn't quite meet
all our needs.

A big help for all of us would be to understand what needs, exactly, you
have. What are the requirements for this class/package? Given that no
one has offered anything besides BigDecimal, it might be moot as there
doesn't seem to be a lot out there, but it might help narrow down any
potential choices.

My choice is really between extending it, and replacing
it with something else. Being lazy, i would rather take advantage of
someone else's hard work than do any myself.

Or you could contract out for it. Sounds like a fun little side
project. We'd still need those requirements though.

 

[Gene Wirchenko]

On Wed, 22 Feb 2012, Gene Wirchenko wrote:
[snip]

I have been working with fixed-point arithmetic in JavaScript so
that I can add dollar amounts exactly. Maybe OP has something similar
in mind, though with the number of digits of precision that he wants
before the decimal point, I hope it is not currency-related.

It is currency-related. What's wrong with that?

You are dealing with monstrously-large numbers. National debts
or something similar?

If you only needed up to fifteen digits of precision total, you
could use IEEE 754 64-bit floating point format and store integers.
They will be stored exactly. IEEE 754 is the only number format that
JavaScript exposes for variable types (though it does use 32-bit
integers internally on some operations).

I had to experiment with this, but I got it working.

Looking up further, according to Wikipedia, there is a 128-bit
format that has 34.02 digits of precision. If your target language
has this format as one of its number types, you could store integers
in such variables. You did state that you need 30 digits of
precision, so this would fit. This would be a cheap, fairly simple
solution.

Sincerely,

Gene Wirchenko

 

[Robert Klemme]

Decimal would be fine. BigDecimal might actually be okay too.

I've actually misrepresented the context for this question slightly. My
current place of work does a few calculations, and we currently use a

"few" like in "a few millions per second"?

fixed-point implementation of our own. However, it doesn't quite meet
all our needs. My choice is really between extending it, and replacing
it with something else. Being lazy, i would rather take advantage of
someone else's hard work than do any myself.

Now, we wrote this fixed-point implementation having previously used
BigDecimal, because we had some serious performance problems with that.
This was before my time, so i'm very hazy on the details. I had already
dismissed BigDecimal out of hand on the basis of that, but it might
actually be worth looking at again.

How long is that benchmark ago? JVMs and standard library have changed
quite a bit during past years so the performance issues might actually
have gone by now.

If I would be the one responsible I'd do the measurements myself. It's
usually better to base such decisions on hard (and current) facts. Your
application obviously exists so you have a clear idea of the nature of
operations you have to perform as well as the frequency of operations as
well as the range of input data. That should make it quite easy to
build a benchmark which realistically reflects your business case. You
could separate the load driving from the used math implementation via
interface (see minimalistic example below) so you can reuse the same
tests for all the implementations you want to analyze (at least
BigDecimal and what you built).

Kind regards

robert


package clj.math;

/**
* Abstraction of math impl.
*
* @param <T>
* type of math numbers
* @author robert
*/
public interface Math<T> {

/**
* Create a new number from int.
*
* @param i
* an integer to be converted.
* @return a number object representing the int.
*/
T create(int i);

/**
* Create a new number from String.
*
* @param s
* input string, must be a decimal representation of a number.
* @return a number object representing the string.
*/
T create(String s);

/**
* Addition of two numbers.
*
* @param a
* a number
* @param b
* a number
* @return a + b
*/
T plus(T a, T b);

/**
* Multiplication of two numbers.
*
* @param a
* a number
* @param b
* a number
* @return a * b
*/
T mult(T a, T b);
}

 

[Lew]

On Wed, 22 Feb 2012, Gene Wirchenko wrote:
[snip]

I have been working with fixed-point arithmetic in JavaScript so
that I can add dollar amounts exactly. Maybe OP has something similar
in mind, though with the number of digits of precision that he wants
before the decimal point, I hope it is not currency-related.

It is currency-related. What's wrong with that?

You are dealing with monstrously-large numbers. National debts
or something similar?

If you only needed up to fifteen [decimal] digits of precision total, you
could use IEEE 754 64-bit floating point format and store integers.
They will be stored exactly. IEEE 754 is the only number format that
JavaScript exposes for variable types (though it does use 32-bit
integers internally on some operations).

I had to experiment with this, but I got it working.

Looking up further, according to Wikipedia, there is a 128-bit
format that has 34.02 [decimal] digits of precision. If your target language
has this format as one of its number types, you could store integers
in such variables. You did state that you need 30 [decimal] digits of
precision, so this would fit. This would be a cheap, fairly simple
solution.

Are you taking into account the precision of intermediate results?

If you multiply to 30-digit values you need 60 digits of precision to
represent the calculation.

This is a good time to recommend that everyone read "What Every Computer
Scientist Should Know About Floating Point Arithmetic", by David Goldberg.

 

[Jan Burse]

You might want to implement a flexible ALU. You
could use:

Long: To represent [-922337203685477.5808, 922337203685477.5807]
BigDecimal: To represent everyting that is outside of the above
range or has not a scale 4.

You can implement the ALU as static methods that take
as argument the type Number.

public class myALU {

public Number add(Number a, Number b);
Etc..

}

I did not yet do it. But I did something similar for
arbitrary long integers. So I was dynamically switching
between:

Integer: To represent [2147483648, 2147483647]
BigInteger: To represent everyting that is outside of
the above range.

I also used Integer.valueOf() instead of new Integer(),
since the later works with a small cache. The overall
performance boost was quite visible.

I am planning to do the same for BigDecimals now. I have
picked the range [-922337203685477.5808, 922337203685477.5807]
since many databases (for example MS SQL Server) use this
range and scale for a small currency/money datatype.

Bye

 

[Martin Gregorie]

It is currency-related. What's wrong with that?

I take it there is a mandatory and tightly specified set of operations
for currency conversion (or equivalent) involved in what you need to do?

If so, I've been there and they're usually specified that way to overcome
the deficiencies and rounding errors inherent in fixed point decimal
arithmetic as it is/was usually implemented in assembler or COBOL on
hardware that uses binary integers or BCD.

 

[Gene Wirchenko]

On 02/23/2012 02:03 PM, Gene Wirchenko wrote:
[snip]

Looking up further, according to Wikipedia, there is a 128-bit
format that has 34.02 [decimal] digits of precision. If your target language
has this format as one of its number types, you could store integers
in such variables. You did state that you need 30 [decimal] digits of
precision, so this would fit. This would be a cheap, fairly simple
solution.

Are you taking into account the precision of intermediate results?

OP apparently already has. Take a look at his original post.

If you multiply to 30-digit values you need 60 digits of precision to
represent the calculation.

His numbers are not quite THAT big.

This is a good time to recommend that everyone read "What Every Computer
Scientist Should Know About Floating Point Arithmetic", by David Goldberg.

Yes.

It is also worth pointing out that many *integer* values can be
represented exactly in floating point. The emphasis on "integer" is
deliberate.

Sincerely,

Gene Wirchenko

 

[Roedy Green]

These numbers will mostly not be more than a bilion, and will probably
never be more than a hundred billion. Some of them, i will need to
represent to eight decimal places

So long max 9,223,372,036,854,775,807 would be sufficient, except for
intermediate results? I had a similar problem back in 1985
implementing a 32-bit forth on a 16-bit 8086 architecture.

If your results are still 64 bits, just collecting the low order bits
will work.

If you need 128 bits, you could do it like this for unsigned multiply.

split your two numbers into two 32 bit quantities

a = bc
d = ef


a * d = c*f + (b*f + c*e) >> 32 + (b*e) >> 64

In assembler this is easier since you get the high bits too as a
matter of course from a multiply.

If you don't need much, rolling your own based on the way you did it
in grade 4 (considering your numbers as base 2^32 numbers rather than
base 10). might be much easier than introducing a full library.

In the process I bested Knuth and came up with a more efficient
multiprecision division algorithm.

 

[glen herrmannsfeldt]

(snip)

Fixed point math is susceptible to precision issues which can
be more severe than those of float and double: 0.01 * 0.2 -> 0.00

In PL/I, if you multiply, you get the appropriate number if digits
after the radix point.

FIXED DECIMAL(3,2) times FIXED DECIMAL(2,1) generates a
product of FIXED DECIMAL(5,3). If you force it to throw away
low order digits, then, yes you can lose precision.

-- glen

 

[Arne Vajhøj]

(snip)


In PL/I, if you multiply, you get the appropriate number if digits
after the radix point.

FIXED DECIMAL(3,2) times FIXED DECIMAL(2,1) generates a
product of FIXED DECIMAL(5,3). If you force it to throw away
low order digits, then, yes you can lose precision.

That is rather similar to how BigDecimal works.

import java.math.BigDecimal;

public class Fixed {
public static void main(String[] args) {
BigDecimal d1 = new BigDecimal("12.3");
System.out.println(d1 + " " + d1.scale());
BigDecimal d2 = new BigDecimal("4.56");
System.out.println(d2 + " " + d2.scale());
BigDecimal d3 = d1.multiply(d2);
System.out.println(d3 + " " + d3.scale());
}
}

12.3 1
4.56 2
56.088 3

Arne

 

[Robert Klemme]

That is rather similar to how BigDecimal works.

And that is not exactly how FP arithmetic is described in Wikipedia:

"For simplicity, fixed-point multiply procedures use the same result
format as the operands. This has the effect of keeping the middle bits;
the I-number of least significant integer bits, and the Q-number of most
significant fractional bits. Fractional bits lost below this value
represent a precision loss which is common in fractional multiplication.
If any integer bits are lost, however, the value will be radically
inaccurate."

It boils down to how fixed "fixed" is. In my understanding decimal
places are fixed throughout the whole calculation which is not what BD
does (obviously to avoid precision loss).

Kind regards

robert