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:
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 :-)
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.

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


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
            loops = 10000
        t = gp.eval("""n = %s; gettime(); for (i=1,%s,factor(n)); gettime()""" % (n,loops))
        t = 1000 * RDF(t)/loops
        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

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")"factortiming.png")