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



#2

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.


#3

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

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

Thanks,

Bruce


#4

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.

#5

Hi Pier

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

What sequenceIsConvergent and limitCyclicSequences means?


#6

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


#7

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.


#8

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.

#9

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


#10

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.

#11

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


#12

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.


#13

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.


#14

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

#15

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

#16

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


#17

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.


#18

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.


#19

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


#20

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.

#21

BCD vs float...

TW


#22

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..

#23

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

#24

"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 ;)


#25

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

#26

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.

#27

Arm asm solution of 3298 and List updated

Just to share :)


Possibly Related Threads...
Thread Author Replies Views Last Post
  [HP-Prime CAS] "Warning, ^ (Command) Is ambiguous on non square matrices"?? CompSystems 1 226 12-07-2013, 07:15 PM
Last Post: CompSystems
  A fast Bernoulli Number method for the HP Prime Namir 16 703 11-22-2013, 04:46 PM
Last Post: Namir
  HP-42S ESD self-test Yriarte 2 194 10-24-2013, 09:08 AM
Last Post: Yriarte
  Yet another benchmark port on the wiki: Savage Pier Aiello 35 1,276 09-26-2013, 03:22 AM
Last Post: Pier Aiello
  So I took a test with my Prime today ... kris223 12 547 09-25-2013, 07:19 PM
Last Post: kris223
  New community-maintained version of "Calculators benchmark: add loop" Pier Aiello 20 786 09-12-2013, 02:42 AM
Last Post: Pier Aiello
  Concern about Voyager keyboard test Matt Agajanian 2 232 08-30-2013, 07:56 PM
Last Post: Matt Agajanian
  Downhill Simplex Method (Nelder Mead) for WP-34S Marcel Samek 0 106 07-07-2013, 03:05 AM
Last Post: Marcel Samek
  Voyager Self Test Mike (Stgt) 5 301 05-16-2013, 03:28 PM
Last Post: Mike (Stgt)
  Square Root Simplifier for HP39gII Mic 4 249 03-11-2013, 08:25 AM
Last Post: Eddie W. Shore

Forum Jump: