From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/77 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: math argument reduction Date: Sun, 26 Jun 2011 20:04:02 +0200 Message-ID: <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 1309111463 6160 80.91.229.12 (26 Jun 2011 18:04:23 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 26 Jun 2011 18:04:23 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-161-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jun 26 20:04:19 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 1Qatgv-0007JK-1A for gllmg-musl@lo.gmane.org; Sun, 26 Jun 2011 20:04:17 +0200 Original-Received: (qmail 1417 invoked by uid 550); 26 Jun 2011 18:04:15 -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 1406 invoked from network); 26 Jun 2011 18:04:15 -0000 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Xref: news.gmane.org gmane.linux.lib.musl.general:77 Archived-At: 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 at that point it's probably not much harder to implement the standard method of argument reduction used in sun and bsd libm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.5616