> From: "Daniel Fischer" <[email protected]> > To: [email protected] > 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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
