Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Last active July 13, 2021 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Hermann-SW/004f2a6d26884deabce5842a37eef09f to your computer and use it in GitHub Desktop.
Save Hermann-SW/004f2a6d26884deabce5842a37eef09f to your computer and use it in GitHub Desktop.
loop2 displays "x->(x^2+a) mod n" graph using Graphviz neato command and Gnome image viewer
#!/bin/bash
#if 0
if [ $0 -nt /tmp/$0 ]; then gcc -xc -Wall -Wextra <(tail -n+2 $0) -o /tmp/$0; fi
/tmp/$0 $1 $2 > $1_$2.dot
neato -Tsvg $1_$2.dot > $1_$2.svg
eog $1_$2.svg
exit
#endif
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
unsigned dif(unsigned a, unsigned b)
{
return (a<b) ? b-a : a-b;
}
unsigned gcd(unsigned a, unsigned b)
{
if (a<b)
{
if (a==0) return b; else b%=a;
}
while (b!=0)
{
a%=b;
if (a==0) return b;
b%=a;
}
return a;
}
char nbsp[3] = { 0xC2, 0xA0, 0x00 };
char buf[10][100];
unsigned int buc=0;
char *lab(unsigned u)
{
if (++buc==10) buc=0;
sprintf(buf[buc], "\"%s%u%s\"", nbsp, u, nbsp);
return buf[buc];
}
int main(int argc, char *argv[])
{
unsigned n, a, x;
assert(argc==3);
n = atoi(argv[1]);
a = atoi(argv[2]);
printf("digraph D {\n");
printf("size=\"8 8\"\n");
for(x=0; x<n; ++x)
if (gcd(dif(x, n-x), n) > 1)
printf("%s [shape=box]\n", lab(x));
for(x=0; x<n; ++x)
printf("%s->%s\n", lab(x), lab((x*x+a)%n));
printf("}\n");
}
@Hermann-SW
Copy link
Author

Hermann-SW commented Jul 13, 2021

https://www.raspberrypi.org/forums/viewtopic.php?f=33&t=312344&p=1888647#p1888647

Executing this command ...

pi@raspberrypi4B:~/rho $ ./loop2 91 1

... displays this graph (with installed "graphviz" package):

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment