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 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.
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).
The test function
(1) forms 10^5 digit strings of length l,
(2) parses each to Integer by read str :: Integer
(`read' of the Haskell library),
(3) takes the remainder by 7 (in order not to have large sums in
the end),
(4) sums these remainders.
The Haskell code:
--------------------------------------------------------------------
main = putStr $ concat
["l = ", shows l ", number of strings = ", shows l0Exp
", p = ", shows p "\nresSum = ", shows resSum "\n"
]
where
m = 128 :: Int -- edit this multiplicity
-- Int <--> SingleInteger
digits = (if m == 1 then id else reverse)
['0' .. '9'] :: [Char]
l0 = 5 :: Int
l0Exp = (10 :: Int)^l0
l = l0 * m
strs :: Int -> [String] -- all digit strings of length n
strs n = if n == 0 then [""]
else
[d : ds | ds <- strs (pred n), d <- digits]
strings = strs l
segm = take l0Exp strings -- length segm is always 10^l0
p = 7
parseReduce str =
fromInteger (rem (read str :: Integer) p) :: Int
--------
resSum = sum [parseReduce str | str <- segm]
-- testPairs = [(str, read str :: Integer) | str <- strings]
--------------------------------------------------------------------
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.
