Re: Arbitrary precision modulo operation - Mailing list pgsql-general

From Dann Corbit
Subject Re: Arbitrary precision modulo operation
Date
Msg-id D90A5A6C612A39408103E6ECDD77B829408D6E@voyager.corporate.connx.com
Whole thread Raw
In response to Arbitrary precision modulo operation  (Chadwick Boggs <chadwickboggs@yahoo.com>)
List pgsql-general
I do not know how division is performed in numeric quantities for
PostgreSQL.

However, if the algorithm is being revised, here is a possible outline:

1.  Convert to double and perform the division to get an estimate
2.  Use Newton's method for division, starting at 30 digits and doubling
the digits for each iteration.
3.  Stop when you have reached 50% excess digits or so
4.  Round to the correct value.

Since the computations use smaller significant digits until the last
iteration, there is typically a large savings compared to performing all
calculations in full precision.

So, if the target is 70 digits you will have:

~15 digits precision after the double precision floating point divide
30 digits after one iteration
60 digits after two iterations
120 digits after three iterations

Then round to the correct length.

See:
http://www.azillionmonkeys.com/qed/adiv.html

For a short discussion of Newton's method for division.

pgsql-general by date:

Previous
From: "Dann Corbit"
Date:
Subject: Re: Arbitrary precision modulo operation
Next
From: "Dann Corbit"
Date:
Subject: Re: Arbitrary precision modulo operation