▼
Posts: 120
Threads: 14
Joined: May 2013
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 (n1) 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.
▼
Posts: 553
Threads: 57
Joined: Sep 2006
Great job on putting these up in a central place, Pier!
I contacted you offline about the wiki, so check your mail. :)
Thanks,
Bruce
▼
Posts: 120
Threads: 14
Joined: May 2013
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.
Posts: 468
Threads: 17
Joined: May 2011
Hi Pier
Could you explain what this program do ?
It's very unclear for me.
What sequenceIsConvergent and limitCyclicSequences means?
▼
Posts: 120
Threads: 14
Joined: May 2013
Of course, and i use wikipedia for this (since it was my main source (1)). Given the notions in the Middlesquare 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 n1.
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 ndigit 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
▼
Posts: 189
Threads: 39
Joined: Nov 2011
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 WP34S 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 nontrivial benchmark that focuses on what they have in common, rather than what they don't, would be of more value.
▼
Posts: 120
Threads: 14
Joined: May 2013
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.
Posts: 120
Threads: 14
Joined: May 2013
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 k1 do {
if ( k mod j == 0 ) then {
j:= k1 //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
▼
Posts: 120
Threads: 14
Joined: May 2013
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 20042010, with scripting language like python, can be matched by newer calculators as nspire/prime as well as C implementations on hp50g/casios/ti8x .
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.
Posts: 468
Threads: 17
Joined: May 2011
Prime Result (Hdw rev 5106 )
EXPORT Bench1(n)
BEGIN
FOR K:=3 TO n DO
FOR J:=2 TO K1 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
▼
Posts: 120
Threads: 14
Joined: May 2013
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/ti8X.
edit:
The Prime has a CPU of 400mhz, comparable to smartphones of years 20082010 . 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.
▼
Posts: 113
Threads: 8
Joined: Feb 2007
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.
▼
Posts: 120
Threads: 14
Joined: May 2013
Oh, i didn't know that. Thanks :)
Posts: 120
Threads: 14
Joined: May 2013
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
TINspire 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
Posts: 120
Threads: 14
Joined: May 2013
Maybe for n=100 is 0.052? It seems too slow :/
▼
Posts: 1,278
Threads: 44
Joined: Jul 2007
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.
▼
Posts: 120
Threads: 14
Joined: May 2013
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 120
Threads: 14
Joined: May 2013
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.
Posts: 1,278
Threads: 44
Joined: Jul 2007
▼
Posts: 120
Threads: 14
Joined: May 2013
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..
Posts: 468
Threads: 17
Joined: May 2011
You're rigth. It's 0.052s and not 0.52
Posts: 468
Threads: 17
Joined: May 2011
"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 ;)
▼
Posts: 120
Threads: 14
Joined: May 2013
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
Posts: 120
Threads: 14
Joined: May 2013
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.
Posts: 120
Threads: 14
Joined: May 2013
