--- 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