Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Phil's max_min_norm

Expand Messages
  • Phil Carmody
    ... 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

      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!
    Your message has been successfully submitted and would be delivered to recipients shortly.