[Octave-bug-tracker] [bug #61129] Performance of factor(). Proposed patch attached.

[anonymous]

Follow-up Comment #4, bug #61129 (project octave):

Patch1 from comment #1 is more performant than Patch2 from comment #3 by a
factor of 2.63x.

Patch1 is also faster than Base by a factor of 6.76x.

Benchmark results:

Input value                 Base time        Patch1 time      Patch2 time
-------------------------------------------------------------------------
15999999832000000431        78.796292         0.057512        22.501813
15999999832000000432        80.945415         0.033662         0.888980
15999999832000000433        81.235536         0.003839        13.643711
15999999832000000434        80.566282        29.735831        30.042800
15999999832000000435        80.369279         0.162935        32.149949
15999999832000000436        80.402935         0.576786        36.607844
15999999832000000437        80.473461         0.003428        43.228909
15999999832000000438        79.911322         5.508081        55.743914
15999999832000000439        80.216414         0.013743        25.881780
15999999832000000440        80.265364         0.003458         0.423624
15999999832000000441        80.262461        80.191746        80.550838
15999999832000000442        80.185449         1.285730        55.418297
15999999832000000443        79.920971         0.255986         0.251054
15999999832000000444        79.780322        36.028808        36.207622
15999999832000000445        79.810045         2.573832        31.841480
15999999832000000446        79.860735         0.460476         9.549184
15999999832000000447        79.950774         0.107162        80.169429
15999999832000000448        79.845526         0.033626         7.154385
15999999832000000449        79.772000        11.908558        11.971591
15999999832000000450        79.687228         0.005464         0.815687
15999999832000000451        79.847437        79.790655        80.241356

Times:
ans = 1682.105248451233    ## Base
ans =  248.741317987442    ## Patch1
ans =  655.2842469215393   ## Patch2


Also, Patch2 fails the assertion for the input value 15999999832000000434
which has a prime factor larger than flintmax(). Patch1 and Base are both OK
on the assertions.

Benchmark code:

p = uint64 (3999999979) ^ 2; ## large prime^2, slow to factorize
lo = p-10;
hi = p+10;

pos = 0;
for i = lo:hi
  pos += 1;

  ## base factor()
  tic
  f = factor (i);
  t0(pos) = toc;
  p0(pos) = prod(f, "native");

  ## Patch1
  tic
  f = myfactor (i);
  t1(pos) = toc;
  p1(pos) = prod(f, "native");

  ## Patch2
  tic
  f = myfactor2 (i);
  t2(pos) = toc;
  p2(pos) = prod(f, "native");

  fprintf (1, "%u\t%f\t%f\t%f\n", i, t0(pos), t1(pos), t2(pos));
end
sum(t0)
sum(t1)
sum(t2)

assert (all(p0 == (lo:hi)))
assert (all(p1 == (lo:hi)))
assert (all(p2 == (lo:hi)))




    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61129>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/