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