From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/78 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: math argument reduction Date: Sun, 26 Jun 2011 14:33:44 -0400 Message-ID: <20110626183344.GX12592@brightrain.aerifal.cx> References: <20110626180402.GX27421@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1309113642 17529 80.91.229.12 (26 Jun 2011 18:40:42 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 26 Jun 2011 18:40:42 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-162-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jun 26 20:40:39 2011 Return-path: Envelope-to: gllmg-musl@lo.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by lo.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1QauG6-0003xm-Ba for gllmg-musl@lo.gmane.org; Sun, 26 Jun 2011 20:40:38 +0200 Original-Received: (qmail 16075 invoked by uid 550); 26 Jun 2011 18:40:36 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 16067 invoked from network); 26 Jun 2011 18:40:36 -0000 Content-Disposition: inline In-Reply-To: <20110626180402.GX27421@port70.net> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:78 Archived-At: On Sun, Jun 26, 2011 at 08:04:02PM +0200, Szabolcs Nagy wrote: > dalias, i thought about the simple argument reduction method > you proposed on irc, imho it won't be that good > > the task is to calculate X mod M, so to get the fractional part of > x = X/M > you said you would treat X as a sum (of 2^n terms) let's say > X = A+B > and assume we have precalculated a=A/M and b=B/M in a table, then > x = a+b > is easy to get > > but it well might be that the form of a+b is > > [..]1011 . 0000000000000001101011[..] > > so the fractional part has many leading zeros > (it can be as many as 61) so you need to store a and b > with large precision to get good floating point representation > of the fractional part > (53 + 61 bits precision + some extra bits for rounding) > > so you need to store and do arithmetics with 120bit fixpoint values I think you misunderstood my algorithm. You never need to compute X/M. It's A%M and B%M, not A/M and B/M, which you have precalculated in your tables. And therefore, (A+B)%M is congruent to A%M + B%M. In general it could be outside the interval [0,M), but not by so much that it's hard to get a good answer. Rich