Expand Messages
• ... For those that aren t familiar with Barrett reduction, it s - multiply by a scaled inverse - throw away the whole part - multipy by the value you were
Message 1 of 3 , May 9 11:40 PM
--- Marcel Martin <znz@...> wrote:
> Phil,
>
> >I don't think it's _my_ anything. In Z[i] it should give you
> exactly
> >the same answer as the algorithm Marcel posted.
> >Marcel's is a 'barrett reduction' to my 'high school long
> division'
> >in some ways, did anyone else notice that?

For those that aren't familiar with Barrett reduction, it's
- multiply by a scaled inverse
- throw away the 'whole' part
- multipy by the value you were reducing to.
- scale down by a scale factor (a bitshift traditionally)

> Remainder A mod B. A and B are in Z[i]. C(B) is the conjugate of
> B.
> Let u + vi = A * C(B)
> x := u rem N(B)
> y := v rem N(B)
> Let R = x + yi
> R := R * B / N(B)

Here C(B) is the scaled inverse, and 'whole' parts come in chunks of
N(B).

Of course, Barrett has a 'and correct if we've suffered rounding
errors' stage, which won't happen here as every operation is exact.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! Shopping - Mother's Day is May 12th!
http://shopping.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.