On Fri, Feb 10, 2012 at 09:46:10PM +0100, Waldek Hebisch wrote:
> Serge D. Mechveliani wrote:
> >
> > To my request on fast parsing of Integer Waldek Hebish writes
> >
> > > If you know that the string contains correct integer, then
> > > READ_-FROM_-STRING(s)$Lisp will work. AFAIK there is no Spad level
> > > operation to do directly parse integer.
>>> [..]
> If you have newest trunk the following version should be faster
> (on 1.1.5 it may be slower):
>
> import Character
> zero := ord(char("0")) pretend SI
>
> parseInt(str : String) : I ==
> b := zero
> l := # str pretend SI
> s := 0 :: I
> ten := 10 :: I
> for i in (1 .. l) repeat
> dNum := (ord(qelt(str, i)) pretend SI) - b
> s := (ten*s) + dNum
> s
> [..]
> sbcl READ_-FROM_-STRING is written in Lisp. I am not sure about
> Clisp, probably in C.
>
> > As to me, both pSpad and pLisp are safficiently fast.
>
> 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)) ?
> 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.
> 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 !
-> READ_-FROM_-STRING("-201*(2^2+3)") $Lisp
-201* : SExpression
-- ?
And if it is O(n^2), then it is not for fast parsing of integer.
Regards,
------
Sergei
[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.
