NZEC in MUL (fast multiplication)

[acker_sof]

I'm having the same problem as the poster of this thread: viewtopic.php?f=20&t=5455
i.e. my solution works locally but get a runtime error from SPOJ.

Here's my source code:

thing = raw_input().split()
n = eval(thing[0])
del thing[0]
thing.reverse()
while (n > 0):
   print eval(thing.pop() + '*' + thing.pop())
   n -= 1

Any ideas?

[numerix]

First: Your code doesn't work at all, because it does not handle the input correctly.
Your code only reads the first line of input.

Second: Forget eval(). It is too slow. Convertion can be done by int() better and faster.

Third: You've chosen the wrong problem, if you want to solve it with python.
Python is not fast enough, even though the Karatsuba-multiplication is implemented.

[acker_sof]

I knew a python script wouldn't be able to execute in time with the large numbers used for input. I mostly did it for fun just to see how long it would take to execute but apparently SPOJ doesn't show you the execution time when a TLE occurs. Oh well.

As for the input not being fully read, I don't know why I assumed it would be input all at once, when I was writing the code at 3 or 4 AM the other day I was just pasting the entire sample input from the problem into the console. Not really sure why I thought this was a good idea.

Oh well, I rewrote it to have a less stupid input method but apparently there's no way to see how long a TLE-ing program took to run (is there?)

[numerix]

Oh well, I rewrote it to have a less stupid input method but apparently there's no way to see how long a TLE-ing program took to run (is there?)

No. But you can execute only a part of your programm (e.g. only the input and convertion to int) and then terminate. If that is within the time limit you can see, how long it takes till you get WA.

According to the problem: Search for it in the forum - you'll get usefull hints about the real bottleneck of that problem (if you want to solve it in python). And you should have a look at the TMUL problemset in the tutorial section. I have no idea, how they did it, but there are a few AC python solutions.

[numerix]

I have no idea, how they did it, but there are a few AC python solutions.

I still don't know, how they did it, but I know, how I did it.
I spent some hours on it, experimenting with random testdata and optimizing at several ends and
now I've the fastest python solution at the moment (about 3.5 s for TMUL).

The time limit for MUL is somewhat stricter (2 s for - I suppose - the same testcases) and I'm quite sure, that
there will be no way to do it with python within that 2 s. Perhaps there can be done some minor improvements to get it a little bit faster, but not so fast.

[MAK_sof]

@numerix:
I am very curious as to what those optimizations are. Can you please share some of those techniques to help all Python users here? I'm sure we will be able to use them in other problems as well.

I had tried a few small I/O optimizations, but those still got me TLE, even with psyco.

[numerix]

Do some profiling and find out, where the bottle-neck is. A simple example that can be used for TMUL:

from time import time
size = 1000 # change it to 10000
print "size", size
line = "1234567890"*size+" "+"1234567890"*size
t0 = time()
s, t = line.split()
print "split", time()-t0
t0 = time()
a, b = int(s), int(t)
print "int  ",time()-t0
t0 = time()
c = a * b
print "mul  ", time()-t0
t0 = time()
out = str(c)
print "str  ", time()-t0
print "len  ", len(out)

On my (very old) machine the results are as follows:

size 1000
split 0.000113964080811
int   0.102551221848
mul   0.0254321098328
str   0.422478914261
len   19999

size 10000
split 0.0239429473877
int   4.40381789207
mul   0.475347995758
str   46.4313352108
len   199999

That was my starting point.

You should be aware that any number that shall be given out, has to be converted to a string (at least I know no other technique).
Of course it is not necessary to do it explicitly - as I did in the example -, but if you don't, it is done implicitly. So, avoiding an explicit conversion to string and using "print c" instead does'nt help.

[MAK_sof]

Thank you.
Although no obvious way of eliminating or at least reducing the number of str and/or int calls come to mind, you have provided a very good starting point.

[numerix]

Although no obvious way of eliminating or at least reducing the number of str and/or int calls come to mind,

No, you can't reduce the number of str() or int() calls - it has to be done.

Compare the runtimes of the first and the second example: The length of the output string is multiplied by 10, but the time needed for convertion from int to str is about 100 times as long! So, convertion of smaller integers is much "faster" than convertion of large integers ...

[MAK_sof]

I see what you are driving at. Thanks!