A brand new calculator benchmark: "middle square method seed test"

[Pier Aiello]

I have written it directly on wiki4hp (and sorry for my english, i hope that others editors will fix it)

Here i copy only the pseudocode of the test:

k:= a number > 0

n:= a power 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 { //you can't use new == 0 here as a "fast" condition.

      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 tipe 10^d, its square is equal to 10^(d*2) and it has (d*2+1) digits.

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

Then we see all the numbers lower than 10^(d*2) with (d*2) digits, so if d=4, 

we see 1542^2 as 02377764 instead of 2377764.

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

So the middle number extracted is 3777.

Again, i hope that the admin of wiki4hp will be more tolerant, so users can edit directly the wiki page.

Oh, my hp50g is crunching the test with k=2 and several minutes have already passed.

Edited: 10 Sept 2013, 7:26 p.m.

[Bruce Bergman]

Great job on putting these up in a central place, Pier!

I contacted you offline about the wiki, so check your mail. :-)

Thanks,

Bruce

[Pier Aiello]

Email checked ;)

About the benchmark, my hp50g is in trouble!!

The smallest input, 100 (or 100^k with k=1), have a complexity of O(100*100) in terms of repeated cycles. It, anyway, has finished in 24 secs.

But with 100^2, we have a complexity of O(100^2*100^2=100^4), that is 100^2 times the previous one. So 24*100^2 = 240.000 secs = several days.

Now i'm keep it crunching (thanks to usb hubs that can be coupled with a small power supply [a nokia one, for example], so they are can give current even without a computer), but i guess that the 100^2 input is only for faster version/devices. Maybe an HPGCC version can do it in several minutes.

I'm curious about a HP50g with HPGCC / Wp34s / HP39gII / HP prime / TI 89 with TIGCC / TI nspire versions.

While i guess that previous calculators can solve, in less than an hour, only the 100^1 input.

[Gilles Carpentier]

Hi Pier

Could you explain what this program do ?
It's very unclear for me.

What sequenceIsConvergent and limitCyclicSequences means?

[Pier Aiello]

Of course, and i use wikipedia for this (since it was my main source (1)). Given the notions in the Middle-square Wikipedia article we have that the middle square method has a lot of flaws because the sequence can be convergent or cyclic really fast. An example:

Let k=1 , so we have as reference n:= 100^k = 100

Do sequences for all the seeds from a:=n/10 to n-1.

So the seeds are {a:=10,11,12,...,99}

How do we compute a sequence?

a:=10

seed:=a

1. we first square the number

10*10 = 100

2. But our reference is 100, so 100 squared is 10000, with 4 zeroes, then we consider the number with four digits (with a leading zero)

0100

3. Then we pick the middle digits, as many as the zeroes of n (that is 100), the new seed is

0[10]0

4. But the new seed is the same as the initial seed, then if we reapply the process we end up always with 10. Then the sequence is convergent.

Next step

a:=11

seed:=a

seed^2 -> 121

See it with 4 digits -> 0121

Pick middle digits -> 0[12]1 , seed:= 12

seed^2 -> 144

See it with 4 digits -> 0144

Pick middle digits -> 0[14]4, seed:=14

seed^2 -> 196

See it with 4 digits -> 0196

Pick middle digits -> 0[19]6, seed:=19

seed^2 -> 361

See it with 4 digits -> 0361

Pick middle digits -> 0[36]1, seed:=36

seed^2 -> 1296

See it with 4 digits -> 1296

Pick middle digits -> 1[29]6, seed:=29

seed^2 -> 841

See it with 4 digits -> 0841

Pick middle digits -> 0[84]1, seed:=84

seed^2 -> 7056

See it with 4 digits -> 7056

Pick middle digits -> 7[05]6, seed:=5

seed^2 -> 25

See it with 4 digits -> 0025

Pick middle digits -> 0[02]5, seed:=2

seed^2 -> 4

See it with 4 digits -> 0004

Pick middle digits -> 0[00]4, seed:=0

seed^2 -> 0

See it with 4 digits -> 0000

Pick middle digits -> 0[00]0, seed:=0

Here the new seed is the same of the previous, so the process stops

let's skip some iterations

a:=24

seed:=a

seed^2 -> 576

See it with 4 digits -> 0576

Pick middle digits -> 0[57]6, seed:=57

seed^2 -> 3249

See it with 4 digits -> 3249

Pick middle digits -> 3[24]9, seed:=24

At this time you can do an infinite loop that is cyclic,

so i limit any sequence to max 100^k iterations (2).

