Re: [Haskell-cafe] Fast Integer Input
> From: "Daniel Fischer" > To: 200901...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
2010/8/23 Bertram Felgenhauer : > Serguey Zefirov wrote: > The timings seem about right. Thank you for letting me know about divide-and-conquer variant. But I am still amuzed that producing 1200 words of data from 13Kbytes of text took those little 200 cycles of CPU. This is quite interesting and I think I should investigate that later. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
Serguey Zefirov wrote: > 2010/8/23 <200901...@daiict.ac.in>: > > This function takes 1.8 seconds to > > convert 2000 integers of length 10^13000. I need it to be smaller that > > 0.5 sec. Is it possible? > > 2000 integers of magnitude 10^13000 equals to about 26 MBytes of data > (2000 numbers each 13000 digits long). Rounding 1.8 seconds to two > seconds we conclude that you proceed with speed about 13MBytes per > second. Assuming you have CPU clock frequency near 2.6GHz, you > performing about 200 clock cycles per input digit. > > 10^13000 roughly equal to 2^39000. Or (2^32)^1219 - 1219 32-bit words > of representation. So you're doing some last nextN = > (n*10)+currentDigit conversion operations in less that one clock cycle > per word. You can do better than calculating (n*10 + d) repeatedly, using a divide and conquer scheme, which is in fact implemented in ByteString's readInteger: ((a*10 + b) * 100 + (c*10 + d)) * 1 + ... This helps because now we're multiplying numbers of roughly equal size, which using FFT and related methods, as gmp uses, can be sped up immensely, beating the quadratic complexity that you get with the naive approach. The timings seem about right. HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
>>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? >>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)# -*- coding: utf-8 -*- import random fibs = [0]*60001 fibs[1] = 1 for i in xrange(2, 60001): fibs[i] = fibs[i-1] + fibs[i-2] for _ in xrange(2000): i = random.randint(58000, 6) print fibs[i] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
2010/8/23 <200901...@daiict.ac.in>: > This function takes 1.8 seconds to > convert 2000 integers of length 10^13000. I need it to be smaller that > 0.5 sec. Is it possible? 2000 integers of magnitude 10^13000 equals to about 26 MBytes of data (2000 numbers each 13000 digits long). Rounding 1.8 seconds to two seconds we conclude that you proceed with speed about 13MBytes per second. Assuming you have CPU clock frequency near 2.6GHz, you performing about 200 clock cycles per input digit. 10^13000 roughly equal to 2^39000. Or (2^32)^1219 - 1219 32-bit words of representation. So you're doing some last nextN = (n*10)+currentDigit conversion operations in less that one clock cycle per word. Either I err'd in my math, or you're performing better than most of us could expect. Maybe you are off in your 10^13000 by an order of magnitude. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fast Integer Input
I need a function which has fast conversion from Bytestring to Integer. I am currently using this: import qualified Data.ByteString.Lazy.Char8 as BS readInteger :: BS.ByteString -> Integer readInteger x = case BS.readInteger x of Just (i,_) -> i Are there faster implementations? This function takes 1.8 seconds to convert 2000 integers of length 10^13000. I need it to be smaller that 0.5 sec. Is it possible? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
