The idea Design a computation benchmark that involves the basic operations with little use of memory and can be handled by almost all programmable calculators. Moreover it's design should allow a challenge task even for newer calculators simply by increasing the input value. 1)
The pseudocode
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 } } }
How to report the results
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"
10 T=TIME 20 INPUT N 30 FOR K=3 TO N 40 FOR J=2 TO K-1 50 IF MOD(K,J)=0 THEN J=K-1 60 NEXT J 70 NEXT K 80 DISP TIME-T
EXPORT Bench1(n) BEGIN FOR K:=3 TO n DO FOR J:=2 TO K-1 DO IF K MOD J == 0 THEN BREAK; END; END; END; END;
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;
local start = zmg.ticks() n=100 for k=3,n do for j=2,k-1 do if k%j==0 then j=k-1 end end end print('n=100: ' .. (zmg.ticks()-start)/128 .. 'sec')
?->N For 3->K To N For 2->J To K-1 K-J*Int (K/J)=0=>Break Next Next
?->N For 3->K To N For 2->J To K-1 K-J*Int (K/J)=0=>Break Next Next
?->N For 3->K To N For 2->J To K-1 If K-J*Int (K/J)=0 Then K-1->J //31 sec, instead with Break are 30 IfEnd Next Next
?->N For 3->K To N For 2->J To K-1 K-J*Int (K/J)=0=>Break Next Next
?->N For 3->K To N For 2->J To K-1 If K-J*Int (K/J)=0 Then K-1->J //or Break, no change in performance IfEnd Next Next
def naiveprimes(n): import time; print time.localtime(); for k in range(3,n+1): for j in range(2,k): if k % j == 0: break; print time.localtime();
def naiveprimes(n): import time; print time.localtime(); for k in range(3,n+1): for j in range(2,k): if k % j == 0: break; print time.localtime();
The code has a temporal complexity of $ O( \frac{n \cdot (n+1)}{2} ) $ , so times between different inputs should be loosely proportional.
Then, with $ 10n $ we have the following proportion
$$ \left [
\frac
{\left ( \frac
{10n\cdot(10n+1)}
{2}
\right )}
{\left ( \frac
{n\cdot(n+1)}
{2}
\right )}
\sim
\frac
{t_{10n}} {t_n}
\right ]
\rightarrow
\left [
\left ( \frac
{10n\cdot(10n+1)}
{2}
\right )
\cdot
\left ( \frac
{2}
{n\cdot(n+1)}
\right )
\sim
\frac
{t_{10n}} {t_n}
\right ]
\rightarrow
\left [
t_{10n}
\sim
t_n \cdot
\left ( \frac
{10\cdot(10n+1)}
{(n+1))}
\right )
\right ] $$
In our case n=100 so we have 99 as a “coefficent”.
Thus for Hp50g:
8 sec * 99 = 792 sec (result of n:=100 times the coefficent) and the real result is 545
For Primz
6.5*99 = 643 sec while the real is 386
3.9*99 = 386 sec while the real is 237
Note: the same order of magnitude!
Because putting code in references makes the dokuwiki source code hard to read.
// ultranaiveprimes.c: silly algorithm for finding primes #define MIN_AMS 101 #define USE_TI89 #define USE_TI92P #define USE_V200 #define USE_TI89T #define NO_CALC_DETECT #define OPTIMIZE_ROM_CALLS #define RETURN_VALUE #include <stdint.h> #include <system.h> #include <args.h> #include <estack.h> #include <intr.h> #include <timath.h> #define TIMER_START_VAL (100000UL) #define N (10000) void _main(void) { uint16_t j, k; short orig_rate = PRG_getRate(); unsigned short orig_start = PRG_getStart(); unsigned long val = 0; // Make the system timer an order of magnitude more precise; // NOTE: this code assumes a HW2+ TI-68k, i.e. anything since 1999. PRG_setRate(1); // Increment counter at a rate of 2^19/2^9 Hz PRG_setStart(0xCE); // Trigger the interrupt every 257 - 0xCE = 51 increments ~ 20.07 Hz. // The PRG_getStart() above effectively waited for the interrupt to trigger, so we don't need another wait. /*OSRegisterTimer(USER_TIMER, 1); while (!OSTimerExpired(USER_TIMER)); OSFreeTimer(USER_TIMER);*/ OSRegisterTimer(USER_TIMER, TIMER_START_VAL); // Main loop :) for (k = 3; k < N; k++) { for (j = 2; j < k - 1; j++) { if (k % j == 0) { j = k - 1; // so we exit from the inner for } } } // Retrieve timer value. val = TIMER_START_VAL - OSTimerCurVal(USER_TIMER); OSFreeTimer(USER_TIMER); // Push arguments onto the RPN stack: clean arguments up, then create a list. while (GetArgType (top_estack) != END_TAG) { top_estack = next_expression_index (top_estack); } top_estack--; push_longint(val); // Restore old system state. PRG_setRate(orig_rate); PRG_setStart(orig_start); } Compiler options: tigcc -v -O3 -Wall -W -mpcrel --optimize-code --cut-ranges --reorder-sections --remove-unused --merge-constants -fmerge-all-constants -Wa,--all-relocs -Wa,-l -fverbose-asm -save-temps -o unprimes ultranaiveprimes.c
#include <display_syscalls.h> #include <keyboard_syscalls.h> #include <keyboard.hpp> #include <color.h> // Getkey routine const unsigned short* keyboard_register = (unsigned short*)0xA44B0000; unsigned short lastkey[8]; unsigned short holdkey[8]; void keyupdate(void) { memcpy(holdkey, lastkey, sizeof(unsigned short)*8); memcpy(lastkey, keyboard_register, sizeof(unsigned short)*8); } int keydownlast(int basic_keycode) { int row, col, word, bit; row = basic_keycode%10; col = basic_keycode/10-1; word = row>>1; bit = col + 8*(row&1); return (0 != (lastkey[word] & 1<<bit)); } int keydownhold(int basic_keycode) { int row, col, word, bit; row = basic_keycode%10; col = basic_keycode/10-1; word = row>>1; bit = col + 8*(row&1); return (0 != (holdkey[word] & 1<<bit)); } int main() { int n=100; //change n as input int key; // clear screen Bdisp_AllClr_VRAM(); PrintXY(1,1,"Wait...",0,COLOR_BLACK); Bdisp_PutDisp_DD(); for (int k = 3; k < n; ++k) { for (int j = 2; j < k-1; ++j) { if(k%j==0) { j = k-1; } } } PrintXY(1,1," done",0,COLOR_BLACK); Bdisp_PutDisp_DD(); GetKey(&key); while(1) { GetKey(&key); } return 1; }
1000->N For 3->K To N For 2->J To K-1 MOD(K,J)=0=>Break Next Next
CODE A=0.W GOSBVL POP# GOSBVL SAVPTR SKUB { *start !ARM STMDB sp! {R4 R5 R6 LP} LDR R2,[R1,#2316] MOV R3,3 *outer MOV R4,2 *inner MOV R5,R4 *modloop1 MOV R5,R5 LSL #1 CMP R5,R3 BLO modloop1 BEQ outer_end MOV R6,R3 *modloop2 CMP R6,R5 BEQ outer_end SUBHS R6,R6,R5 MOV R5,R5 LSR #1 CMP R5,R4 BHS modloop2 ADD R4,R4,1 CMP R4,R3 BLO inner *outer_end ADD R3,R3,1 CMP R3,R2 BLS outer LDMIA sp! {R4 R5 R6 PC} !ASM *end } C=RSTK D0=C D1=80100 LC(5)end-start MOVEDN LC 80100 ARMSAT GOVLNG GETPTRLOOP ENDCODE
CODE A=0.W GOSBVL POP# GOSBVL SAVPTR SKUB { *start !ARM STMDB sp! {R4 R5 R6 LP} LDR R2,[R1,#2316] ;Saturn A register MOV R3,3 *outer MOV R4,2 *inner MOVS R5,R4 LSL #16 MOVCS R5.R4 MOVS R6,R5 LSL #8 MOVCS R6,R5 MOVS R5,R6 LSL #4 MOVCS R5,R6 MOVS R6,R5 LSL #2 MOVCSS R6,R5 MOVPL R6,R6 LSL #1 MOV R5,R3 *modloop CMP R5,R6 BEQ outer_end SUBHS R5,R5,R6 MOV R6,R6 LSR #1 CMP R6,R4 BHS modloop ADD R4,R4,1 CMP R4,R3 BLO inner *outer_end ADD R3,R3,1 CMP R3,R2 BLS outer LDMIA sp! {R4 R5 R6 PC} !ASM *end } C=RSTK D0=C D1=80100 LC(5)end-start MOVEDN LC 80100 ARMSAT GOVLNG GETPTRLOOP ENDCODE
local timerStart = timer.getMilliSecCounter() local n = 100 for k = 3, n do for j = 2, k-1 do if k%j==0 then break end end end print("n = " .. n, (timer.getMilliSecCounter()-timerStart)/1000 .. ' s.')
CODE GOSBVL POP# GOSBVL SAVPTR A+1.A B=0.A B+3.A *outer C=0.A C+2.A *inner D=B.A D%C.A ?D=0.A GOYES outer_end C+1.A ?B>C.A GOYES inner *outer_end B+1.A ?A>B.A GOYES outer GOVLNG GETPTRLOOP ENDCODE
CODE GOSBVL POP# A+1.A R0=A.A A=0.A A+3.A *outer R1=A.A C=0.A C+2.A *inner R2=C.A GOSBVL IntDiv ?A=0.A GOYES outer_end C=R2.A C+1.A A=R1.A ?A>C.A GOYES inner *outer_end A=R1.A A+1.A C=R0.A ?C>A GOYES outer GOVLNG Loop ENDCODE
:: CK1NOLASTWD CK&DISPATCH1 real :: CLKTICKS SWAP COERCE #1+ THREE DO INDEX@ TWO DO JINDEX@ INDEX@ #/ DROP #0= IT ExitAtLOOP LOOP ATTN? IT ExitAtLOOP LOOP CLKTICKS SWAP bit- HXS>% %8192 %/ ; ;
« @n as input PUSH @saves system flags -105 SF @approx mode 3 SWAP @from 3 to n FOR k 2 k 1 - @fro 2 to k-1 FOR j IF k j MOD 0 == @k mod j == 0 THEN k 'j' STO @to exit from the FOR END NEXT NEXT POP » executed with TEVAL
prime(n) Prgm Local k,j For k,3,n For j,2,k-1 If mod(k,j)=0:Exit EndFor EndFor EndPrgm