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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Mar 28, 2024 at 11:40:20AM +0100, 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 

You can save time by avoiding to compute i^2 several time.
Then you can save time by computing i^2 anj j^2 iteratively by
using the formula

(i+1)^2 = i^2 + (2*i+1)

i*(j+1) = i*j + i

Cheers,
Bill