0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
int cmp(const void *a, const void *b)
{
   unsigned long A=*(unsigned long *) a;
   unsigned long B=*(unsigned long *) b;
   if( A < B) return (-1);
   else if (A > B) return 1;
   else return (0);
};
int main(int argc,char **argv)
{
   {unsigned int seed= (argc==1)?1:atoi(argv[1]);srand(seed);}
   int n = 24;/* will theoretically work for n<= 64,#number bits in unsigned long but takes too long*/
   assert( n < sizeof(unsigned long)*8);
   unsigned long N= (1<<n);  // N  a power of 2  */
   unsigned long M= N-1; // mod N,  and it  with  M
   fprintf(stdout,"N=%lu M=%lu,  bits in N =%lu\n",N,M,sizeof(unsigned long)*8);
   unsigned  long r0= rand() & M;
   unsigned  long q= (rand() & M) | 1; // or with 1 to make sure its odd
   fprintf(stdout,"r0=%lu q=%lu\n",r0,q);
   unsigned long r,a;
   unsigned long *P=calloc(N,sizeof(unsigned long ));
   assert( P != 0); // allocation success required
   long i;
   for (a=0,r=r0, i=0;i<N;i++ , a+=q, r=(r + a) & M)   P[i]=r;
   qsort(P,N,sizeof(unsigned long),cmp);
   for (i=0;i<N;i++) assert( P[i] == i);
   free(P);
}
lhickey
  • 1
  • I need to enter this small program but it is mangled beyond recongnition with cut and paste. – lhickey Dec 09 '17 at 22:54
  • You need to indent to have it formatted as code rather than as text. There's a shortcut to help with this: CTRL-K will indent a block of text. –  Dec 09 '17 at 22:59
  • 2
    That said, you really should post the mathematical question you mean to ask, not "Here's some code. See if you can both figure out what it's doing and figure out what I want to know so you can tell me." –  Dec 09 '17 at 23:00
  • 1
    I didn't see a quadratic equation. Where is it? I'm not good at reading C :-( IMHO if there is an actual equation looping over the field that probably is a math question, but you should probably phrase it as one! – Jyrki Lahtonen Dec 09 '17 at 23:05
  • This question doesn{t belong here. – DonAntonio Dec 09 '17 at 23:05
  • the quadratic equation comes from adding q to a and adding a to r. This operation makes a constant second difference on r_i when q is constant. – lhickey Jan 26 '18 at 16:43

1 Answers1

1

The main code is there : $q,r_0$ are random, $a_{i+1} = a_i + q= i q, r_{i+1} = (r_i+a)\ \ \land \ \ 2^N-1$ (where $\land$ is bitwise and).

Thus $$r_{i+1} = r_i+a r_i= r_i+iq = r_i+q \frac{i(i+1)}{2}=r_0+q\frac{i(i+1)(i+2)}{6} \bmod 2^N$$

At the end the program checks if $\{r_i\}$ contains all the integers $\bmod 2^N$.

reuns
  • 77,999
  • why does the r_i sequence form a permutation of period 2^24? (full permutation) Get a distinct permutation for every choice of r_0 and q, with q chosen odd. all arithmetic is mod 2^24. – lhickey Jan 26 '18 at 16:45