On Fri, 23 Feb 2018 06:07:44 +1100, Chris Angelico wrote: > On Fri, Feb 23, 2018 at 3:00 AM, Steven D'Aprano > <steve+comp.lang.pyt...@pearwood.info> wrote: >> On Thu, 22 Feb 2018 12:03:09 +0000, bartc wrote: >>> Here's another speed-up I found myself, although it was only 50 times >>> faster, not 17,000: just write the code in C, and call it via >>> os.system("fib.exe"). >> >> Did you include the time taken to capture the text output from stdout, >> parse it, and convert to an int? > > Relatively trivial compared to the overhead of invoking a subprocess > THROUGH A SHELL. On Windows, that has to invoke cmd.exe; on Unix-like > systems, most likely /bin/sh. And then that has to search the system > path (maybe that doesn't happen on his Windows system, as presumably > it's finding the executable on the cwd check). That's file system > operations, and a lot of them. > >> Did your C code support numbers greater than 2**64? My fibonacci >> function can calculate the 10,000th Fibonacci number in a blink of the >> eye: >> >> py> fibi(10000) >> 336447648764317832666216120051075...976171121233066073310059947366875 >> >> Output truncated for brevity, it is a 2090-digit number. >> >> Admittedly it did take about a minute and a half to generate all 208988 >> digits of the one millionth Fibonacci number, but the performance is >> fast enough for my needs. > > Yeah, but if you stick that into a variable, you can separately time the > calculation from the stringification. Using the exact code from the > page: > > def fib_seq(n): > if n < 2: > return n > a,b = 1,0 for i in range(n-1): > a,b = a+b,a > return a > >>>> time.time(); x = fib_seq(1000000); time.time() > 1519325946.7880309 1519325953.773382 > > That's seven seconds to calculate the number. How big a number is it? > >>>> x.bit_length() > 694241 >>>> math.log10(x) > 208987.29076497658 > > Both take effectively zero time. Dividing that number by 10 that many > times is what takes all the processing. (Stringifying a number basically > consists of div-mod to trim off the last digit, keep going until you run > out of number. Lots of division.) > > So actually calculating the millionth Fibonacci number can be done > fairly quickly; figuring out its first digits would be hard, but we > don't actually need that. Though we could probably get a decent > estimate: > >>>> log = math.log10(x) >>>> print(10**(log - int(log)), "e +", int(log)) > 1.9532821287892859 e + 208987 > > I wouldn't trust all of those digits, but that's a fast way to get an > idea of the scale of a number. Doing that rather than printing the whole > number means you actually see the performance of *calculation*.
I realize that this thread is about benchmarking and not really about generating fibonacci numbers, but I hope nobody is using this code to generate them on a 'production' basis, Fibonacci numbers, any linearly recursive sequence for that matter, can be generated in log time. GP/Pari on my Intel I7 computes fibonacci(100000) in less than 1 ms, fibonacci(1000000) in 5ms, fibonacci(10000000) in 59 ms and finally fibonacci(100000000) in 733 ms. This would obviously be slower in Python but by a constant factor. Best regards, Jack Fearnley > > ChrisA -- https://mail.python.org/mailman/listinfo/python-list