From: Bruno Haible <bruno@cl...>  20061116 15:38:18

> for approximation of Pi with the socalled AGMalgorithm, I would like > to > use floats as long as possible. However, I run in difficulties: > > (setf (ext::longfloatdigits) 10000000) On 32bit machines, CLISP bignums have a limited length (ca. 16 MB or so). Also, the algorithm for multiplication in CLISP is O(n^1.69) and for transcendental functions O(n^2.2), where n is the length of the numbers involved. This is suitable for all kinds of general computations up to ca. 10000 or 100000 digits, but not good for multimillion digit stuff. The CLISP bignums have been rewritten as a C++ library, called CLN [1], and there the length is not practically limited, and the multiplication is O(n^1.3). On 64bit machines, you can now even use numbers larger than 4 GB. Some computation records have been established in the past using CLN. Bruno [1] http://www.ginac.de/CLN/ 
From: Bruno Haible <bruno@cl...>  20061117 14:41:41

> 1. I am no expert in large integer computations, but as much as I remember > fast FFT multiplication is O(n log n). Up to which number of digits c= an > CLN compete with such approaches? =46ast FFT multiplication is, as far as I recall, O(n log n (log log n)^e), e =3D 1 or 2. CLN implements fast FFT; there is no question whether it "competes" with it. This O(n log n (log log n)^e) formula is the theory. What I measured in practice is O(n^1.3). When you look where the log log n factor comes from, it is because in the Sch=F6nhageStrassen algorithm you do multiplications on integers of size sqrt(n), which you _assume_ obey the same formula. But that's not true in practice: sqrt(n) is below the threshold where FFT wins against Karatsuba. And then you've got to consider the Karatsuba complexity, hence sqrt(n) * (sqrt(n))^1.7 ... > 2. Are there any plans of incorporating improved longfloats (e.g. CLN) in= to > CLISP? Or is this too much work for too little interest? It is too much work for too few users. Also, many CL users want portability, therefore they would refrain from relying on a feature that they don't have in, say, SBCL. The right approach for using CLN from CL would IMO be through an FFI/UFFI/CFFI/... interface. Then the numbers would not appear as _the_ builtin numbers of the CL implementation, but it would be usable by CA systems like Axiom or Maxima in a portable way. Bruno 
From: Sam Steingold <sds@gn...>  20061117 14:56:57

Bruno Haible wrote: >> 2. Are there any plans of incorporating improved longfloats (e.g. CLN) into >> CLISP? Or is this too much work for too little interest? > > It is too much work for too few users. IOW, PTC. > Also, many CL users want portability, > therefore they would refrain from relying on a feature that they don't have > in, say, SBCL. this argument is absurd. if it were true, people would not use CLISP variablelength floats because they are not available in SBCL and threads in SBCL because they are not available in CLISP. S. 
From: Bruno Haible <bruno@cl...>  20061117 20:03:38

Sam wrote: > >> 2. Are there any plans of incorporating improved longfloats (e.g. CLN) into > >> CLISP? Or is this too much work for too little interest? > > > > It is too much work for too few users. > > IOW, PTC. What does "PTC" mean? I was trying to say that there are only ~100 people in the world who are seriously interested in multimullion digit computations, and less than a handful of them are using Common Lisp and have big problems using C++ instead. Porting CLN's multiplication routine back to clisp is probably 2 weeks of work, porting the transcendental functions routines is probably 23 months of work (fulltime). Bruno 
From: Nicolas Neuss <neuss@ma...>  20061118 11:32:25

First, I want to thank you for your detailed explanation in your other post. Bruno Haible <bruno@...> writes: > Sam wrote: > > >> 2. Are there any plans of incorporating improved longfloats (e.g. CLN) into > > >> CLISP? Or is this too much work for too little interest? > > > > > > It is too much work for too few users. > > > > IOW, PTC. > > What does "PTC" mean? I have found "patches thoughtfully considered", which was probably directed at myself:) > I was trying to say that there are only ~100 people in the world who are > seriously interested in multimullion digit computations, and less than a > handful of them are using Common Lisp and have big problems using C++ > instead. That's, of course, also the problem in my case  I am not really needing this stuff (who needs pi with millions of digits?). It would have been nice, if I could have done such calculations with CLISP for a seminar on pi calculations, but this can hardly be considered as a serious purpose. > Porting CLN's multiplication routine back to clisp is probably 2 weeks of > work, porting the transcendental functions routines is probably 23 > months of work (fulltime). I agree with your previous post: it would probably be more useful to have a lesser interface to CLN which works for most Lisps. On the other hand, the integration in CLISP is a proof of concept that long floats fit already well in the ANSI CL standard (do we see CLISP's influence here?). Maybe it would be an interesting research topic to define an interface within Lisp/Scheme implementations which provides portably a wellintegrated numeric tower using libraries like CLN? Nicolas 
From: Nicolas Neuss <neuss@ma...>  20061116 17:27:05

Hello Bruno, thank you for the answer, although it ruins my intentions to redo more recent Pi calculations using CL/CLISP. May I ask two further questions: 1. I am no expert in large integer computations, but as much as I remember fast FFT multiplication is O(n log n). Up to which number of digits can CLN compete with such approaches? 2. Are there any plans of incorporating improved longfloats (e.g. CLN) into CLISP? Or is this too much work for too little interest? Thank you, Nicolas Bruno Haible <bruno@...> writes: > > for approximation of Pi with the socalled AGMalgorithm, I would like > > to > > use floats as long as possible. However, I run in difficulties: > > > > (setf (ext::longfloatdigits) 10000000) > > On 32bit machines, CLISP bignums have a limited length (ca. 16 MB or so). > Also, the algorithm for multiplication in CLISP is O(n^1.69) and for > transcendental functions O(n^2.2), where n is the length of the numbers > involved. > > This is suitable for all kinds of general computations up to ca. 10000 or > 100000 digits, but not good for multimillion digit stuff. > > The CLISP bignums have been rewritten as a C++ library, called CLN [1], > and there the length is not practically limited, and the multiplication > is O(n^1.3). On 64bit machines, you can now even use numbers larger than > 4 GB. Some computation records have been established in the past using CLN. > > Bruno > > [1] http://www.ginac.de/CLN/ 