(1) I want to design a "simple" benchmark, so i thought about the extraction of numbers from a random sequence, or better, from decimals of transcendental numbers. So i stumbled on Bailey–Borwein–Plouffe formula, but it is a bit complex so i prefer a simpler method.

(2)Yes, i miss the phrase For a generator of n-digit numbers the period can be no longer than 8^n, now it is late and moreover this is a benchmark so the more computations, the better challenge for fast calculators.

Edited: 11 Sept 2013, 8:05 p.m. after one or more responses were posted

[Marcel Samek]

I think that using this particular problem as a general purpose benchmarks for calculators is somewhat problematic.

The reason I think so is that it focuses on integer manipulation and digit twiddling and not all calculators have comparable instruction sets to do these operations. While I am sure that I could code this up on pretty much any calculator, on a 15C, for example, where there are only floating point operations, the code would be
radically different then it would on a WP-34S which has both integer operations as well as bit twiddling operations.

So, what does a benchmark like this compare? For one it compares the cleverness of the programmer on different platforms, but that isn't really the point. What you really want is a benchmark that can be implemented in a comparable way on various platforms so that you can actually compare the performance of the target in executing the comparable code. When the code starts looking very different on different platforms, you are not really comparing the performance of the platform, but rather the suitability of the platform to a particular type of problem.

While some calculators have integer and bit operations, pretty much all of them have floating point operations, and all of them have trigonometric functions, etc. and it seems to me that a non-trivial benchmark that focuses on what they have in common, rather than what they don't, would be of more value.

[Pier Aiello]

Yeah, you are right. But i thought that the entire benchmark, even if rewards the ability of the programmer plus the math framework of the calculator, have as target calculators like 48 series and its successors (so with an extended mathematical framework).

But anyway, you are still right, i'll write ASAP another benchmark, that is based on prime numbers without any memory use. It's a plain stupid one: new number, start dividing it by 2,3,... (using modulo, or a user function that simulate it) it is prime? Yes, else check then next one.

Edited: 11 Sept 2013, 7:54 p.m.

[Pier Aiello]

As Marcel Samek on 11 Sept 2013 pointed out, the middle square test don't fit in programmable calculators with limited mathematical framework about floor/ceiling functions and manipulating digits.

So, there is a new simpler, but anyway tough, benchmark: "Ultra naive search for primes" .

The code is:

input: n

--

for k:=3 to n do {

  for j:=2 to k-1 do {

    if ( k mod j == 0 ) then {

      j:= k-1 //so we exit from the inner for

    }

  }

}

The result format is:

A result is composed by the following list

- the device used plus the language used, eventual overclock, eventual custom firmware and so on.

- time elapsed for a given n in seconds (see below)

- the code used.

if the calculator is too slow, or limited, to compute a given n, then report "for n the computation

takes too much time". Conversely, if the calculator is too fast to compute a given n, then report 

"for n the computation takes too little time, i skipped it"

The options are

n:= 100

n:= 1000

For very fast implementations:

n:= 10000

n:= 100000

PS: i can't add the hp50g values now, since it is still crunching the middle square test with k:=2

[Pier Aiello]

Ok, Casio's guys are really kind and i'm starting to gather some results (on primz for example).

Primz is almost 2x faster than 50g (at least the hp50g with my userRPL that is very simple) even if it has not so much memory.

While Ti community is still idle (as well as HP one. Lend me some calculators!)

I have added also some results of smartphones (using python) that are powerful but not extremely powerful as today ones. I think that cheap or mid level smartphones of 2004-2010, with scripting language like python, can be matched by newer calculators as nspire/prime as well as C implementations on hp50g/casios/ti-8x .

Even newer devices (released after 2010) with emulators of calculators or mathematical frameworks (math studio / spacetime for example, free42, droid48, etc. ) can't do so better, in my opinion than the stuff cited previously.

[Gilles Carpentier]

Prime Result (Hdw rev 5106 )

EXPORT Bench1(n)

BEGIN

 FOR K:=3 TO n DO

   FOR J:=2 TO K-1 DO

    IF NOT(K MOD J) THEN BREAK; END; 

   END; 

 END;

END;

TIME(Bench1(100)) -> 0.52 sec TYPO EDIT It's 0.052s

TIME(Bench1(1000)) -> 2.762 sec

TIME(Bench1(10000)) -> 202.112 sec

Edited: 13 Sept 2013, 7:26 a.m. after one or more responses were posted

[Pier Aiello]

Thanks! I'll add it now but anyway the prizm has done an unbelievable result! It is way faster than the palm treo pro and nokia e5 (both with python that is like lua/modula on TIs, CASIOs and HPs).

