Talk:Barrett reduction

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Circular reasoning??[edit]

Im a bit confused by the explanation of the algorithm. There doesnt seem to be any explanation as to how the values for k and m are calculated. Say, by computer algorithm, for example. A human could reason it, probably. The value of m is defined as the floor of a power of 2 divided by n. But I thought the point of the algorithm was to avoid division by n. There seems to be no way to know 1/n or approximate s ahead of time. I thought this because I was referred to this algorithm by another source which stated that Barrett reduction was a fast way of finding a modulus that circumvents the need for division. They were talking about integer division, granted, but integer division is faster and easier than floating point division, which itself is based on integer operations. What am I missing here?

Possible article source[edit]

This page [1] looks like it might be a good source of information on this algorithm. CountingPine (talk) 21:36, 9 July 2011 (UTC)[reply]

Think of n as representing the fixed-point number n 2^{-k}[edit]

Why not introduce a new variable for n? This makes the algorithm less clear. Or should n be m?