>>>>> "Andreas" == Andreas Eder <Andreas.Eder@t-online.de> writes:
Andreas> Raymond Toy writes:
>> >>>>> "Pedro" == Pedro Fortuny Ayuso <P.Fortuny@maths.qmul.ac.uk> writes:
Pedro> That would be a good idea, although IMO, primality tests are simple
Pedro> enough to require very little lisp coding, and we would avoid foreign
Pedro> function calls. If this approach looks interesting for enough people,
Pedro> I am eager to start working on this (I am trying to learn lisp by now,
Pedro> and anyway the gurus in the list are surely kind enough to correct
Pedro> my mistakes).
>>
>> While I would like to see this, I suspect that you won't be able to
>> make this run fast enough to be usable. The code will probably cause
>> so much consing that it runs slowly. A pure guess on my part.
Andreas> I don't think that it will cons to death (so to speak). At least not
Andreas> on cmucl, since python is very good at optimizing numerical code. And
Yes, cmucl can be quite good on floating-point stuff, but, bignum
arithmetic isn't particularly fast on cmucl. Clisp usually wins big
here. And the division/truncation operations are done using the
standard pencil-and-paper algorithms (I think).
Andreas> available, it will not matter for the numbers that we are likely to
Andreas> tackle. If you are really going for the raw speed, then there is no
Andreas> way around assembler, and equally important the fast fft-based
Andreas> algorithms.
I implemented a Karatsuba multiplier (in Lisp) for cmucl using
cmucl-internal functions and the cross-over point is 512 to 1024 bits
long. I was hoping the cross-over point would be lower, but that's
the best I could do. I had an FFT version once too, but I was never
sure that I got all the rounding and stuff right, so I think I gave
up. (Still have the FFT code, but probably not the bignum part of
it.)
Andreas> But prime-testing in the range of up to a few hundred digits should be
Andreas> doable in lisp. And I am willing to help as much as I can.
Likewise.
Ray