From: "Daniel Fischer" To: 200901104@daiict.ac.in Sent: Monday, August 23, 2010 11:14:55 PM Subject: Re: [Haskell-cafe] Fast Integer Input On Monday 23 August 2010 17:06:02 you wrote:

...

...

...

Does the length of those numbers happen to be fixed? It they are all exactly 13000 decimals then it should be possible to create a more optimised parser.

Well actually they can have any number of digits less than 13000. But the only post processing of the numbers is calculating the binary logarithm of the number. Does that help?

That, time limit, SPOJ? (If so, which one?)

Yes. The time limit is 4 sec. The question has more parts than just this though. http://www.spoj.pl/problems/VGCD/. (Note: Spoiler at the bottom)

You can calculate the binary logarithm to high accuracy without parsing the entire number. Just parse the first k digits and get the count of digits, from that the logarithm is quickly calculated.

I will try this out.

...

...

...

It would also help if you could post a working example of your code and some test data somewhere so people can run it and test if for themselves.

I have a slow Internet connection. So I will attach the script I used to generate the cases instead.(Note: It will take a few minutes to complete)

Spoiler: The given numbers are Fibonacci. Wikipedia has said some interesting properties, which makes the question into finding where the number is in the Fibonacci sequence.