Re: Factoring small numbers

[Jeroen Demeyer <jdemeyer@cage.ugent.be>]

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

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")