Monday, September 18, 2017

Setup realvnc server on raspberry headless using tightvncviewer

When I tried to connect to my headless raspberry via tightvncviewer I got the following message:

It appears that you have to install a viewer from realvnc ($? or registration?) in order to connect.

So I logged in to the raspberry via ssh and started a virtual vnc screen:

vncserver-virtual -Encryption PreferOn -Authentication VncAuth
This starts a new, virtual vnc server with the standard vnc authentications, tightvncviewer can connect to this one.

From this vnc connection I started a realvncviewer session to "localhost"

Allowing me to change the options for the default vnc server connected to the "screen" (port 5900 or :0) on the raspberry.

Accessing the options on the :0 realvnc server via realvnc viewer from a virtual (:1) realvncviewer from tightvncviewer.

From the options change Security/Authentication from "UNIX password" to "VNC password".

Now it is possible to connect directly to the realvncserver from tightvncviewer.

Thursday, January 12, 2017

Fast forwarding the std::next_permutation algorithm

I started my computer with a project that looks more and more like Sisyfos work.

It is trying to solve a puzzle by running through a set of permutations, and it is using std::next_permutation.

However, a day into the computation I realized that the algorithm could be further improved. Should I stop the calculation and restart it? Or let it continue, with the ineffective algorithm?

Looking at the internet I found an in depth explanation of std::next_permutation Implementation Explanation. std::next_permutation will from a starting point increase the permutation in an lexical fashion until it rolls over and returns false:

std::vector<int> skip_next_list = { 1,2,3,4, 5, 6, 7, 8, 9, 10, 11};
do {
//some work here
} while (std::next_permutation(skip_next_list.begin(), skip_next_list.end()));

My search had reached 309000000 when I aborted the job, so I needed to fast forward to that point. I realized that for 6 iterations (3!) it would update the last three entries of skip_next_list, for 24 (4!) the last four and so on.

So this is the skip_next_permutation function, fast forwarding to a number far into the sequence of std::next_permutation.

template<typename It> void skip_next_permutation(uint64_t skip_num, It begin, It end)
 if (skip_num <= 0) return; // does not have to be an error

 //build a lut of factorials, this could be a static
 std::vector<uint64_t> factorials;
 factorials.push_back(1); ///  0! == 1
 long idx = 1;
 long input_length = end - begin;
 do {
  factorials.push_back(factorials[idx-1] * idx);
 } while (factorials[++idx - 1] <= skip_num); //

 // now start to loop, find the factorial that is one smaller than the number we want to skip forward
 long my_inc = factorials.size() - 2; // always 2 lower than factorials.size()

  int quotient = skip_num / factorials[my_inc];
  skip_num = skip_num%factorials[my_inc]; //the remaider are the remaining skip_num

  if (skip_num == 0 && quotient == 0) goto end_loop;
  std::swap(begin[input_length - my_inc - 1], begin[input_length - my_inc + quotient - 1]);
  std::sort(begin + input_length - my_inc, end); //avoid with clever management?
 } while (my_inc >= 1);
The following table shows the factorials std::next_permutation algorithm exhausted, the number used for skip_next_permutation and the time std::next_permutation used.

Time / ms
362 879
39 916 799
6 227 020 799
14 436.6

The fast forward function skip_next_permutation uses approximately 0.009 ms for all the values.