[Haskell-cafe] Fast Integer Input

[200901104 at daiict.ac.in]

> From: "Daniel Fischer" <daniel.is.fischer at web.de>
> To: 200901104 at 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.