About calculator benchmark (8 queens) and fast devices. MS challenge #2

[pier4r]

While reading the general forum, I ended up rereading the first page of the HRAST basic, pointing to the calculator benchmark. (The HRAST basic produces quite neat results, in line with sysrpl versions)

I thought that the benchmark, here, was not maintained since long time. Instead it has many new results! I wonder how the maintainer tracks the new results (Xerses seems registered here, just not so active). Kudos to him.

Said that, I believe that executions that are getting under 1 seconds are increasingly limited by the overhead of just 'starting' the computation. Therefore I would suggest to expand the benchmark for faster devices, for example nqueens with n=9, to see how much the real computation takes on the "fast" device.

For example, in a recent topic that I found here, a user reports a Free42 results that I believe are limited by the need to start the program (same for the HP prime application on similar android devices).

I remember I had this idea already and I checked the benchmarks that I added on the wiki4hp in 2013 (digression1). In particular the middle square benchmark (that is not a benchmark, rather a challenge, more of it later) that I proposed after reading the article of the middle square method used by von Neumann.

Here is the idea:

Code:


k:= a positive integer
n:= 100^k
For i:=(n/10) to (n-1) do {
  old := i
  sequenceIsConvergent := false
  limitCyclicSequences := 0 //because we can end in cyclic sequences and we don't want to use a lot of memory!
  while ( (NOT sequenceIsConvergent) AND (limitCyclicSequences < n) ) {
    new = extract_middle_number from old^2 (see below)
    if new == old { 
      sequenceIsConvergent = true
    }
    else { 
      old := new
      limitCyclicSequences = limitCyclicSequences+1;
    }    
  }//end while
}//end for

->Result: the time spent to finish the computation given the starting k value.

How does extract_middle_digits work?
Given n, that is a power of 10 of the type 10^d, 
its square is equal to 10^(d*2) and it has (d*2+1) digits.

We consider only the last (d*2) digits. 
That is: if n=10000, 10000*10000 = 100000000 we consider only 00000000 without the first 1.

Then we 'consider' all the numbers lower than 10^(d*2) with (d*2) digits. 
For example if d=4 and the number under process is 1542, 
we consider 1542^2 as 02377764 instead of 2377764.

Why d=4 ? Because we use as seed, with n=10000, numbers from 1000 to 9999, so numbers having 4 digits.

After that we pick the d=4 middle digits, from 02377764 we pick 02[3777]64.
So the middle number extracted is 3777.

This type of benchmark is pretty scalable, changing 'k', and should expose also the relative timings between a fast device/implementation vs a slower one as soon as k changes.

Anyway a user pointed out in my previous topic on the old forum that a benchmark is useful as comparison if similar set of instructions are used between calculators. Instead the middle square procedure can take advantage of instructions that some calculators does not have (Like IP and FP). Furthermore one is free to derive its own method to extract the middle digits, not exactly a fixed procedure.

Therefore more than a benchmark it is a challenge, where every calculator (and programming languages for those) is welcomed.
Since it is a challenge, feel free to find the most efficient method to compute the middle squares within the given constraints (k, n, i in the pseudocode above, the rest is optional).

According to the results previously collected, with 100^1 :
- 50g, ARM ASM / SATURN ASM under 1 second - same problem of the 8 queens benchmark
- 50g sysRPL around 1 second
- 50g userRPL around 10 seconds

With 100^2
- 50g, ARM ASM 169 sec
- 50g, saturn ASM 1445 secs - with k=2 one can appreciate the difference between saturn ASM and ARM ASM a bit more.
- 50g userRPL (not optimized) estimated over 250000 seconds

I don't think that calculators that handles the 8 queens benchmark in more than 10 minutes can end the challenge in little time ('little' according to your patience), but maybe others like the 48 series or those HP palmtops can do it.

What about the newRPL? (I can attempt this on the PC version, but that does not count)
Anyone willing to do it with HRAST BASIC?
(any other stable language for the 50g? Hp lua AFAIK is not so stable)
42s?
48 variants?
HP prime?
Casio/Ti ? (I will ask on the respective communities if I collect some more results here)

Is anyone willing to give it a shoot? I will try to implement it on the ti89, nspire and, why not, the free42 just as reference (also to learn a bit the RPN programming, although it looks like assembly)

digression1: there are many more to add, a simple search like site:hpmuseum.org benchmark returns hundreds of results to check, with at least tens of different benchmarks.

PS: The challenge itself could be even translated in a list processing problem now that I think about it, since one can work on the single digits. Although one has to implement operations for digits operations.