## clisp-list

 Re: [clisp-list] very long floats From: Bruno Haible - 2006-11-16 15:38:18 ```> for approximation of Pi with the so-called AGM-algorithm, I would like > to > use floats as long as possible. However, I run in difficulties: > > (setf (ext::long-float-digits) 10000000) On 32-bit 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 multi-million 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 64-bit 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/ ```
 Re: [clisp-list] very long floats From: Bruno Haible - 2006-11-17 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=F6nhage-Strassen 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_ built-in numbers of the CL implementation, but it would be usable by CA systems like Axiom or Maxima in a portable way. Bruno ```
 Re: [clisp-list] very long floats From: Sam Steingold - 2006-11-17 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 variable-length floats because they are not available in SBCL and threads in SBCL because they are not available in CLISP. S. ```
 Re: [clisp-list] very long floats From: Bruno Haible - 2006-11-17 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 2-3 months of work (full-time). Bruno ```
 Re: [clisp-list] very long floats From: Nicolas Neuss - 2006-11-18 11:32:25 ```First, I want to thank you for your detailed explanation in your other post. Bruno Haible 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 2-3 > months of work (full-time). 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 well-integrated numeric tower using libraries like CLN? Nicolas ```
 Re: [clisp-list] very long floats From: Nicolas Neuss - 2006-11-16 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 writes: > > for approximation of Pi with the so-called AGM-algorithm, I would like > > to > > use floats as long as possible. However, I run in difficulties: > > > > (setf (ext::long-float-digits) 10000000) > > On 32-bit 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 multi-million 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 64-bit 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/ ```