Jeroen Demeyer on Thu, 08 May 2014 23:11:22 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Factoring small numbers |
On 2014-05-08 20:49, Karim Belabas wrote:
GAP sometimes fails to factor a number, this problem starts to appear at around 58 bits. So I'm restricting my benchmark to 56 bits, with randomly chosen numbers.Benchmarking the factorization of a single small integer is not very useful. Can you try a set of about 1000 "random" integers of the same size ? (and share your benchmark code :-)
Attached you can see timings for factoring lots of numbers, every number is factored once with PARI and once with GAP. The x-axis is the 2-log of the number, the y-axis (log-scale) the number of microseconds for the factorization.
Note that PARI is usually faster, but it has outliers in both directions, while GAP is more constant.
Hardware: Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz Jeroen.
Attachment:
factortiming.png
Description: PNG image
LPARI = [] LGAP = [] for d in [3..56]: print d s = 2^(d-1) for i in range(20): n = s + ZZ.random_element(s) m = RDF(n).log(2) if d < 20: loops = 100000 else: loops = 10000 t = gp.eval("""n = %s; gettime(); for (i=1,%s,factor(n)); gettime()""" % (n,loops)) t = 1000 * RDF(t)/loops LPARI.append((m,t)) t = gap.eval("""n := %s;; t0 := Runtime();; for i in [1..%s] do FactorsInt(n); od; Runtime() - t0; """ % (n,loops)) t = 1000 * RDF(t)/loops LGAP.append((m,t)) P = list_plot_semilogy(LPARI, color=Color(0,1,0), legend_label="PARI 2.7.1") P += list_plot_semilogy(LGAP, color=Color(0.5,0,1), legend_label="GAP 4.7.4") P.save("factortiming.png")