Re: [PrimeNumbers] Phil's max_min_norm
- --- Marcel Martin <znz@...> wrote:
> Phil,For those that aren't familiar with Barrett reduction, it's
> >I don't think it's _my_ anything. In Z[i] it should give you
> >the same answer as the algorithm Marcel posted.
> >Marcel's is a 'barrett reduction' to my 'high school long
> >in some ways, did anyone else notice that?
- 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 ofHere C(B) is the scaled inverse, and 'whole' parts come in chunks of
> 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)
Of course, Barrett has a 'and correct if we've suffered rounding
errors' stage, which won't happen here as every operation is exact.
"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!