Re: Prime numbers

"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> writes:
Phil Carmody wrote:
"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> writes:

50% of my cyclotomic sieve is spent in a Cantor Zassenhaus
routine. I remember you saying that CZ was the bee's knees
for similar situations in the past, but my implementation
must truly suck. I wrote it many years ago, and it would
take a while to even work out what I was doing again, so
perhaps an entirely new approach, purloined from a hotshot
coder like yourself, might be better :-)

If you send your snail maill address, I could send some CZ code
for 32-bit numbers. It would not be a lot of work to modify it for
64-bits on a platform that can handle 64-bit ints.

Snail mail as in Ristiaallokonkatu 4 F 131, Espoo 02320, Finland?

And if you are working mod k*2^n + 1, the modular reductions
can be made very fast.

The technique I use has fixed-time modular reductions, no matter
what the form. I'm using the fairly common 'x as an integer,
1/p as a float' technique.
xy%p ~= lowbits(x*y) - lowbits(int(x'*y'*1/p')*p)
where the "'" operands are FP.
Slows down when FP<->Int conversions are slow (e.g. PPC), but
otherwise makes good use of both int and FP cores.
You get different behaviour depending on how int() works (which
is not always a C cast, so it depends on the FPU rounding mode) -
But often {-p/2, +p/2} is prefered over {0, p-1} .

I'll have a look at my code today, tidy it up a bit perhaps,
make a minor optimisation which I've spotted is possible,
and put it on the table; perhaps I've missed something.

I don't think the maths primitives can be made much faster
without hitting asm, so perhaps it's my loop termination/repetition
conditions that are screwed, and I'm doing too much unnecessary
work.

Here's hoping I have no 'real' work to do today...

Thanks,
Phil
--
The man who is always worrying about whether or not his soul would be
damned generally has a soul that isn't worth a damn.
-- Oliver Wendell Holmes, Sr. (1809-1894), American physician and writer
.

Relevant Pages

  • Re: All programs are undefined, Re: Why this works???
    ... terms of the capabilities of a particular machine about whose details ISO ... void printat(const char *s, int x, int y, int bg, int fg) ... If this technique were not well-defined under the above circumstances, ... these programs were able to rely on the well-definedness of this technique ...
    (comp.lang.c)
  • Re: code portability
    ... int const *p; ... int Func() { ... I would still be able to read it, I know because I have had to, but it slows most people down. ... Although the fact that most people posting an opinion seem to think your coding style is less readable might give you a hint. ...
    (comp.lang.c)
  • Re: printf() and void *
    ... I'm a little unclear on the point you're making here. ... int main ... Right - the technique is portable, ... But what have we actually created, in what we might call absolute terms? ...
    (comp.lang.c)
  • Re: Attempting to form a thread
    ... soul helps. ... I like Buddhism. ... Or the "urp does illiterate hippie" kinda way? ... it int he moment" is, like, Mu, man. ...
    (uk.religion.pagan)
  • Re: Problems linking a BCB-DLL (.lib) under MSVC
    ... that the opposite way was quiet easy by simply using ... one single IMPLIB command! ... // tried another return value (int) here: ... > stub-generating technique should always work, ...
    (microsoft.public.dotnet.languages.vc)