Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20110626180402.GX27421@port70.net>
Date: Sun, 26 Jun 2011 20:04:02 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: math argument reduction

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

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.