Trial-division interface

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund <tg at gmplib.org> writes:
  
  > Your suggested interface is to store a factor through an (unsigned int
  > *).  I suggest that we inmstead return it.
  
  Fine with me, if you think the additional work (which is unnecessary for
  callers that only care about existence of the factor, not the particular
  value) is insignificant. With the current trialdiv implementation, the
  additional work would be one binvert, which I guess may be a small price
  to pay for a simpler interface.
  
You misunderstand me.

*If* we are going to return it *somehow*, then it is better to make it
the function return value instead if having it go thought an unsigned
int pointer.  Then this return value can be used both as a source for a
factor *and* as a boolean telling if a factor was found.

  Shared read-only data is clearly ok, and I guess shared write-once data
  should be ok as well if the initialization, as you outlined it, doesn't
  cause any trouble. I imagine it gets a little trickier to make
  initialization and allocation thread safe for a prime table of a size
  which is determined (and might grow) during runtime.
  
I was talking about the static size table, not a growable table, i.e. a
table that might be compiled and stored as part of libgmp.{a,so}.

Managing growable prime tables in a thread-safe way without locks is
probably doable, but I haven't thought about it.  The main problem might
be if thread A decides for a larger table than thread B, and then when A
is read and B is read, the end table that wins is B's table.  Then A
will see a smaller table than it expected.  It then needs to recompute:

  while (table.size < new_size)
    compute_table (new_size)

-- 
Torbjörn