Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Fixed-point arithmetic library

Reply
Thread Tools

Fixed-point arithmetic library

 
 
Gene Wirchenko
Guest
Posts: n/a
 
      02-23-2012
On Thu, 23 Feb 2012 21:16:04 +0000, Tom Anderson
<(E-Mail Removed)> wrote:

>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
 
Reply With Quote
 
 
 
 
Robert Klemme
Guest
Posts: n/a
 
      02-23-2012
On 02/23/2012 10:15 PM, Tom Anderson wrote:
> On Wed, 22 Feb 2012, Jan Burse wrote:
>
>> If a decimal scale suits you, you could use:
>>
>> http://docs.oracle.com/javase/7/docs...igDecimal.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


"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);
}
 
Reply With Quote
 
 
 
 
Lew
Guest
Posts: n/a
 
      02-23-2012
On 02/23/2012 02:03 PM, Gene Wirchenko wrote:
> On Thu, 23 Feb 2012 21:16:04 +0000, Tom Anderson
> <(E-Mail Removed)> wrote:
>
>> 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.

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      02-23-2012
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

Tom Anderson schrieb:
> On Wed, 22 Feb 2012, Jan Burse wrote:
>
>> If a decimal scale suits you, you could use:
>>
>> http://docs.oracle.com/javase/7/docs...igDecimal.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
>
>> Decimal scale means your numbers would be represented as:
>>
>> mantissa * 10 ^ -scale
>>
>> Bye
>>
>> Tom Anderson schrieb:
>>
>>> 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.

>


 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      02-23-2012
On Thu, 23 Feb 2012 21:16:04 +0000, Tom Anderson wrote:

>
> 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.


--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
 
Reply With Quote
 
Gene Wirchenko
Guest
Posts: n/a
 
      02-23-2012
On Thu, 23 Feb 2012 14:42:23 -0800, Lew <(E-Mail Removed)> wrote:

>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
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      02-25-2012
On Wed, 22 Feb 2012 21:39:20 +0000, Tom Anderson
<(E-Mail Removed)> wrote, quoted or indirectly quoted someone who
said :

>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.
--
Roedy Green Canadian Mind Products
http://mindprod.com
One of the most useful comments you can put in a program is
"If you change this, remember to change ?XXX? too".

 
Reply With Quote
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      02-27-2012
Robert Klemme <(E-Mail Removed)> wrote:

(snip)
>> 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


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
 
Reply With Quote
 
Arne Vajh°j
Guest
Posts: n/a
 
      02-27-2012
On 2/26/2012 7:59 PM, glen herrmannsfeldt wrote:
> Robert Klemme<(E-Mail Removed)> wrote:
>
> (snip)
>>> 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

>
> 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

 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      02-27-2012
On 27.02.2012 02:50, Arne Vajh°j wrote:
> On 2/26/2012 7:59 PM, glen herrmannsfeldt wrote:
>> Robert Klemme<(E-Mail Removed)> wrote:
>>
>> (snip)
>>>> 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

>>
>> 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.


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

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiprecision arithmetic library question. Michael Press Python 6 06-27-2008 10:40 AM
Small High-precision Arithmetic Library GCRhoads C++ 7 07-20-2007 07:40 PM
Small High-precision Arithmetic Library GCRhoads C Programming 6 07-20-2007 07:40 PM
Simple library for arithmetic expression pasring and evaluating John Doe Java 0 04-17-2005 10:03 PM
Usual Arithmetic Conversions-arithmetic expressions joshc C Programming 5 03-31-2005 02:23 AM



Advertisments