Please, excuse me for my silly errors about O(n*log(n)).
Because parsing from a decimal string is actually
conversion of an natural number from the decimal system to binary
-- a well-known problem. Donald Knuth writes in
"The Art of Programming" (1969, Addison-Wesley), 4.4, Exercise 14
about the method of the cost
O( M(n)*log(n) ),
where M(n) is the cost of multiplication of binary numbers of n binary
digits. This leads to
O( n*log(n)^2*(log(log(n))) ) < O( n*(log(n))^3 )
of which Waldek Hebish wrote recently.
It is still essentiall less than n^2.
But the method for M may be rather subtle, and may occur efficient only
for too large n, I do not know (Shoenhage, Strassen ...).
May be it is not practicable for a real software.
The further improved test for ghc-4.7.1 shows that for larger l
it starts something like l^2.
I suspect that all our libraries use the methods which are still
asymptotically O(n^2).
Regards,
------
Sergei
[email protected]
On Tue, Feb 14, 2012 at 11:35:25PM +0400, Serge D. Mechveliani wrote:
> On Mon, Feb 13, 2012 at 08:42:09PM +0100, Waldek Hebisch wrote:
> > 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 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.
>
> Here is the benchmark of Glasgow Haskell (ghc-7.4.1), 1 GHz machine:
>
> l time [sec]
> 40: 4.8 sec (l = 40, number of strings = 100.000, p = 7)
> 80: 9.3
> 160: 18.8
> 320: 42.4 resSum = 300000
> 460: 103.0 resSum = 299999
>
> It looks like l*log(l).
> [..]
--
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.
