Re: largely OT: a random-number generator and bzip2

"cr88192" <cr88192@xxxxxxxxxxxxxxxxxx> writes:

> "Phil Carmody" <thefatphil_demunged@xxxxxxxxxxx> wrote in message
> news:873bnusr6e.fsf@xxxxxxxxxxxxxxxxxxxxxxx
> > "Matt Mahoney" <matmahoney@xxxxxxxxx> writes:
> >> cr88192 wrote:
> >> > x'=(x + x^2 + x^3 + x^5 + x^7)%16777213
> >
> >> Division is also slow.
> >
> > Which is why one would implement that without division.
> >
> > I probably do twenty trillion modular multiplications like
> > the above per day, and I don't use more than a few hundred
> > divisions.
> >
> curious:
> apart from, eg, power of 2 cases (and other trivial cases), what is the
> general approach for pulling off modulo without division?

Either:
1) transform into a representation where the modular reduction
can be performed by a multiplication (such as Montgomery).
2) perform the division through multiplication by a pre-computed
(sometimes scaled) reciprocal.

Using the latter permits you to parallelise use of the integer
and floating point units typically. That's what I do ~2e13 of
per day.

Phil
--
If a religion is defined to be a system of ideas that contains unprovable
statements, then Godel taught us that mathematics is not only a religion, it
is the only religion that can prove itself to be one. -- John Barrow
.

Relevant Pages

  • Re: largely OT: a random-number generator and bzip2
    ... > I probably do twenty trillion modular multiplications like ... generator that was using a table based approach. ... maybe speed was more of a concern than memory use or ... > If a religion is defined to be a system of ideas that contains unprovable ...
    (comp.compression)
  • Re: largely OT: a random-number generator and bzip2
    ... I probably do twenty trillion modular multiplications like ... If a religion is defined to be a system of ideas that contains unprovable ... -- John Barrow ... Prev by Date: ...
    (comp.compression)