Re: Array of the multiplicities of a highly non injective function

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

On 2024-03-28 11:40, Emmanuel ROYER wrote:
> Dear Pari-users and developers!
>
> Suppose we have a symmetrical function f from [1,K]x[1,K] with values 
> in [1,q] where the integer K is significantly greater than the integer q.
>
> I want to construct a vector V (of size q) such that each V[a] 
> contains the number of pairs (i,j) such that a = f(i,j).
>
> I have two questions
> 1) Is there a more efficient way of doing what I want than the code below?
> 2) Can we imagine parallelizing, for example, the loop on i ?
>
> K = 30;
> q = 7;
> f(i,j) = 1+lift(Mod(i^2+j^2+i*j,q));
> V = vector(q,h,0);
> for(i=1,K,V[f(i,i)] += 1;for(j=1,i-1,V[f(i,j)] += 2));
> V
>
> Comments
> - You have to imagine K much larger
> - I have fixed f in the example but I want to be able to do something 
> for any other choice respecting the assumptions (essentially, symmetry).
>
>
> Emmanuel Royer
> Professeur à l'Université Clermont Auvergne
> https://royer.perso.math.cnrs.fr
> ----
> Institut CNRS-Pauli
> IRL2842
> CNRS & Wolfgang Pauli Institut

Just an innocent port:

do(K=30, q=7) = {
  my(V=Vec(0, q), f(i, j) = 1+lift(Mod(i^2+j^2+i*j, q)) );
  for(i=1, K
  , V[f(i,i)] += 1;
    for(j=1, i-1, V[f(i,j)] += 2)
  );
  V;
}

pardo(K=30, q=7) = {
  my(V=Vec(0, q), f(i, j) = 1+lift(Mod(i^2+j^2+i*j, q)) );
  parfor(i=1, K
  , my(t=Vec(0,q));
    t[f(i,i)] += 1;
    for(j=1, i-1, t[f(i,j)] += 2);
    t
  , t
  , V+=t
  );
  V;
}


? do(4000)
cpu time = 4,426 ms, real time = 4,468 ms.
% [4245387, 1958530, 1958530, 1959673, 1958530, 1959675, 1959675]

? pardo(4000)
cpu time = 5,587 ms, real time = 588 ms.
% [4245387, 1958530, 1958530, 1959673, 1958530, 1959675, 1959675]

-- Ruud