fork(2) download
copy 
  1. import math
  2. from decimal import Decimal
  3. from itertools import islice
  4.  
  5. def blhsing(numbers):
  6.     return Decimal(math.gcd(*numbers)).normalize().as_tuple().exponent
  7.  
  8. def batched(iterable, n):
  9.     "Batch data into tuples of length n. The last batch may be shorter."
  10.     # batched('ABCDEFG', 3) --> ABC DEF G
  11.     if n < 1:
  12.         raise ValueError('n must be at least one')
  13.     it = iter(iterable)
  14.     while batch := tuple(islice(it, n)):
  15.         yield batch
  16.  
  17. def Kelly(numbers):
  18.     E = float('inf')
  19.     for e in map(blhsing, batched(numbers, 100)):
  20.         if e < E:
  21.             E = e
  22.             if not E:
  23.                 return 0
  24.     return E
  25.  
  26. funcs = blhsing, Kelly
  27.  
  28. from random import randrange
  29. from timeit import timeit, default_timer as timer
  30. from statistics import mean, fmean, stdev
  31. import sys
  32.  
  33. d = [randrange(100) * 10 ** randrange(100) for i in range(10000)]
  34.  
  35. times = {f: [] for f in funcs}
  36. def stats(f):
  37.     ts = [t * 1e3 for t in sorted(times[f])[:5]]
  38.     return f'{mean(ts):6.3f} ± {stdev(ts):4.3f} ms '
  39. for _ in range(50):
  40.     for f in funcs:
  41.         t0 = timer()
  42.         f(d)
  43.         times[f].append(timer() - t0)
  44. for f in sorted(funcs, key=stats):
  45.     print(stats(f), f.__name__)
  46.  
  47. print('\nPython:', sys.version)
Success #stdin #stdout 0.07s 11368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 0.020 ± 0.000 ms  Kelly
 0.157 ± 0.000 ms  blhsing

Python: 3.9.5 (default, Nov 18 2021, 16:00:48) 
[GCC 10.3.0]
https://ideone.com/t1xKm1
language:
Python 3 (python  3.12)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!