Without following this thread closely, why not use:
(9) -> integer PARSE_-INTEGER("111111111111111")$Lisp
(9) 111111111111111
Type: PositiveInteger
Kindly, Mark.
-----Original Message-----
From: [email protected] [mailto:[email protected]] On
Behalf Of Waldek Hebisch
Sent: Monday, 13 February 2012 8:42 PM
To: [email protected]
Subject: Re: [fricas-devel] parsing integer
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.
--
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.