And, so, it is way faster than Prime. I'm wating for a "revenge" by Hp50 with HPGCC, hp39gii & prime with C (if it exists); and of course for nspires/ti-8X.

edit:
The Prime has a CPU of 400mhz, comparable to smartphones of years 2008-2010 . The palm treo has the same clock but is way faster, even if pythonCE was a not developed by Windows nor Palm.

So is not only a matter of MHZ + emulation (as in Hp50g).

Edited: 12 Sept 2013, 4:08 p.m.

[bhtooefr]

That particular Treo also has an ARM11 versus the Prime's ARM9.

ARM's own specs would predict that the Treo would be about 14% faster on raw CPU power.

[Pier Aiello]

Oh, i didn't know that. Thanks :)

[Pier Aiello]

A small update, finally a wild Nspire appears!!

n is 10'000

Hp 50g ARM ASM version 2.15 with HPGCC3 patch

- Time: 3.0181 s @75mhz

TI-Nspire CX CAS, not overclocked , OS 3.2.3, lua

- Time: 63 s (default 133 MHz)

HP Prime (Hdw rev 5106 ), modula

- Time: 187.12 sec @400mhz

[Pier Aiello]

Maybe for n=100 is 0.052? It seems too slow :/

[Tim Wessman]

I got:

100->.052s

1000->2.74s

10000->199.67s

So yeah, think it is missing a 0.

Also, I changed it to be K MOD J == 0 to match closer the given code. Seems to also actually reduce the times some.

100->.047_s

1000->2.567_s

10000->187.12_s

Seems to slot it right around a 50g running the more efficent saturn ASM code.

Also, out of curiosity you should ask over in the casio forum if they have any way to do a *native* numerical calculation instead of a pure C int calculation in the C program. It would be interesting to see the casio math library MOD function used instead with the user number object instead of a pure integer for comparison.

TW

Edited: 12 Sept 2013, 7:27 p.m.

[Pier Aiello]

While i agree that prime is very fast just with basic tools, i must ask: is the saturn ASM emulated as well? If it is so, then is not so "efficient" (ok, is way better than userRPL, but i guess that hpgcc is both faster and more readable than a low level lang.)

But what stunned me is what i wrote in message #12. I expected than a math device at the same speed (1) of a smartphone can overcome (or at least be on the same level) the latter by far in math things using an high level and quick language (as is scripting with modula or python). Why? Just because the interpreter/compiler on the math device should be "optimized" a lot for its hw.

Instead the Prime is quite slow against pythonCE on a 400mhz cpu with WM6.1 , and i don't think that pythonCE was optimized for the palm treo hw.

(of course the prime not needs to be extremely faster, in the end is a quick math tool)

(1) I'm aware that the speed doesn't count the cpu efficiency.

[Paul Dale]

Quote:

---

I expected than a math device at the same speed (1) of a smartphone can overcome (or at least be on the same level) the latter by far in math things using an high level and quick language

---

There are a lot of other issues beyond raw CPU speed involved here.

A smart phone won't have a highly accurate, mostly correctly rounded decimal mathematics library. Accuracy costs CPU. A calculator must give the best answers it can all of the time. A phone needn't be so stringent.

- Pauli

[Pier Aiello]

You are completely right. I always forget that a math model involves also accuracy, because i don't use so much smaller digits (even tough i'm aware of techniques of numerical analysis to get the maximum accuracy possible).

Edited: 13 Sept 2013, 4:08 a.m.

[Tim Wessman]

BCD vs float...

TW

[Pier Aiello]

Oh, right. Nevermind then, and thanks for the hint (1)!

(1) For another aspect, this shows that the mathematical environment of a calculator is far better than a "cheap" environment on a smartphone when the correctness is needed..

[Gilles Carpentier]

You're rigth. It's 0.052s and not 0.52

[Gilles Carpentier]

"PS: i can't add the hp50g values now, since it is still crunching the middle square test with k:=2 "

I hope you connect it to the USB port to avoid draining the batteries ;)

[Pier Aiello]

Sure it was connected! (i interrupted the operation after 48 hours). Now it has just done the ultranaiveprimes for n=10'000. 40'000 secs :P

[Pier Aiello]

The ARM ASM on HP50g has smashed both PRIZM and (early)smartphones with scripting languages.

Even tough coding more than simple operations with ASM is quite hard, but they can be a nester to speed up eventual code.

[Pier Aiello]

Arm asm solution of 3298 and List updated

Just to share :)