Serge D. Mechveliani wrote:
>
> 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.
This method is implemented in GMP. For small n other methods are
faster, but above few thousends digits GMP uses Shoenhage-Strassen
method.
> 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).
GMP uses asymptotically fast method. However, in practical ranges
it is more or less questions of constants -- at about millon of digits
gain is of order 20 compared to next best method. On modern
hardware good low level implementation frequently is 100 times
faster than a poor one. So asymptitially fast method which
is amenable to low level improvements wins, but asymptitially fast
method which interferes with low level improvements frequently
looses.
BTW: I have now commited new package containing a function
for parsing integers. When using sbcl it is much faster than
methods builtin into sbcl. When using GMP with sbcl it is
asymptotically fast, and also quite fast for small numbers.
--
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.
