Serge D. Mechveliani wrote:
>
> On Fri, Feb 10, 2012 at 09:46:10PM +0100, Waldek Hebisch wrote:
>
> > Good to hear this. But did you notice that pSpad and
> > AFAIK sbcl READ_-FROM_-STRING are O(n^2) in length of the number?
> >
>
> I missed this!
> An improvenent:
> #str = 1 => (ord(qelt(str, i)) pretend SI) - b
> (str1, str2) := halve str -- divide by middle
> parseInt(str1)*10^(# str2) + parseInt(str2)
>
> It this of O(n*log(n)) ?
>
It looks rather like O(M(n)*log(n)). IIUC GMP multiplication
has complexity given by Shoenhage and Strassen, so in this
case you get O(n*log(n)^2*log(log(n))) -- this is probably close
to optimal. IME constants matter at least that much as exact form
of log terms, so in practice version which efficiently handles
short strings _and_ has optimal complexity would be preferable
to the above.
> > Hmm, it makes sense to add 'fromString' operation to few base
> > types. Given speed and correctness issues I think that I would
> > rather add Spad version.
>
> I hope that fromString $Integer can be cleverly implemented by linking
> to the GMP (Gnu Multi-Precision) library or such. I never looked into
> GMP, but expect that it must be all right there with
> O(of what is needed). And it needs to be only for a string of digits.
>
It is more tricky than you think. We currently support replacing
sbcl and Closure CL operations by GMP versions, so it would be
not so big extension is this case. However, we use GMP only at
user request, so GMP may be unavaliable. ECL and GCL natively
use GMP, but I am not sure if they use GMP function for converting
strings to integers. If yes then we could pass work to
READ_-FROM_-STRING (accepting some overhead). If no then we
would have to work out low level datails of making integers,
so that ECL/GCL correctly handle (in particular garbage collect)
results from GMP. In case of Clisp I think that native multiplication
is quadratic, but we do not support GMP with Clisp -- basically
I see no sense in this as it would be more work than doing it for
sbcl or Closure CL and Clisp is slow anyway.
>
> > READ_-FROM_-STRING is quite general -- it can parse arbitrarily
> > complex expression, decides about (Lisp) types etc.
>
> -> READ_-FROM_-STRING("201") $Lisp
> 201 : SExpression
> -- But my Spad program used it as Integer !
>
1) At level of representation SExpression is a supertype of Integer
(Spad has poor support for subtyping, so at Spad level SExpression
and Integer are disjoint types).
2) Intepreter has no idea what should be type of result from $Lisp
call, so it chooses the most general one (which happens to be
SExpression).
> -> READ_-FROM_-STRING("-201*(2^2+3)") $Lisp
> -201* : SExpression
> -- ?
>
You got symbol in this case. At level of representation Symbol
is a subtype of SExpression so this is OK. But using this
result as Integer without checking is not OK.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
