Skip site navigation (1) Skip section navigation (2)

Re: Arbitrary precision modulo operation

From: "Dann Corbit" <DCorbit(at)connx(dot)com>
To: "Dann Corbit" <DCorbit(at)connx(dot)com>,"Bruno Wolff III" <bruno(at)wolff(dot)to>, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "Paul Tillotson" <pntil(at)shentel(dot)net>,<pgsql-general(at)postgresql(dot)org>
Subject: Re: Arbitrary precision modulo operation
Date: 2004-04-28 21:14:05
Message-ID: D90A5A6C612A39408103E6ECDD77B829408D6E@voyager.corporate.connx.com (view raw or flat)
Thread:
Lists: 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

Next:From: Chris BrowneDate: 2004-04-28 21:58:24
Subject: Re: Postgre and Web Request
Previous:From: Dann CorbitDate: 2004-04-28 21:02:57
Subject: Re: Arbitrary precision modulo operation

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group