The Museum of HP Calculators

HP Forum Archive 21

 A brand new calculator benchmark: "middle square method seed test"Message #1 Posted by Pier Aiello on 10 Sept 2013, 7:23 p.m. 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.

 Re: A brand new calculator benchmark: "middle square method seed test"Message #2 Posted by Bruce Bergman on 10 Sept 2013, 10:06 p.m.,in response to message #1 by Pier Aiello Great job on putting these up in a central place, Pier! I contacted you offline about the wiki, so check your mail. :-) Thanks, Bruce

 Re: A brand new calculator benchmark: "middle square method seed test"Message #3 Posted by Pier Aiello on 11 Sept 2013, 4:34 a.m.,in response to message #2 by Bruce Bergman 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.

 Re: A brand new calculator benchmark: "middle square method seed test"Message #4 Posted by Gilles Carpentier on 11 Sept 2013, 2:51 p.m.,in response to message #1 by Pier Aiello Hi Pier Could you explain what this program do ? It's very unclear for me. What sequenceIsConvergent and limitCyclicSequences means?

 Re: A brand new calculator benchmark: "middle square method seed test"Message #5 Posted by Pier Aiello on 11 Sept 2013, 4:18 p.m.,in response to message #4 by Gilles Carpentier 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

 Re: A brand new calculator benchmark: "middle square method seed test"Message #6 Posted by Marcel Samek on 11 Sept 2013, 6:57 p.m.,in response to message #5 by Pier Aiello 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.

 Re: A brand new calculator benchmark: "middle square method seed test"Message #7 Posted by Pier Aiello on 11 Sept 2013, 7:53 p.m.,in response to message #6 by Marcel Samek 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.

 New "simpler" benchmark: Ultra naive search for primesMessage #8 Posted by Pier Aiello on 11 Sept 2013, 8:42 p.m.,in response to message #1 by 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

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #9 Posted by Pier Aiello on 12 Sept 2013, 10:22 a.m.,in response to message #8 by 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #10 Posted by Gilles Carpentier on 12 Sept 2013, 1:30 p.m.,in response to message #8 by Pier Aiello 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

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #11 Posted by Pier Aiello on 12 Sept 2013, 3:40 p.m.,in response to message #10 by Gilles Carpentier 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #12 Posted by bhtooefr on 13 Sept 2013, 5:45 a.m.,in response to message #11 by Pier Aiello 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #13 Posted by Pier Aiello on 13 Sept 2013, 6:44 a.m.,in response to message #12 by bhtooefr Oh, i didn't know that. Thanks :)

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #14 Posted by Pier Aiello on 17 Sept 2013, 3:46 a.m.,in response to message #11 by 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 ```

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #15 Posted by Pier Aiello on 12 Sept 2013, 3:46 p.m.,in response to message #10 by Gilles Carpentier Maybe for n=100 is 0.052? It seems too slow :/

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #16 Posted by Tim Wessman on 12 Sept 2013, 7:10 p.m.,in response to message #15 by Pier Aiello 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #17 Posted by Pier Aiello on 13 Sept 2013, 3:28 a.m.,in response to message #16 by Tim Wessman 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #18 Posted by Paul Dale on 13 Sept 2013, 3:39 a.m.,in response to message #17 by Pier Aiello 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

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #19 Posted by Pier Aiello on 13 Sept 2013, 4:06 a.m.,in response to message #18 by Paul Dale 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.

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #20 Posted by Tim Wessman on 13 Sept 2013, 12:07 p.m.,in response to message #17 by Pier Aiello BCD vs float... TW

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #21 Posted by Pier Aiello on 13 Sept 2013, 12:45 p.m.,in response to message #20 by Tim Wessman 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..

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #22 Posted by Gilles Carpentier on 13 Sept 2013, 7:27 a.m.,in response to message #15 by Pier Aiello You're rigth. It's 0.052s and not 0.52

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #23 Posted by Gilles Carpentier on 12 Sept 2013, 2:06 p.m.,in response to message #8 by Pier Aiello "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 ;)

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #24 Posted by Pier Aiello on 12 Sept 2013, 3:41 p.m.,in response to message #23 by Gilles Carpentier 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

 Re: New "simpler" benchmark: Ultra naive search for primesMessage #25 Posted by Pier Aiello on 14 Sept 2013, 3:56 a.m.,in response to message #8 by 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.

 593 million for summation benchMessage #26 Posted by Pier Aiello on 13 Sept 2013, 1:58 p.m.,in response to message #1 by Pier Aiello Just to share :)

Go back to the main exhibit hall