« previous next »
Pages: [1]   Go Down

Author Topic: My z80 basic palprime algorithm  (Read 4464 times)

0 Members and 1 Guest are viewing this topic.

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
My z80 basic palprime algorithm
« on: May 13, 2013, 03:46:54 pm »
While I only participated in the TI-Nspire section for the palprime contest, I made a z80 basic version too (which I did not enter). It's my first basic program for z80 based calculators.
It finds the 42nd palprime in 16 seconds (TI-84 Plus)

Here is the code
Code: [Select]
:Ans→N    --- find the AnsTh palprime
:5→A
:0→E
:While 1
:E+1→E
:1+int(log(Ans→B
:int(E10^(1-Ans
:If prod(Ans-{1,3,7,9
:End
:E10^(B+1→F
:E
:For(G,B,1,{-}1
:.1Ans→D
:F+fPart(Ans)10^(G→F
:int(D
:End
:10^(B→P
:For(H,0,9
:If fPart(F/3:Then
:5
:While Ans{^2}≤F and fPart(F/Ans) and fPart(F/(Ans+2
:Ans+6
:End
:If Ans{^2}>F
:Then
:A+1→A
:If A=N:Stop
:End
:End
:F+P→F
:End
:End
The result will be stored in F.

Beware I'm using some end tokens to quickly jump again to the start of the loop, so there is start/end of block 'mismatching' ;P.
While I'm not really going to continue this I'd like to know if I still can optimise it more (the code, not the algorithm)^^

Edit: I forgot, it can not find the first 5 palprimes, not implemented because I was first focusing on the algorithm
« Last Edit: May 13, 2013, 04:04:19 pm by Jim Bauwens »
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: My z80 basic palprime algorithm
« Reply #1 on: May 13, 2013, 08:35:02 pm »
So I tested yours and I got 21 seconds for the 42nd prime palindrome.
Compared to mine, yours is 53 bytes less, too. You have a bunch of places that can be optimised for speed, though, so I tried a few things and here is what I have:
First, here are the main optimisations I made:
Code: [Select]
:If prod(Ans-{1,3,7,9
     Goes to:
:If 1<gcd(10,Ans           ;I actually used 'not equal', but this works, too

:If fPart(F/3
     Goes to:
:If remainder(F,3

:While Ans{^2}≤F and fPart(F/Ans) and fPart(F/(Ans+2
     Goes to:
:While Ans{^2}≤F and min(remainder(F,{Ans,Ans+2
There are a few more, too, but here is what I ended up with:
Code: [Select]
:DelVar EAns-5→N
:While 1
:E+1→E
:1+int(log(E→B
:If 1<gcd(10,int(E10^(1-Ans
:End
:10E→F
:E→D
:While iPart(D
:.1iPart(D→D
:10(F+fPart(Ans→F
:End
:For(H,0,9
:If remainder(F,3
:Then
:√(F→D
:7
:While Ans≤D and min(remainder(F,{Ans,Ans+4
:Ans+6
:End
:N-(Ans>D→N
:If not(Ans
:Return
:End
:End
:F+10^(B→F
:End
:End
Now it takes about 17 seconds to compute the 42nd prime palindrome and it is 24 bytes smaller :)

I have been trying to tweak it to get it even faster and I know that there must be a few optimisations that I am not seeing. It is 77 bytes smaller than mine and almost as fast, so that is really awesome.

...

After adjusting the prime checker thing even more, I made it much faster, and it is now faster than mine, at the cost of some bytes (still 59 bytes smaller than mine). For comparison, the version above takes 17 seconds to find palprime 42 and 86 seconds for palprime 100. This version takes 13 and 52 seconds, respectively.
Code: [Select]
:DelVar EAns-5→N
:While 1
:E+1→E
:1+int(log(E→B
:If 1<gcd(10,int(E10^(1-Ans
:End
:10E→F
:E→D
:While iPart(D
:.1iPart(D→D
:10(F+fPart(Ans→F
:End
:For(H,0,9
:If min(remainder(F,{3,7,11
:Then
:√(F→D
:13
:While Ans≤D and min(remainder(F,Ans+{0,4,6,10,16,18,24,28
:Ans+30
:End
:N-(Ans>D→N
:If not(Ans
:Return
:End
:End
:F+10^(B→F
:End
:End
Hopefully everything is typed properly.
EDIT: Made it even faster. Now 12 and 49 seconds respectively, using the same prime checking routine as my program.
« Last Edit: May 13, 2013, 08:55:20 pm by Xeda112358 »
Logged
+1/-0 karm for this message

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: My z80 basic palprime algorithm
« Reply #2 on: May 13, 2013, 08:42:42 pm »
The problem is that remainder() is available only on 2.53MP and up. How does the algorithm fare if you use an optimized fPart() instead?
Logged
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: My z80 basic palprime algorithm
« Reply #3 on: May 13, 2013, 08:46:55 pm »
I typically avoid using commands specific to the MP OSes, but since it was for a contest where speed was required, that is what I used. However, for those that want the version useful on all OSes:
Code: [Select]
:DelVar EAns-5→N
:While 1
:E+1→E
:1+int(log(E→B
:If 1<gcd(10,int(E10^(1-Ans
:End
:10E→F
:E→D
:While iPart(D
:.1iPart(D→D
:10(F+fPart(Ans→F
:End
:For(H,0,9
:If fPart(F/3
:Then
:√(F→D
:7
:While Ans≤D and min(fPart(F/Ans+{0,4,6,10,12,16,22,24
:Ans+30
:End
:N-(Ans>D→N
:If not(Ans
:Return
:End
:End
:F+10^(B→F
:End
:End
And it takes 70 seconds for the 100th (as opposed to 52 seconds) and 16 seconds for the 42nd (as opposed to 13)
Logged

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: My z80 basic palprime algorithm
« Reply #4 on: May 14, 2013, 03:04:25 pm »
Quote from: Xeda112358 on May 13, 2013, 08:35:02 pm
So I tested yours and I got 21 seconds for the 42nd prime palindrome.
Strange, I just tried it again and I get 16s on my TI-84 Plus. (not sure what OS version actually). I've attached my program to this post, could you time that (in case something is different in tokens)?


Quote from: Xeda112358 on May 13, 2013, 08:35:02 pm

Compared to mine, yours is 53 bytes less, too. You have a bunch of places that can be optimised for speed, though, so I tried a few things and here is what I have:
First, here are the main optimisations I made:
Code: [Select]
:If prod(Ans-{1,3,7,9
     Goes to:
:If 1<gcd(10,Ans           ;I actually used 'not equal', but this works, too

:If fPart(F/3
     Goes to:
:If remainder(F,3

:While Ans{^2}≤F and fPart(F/Ans) and fPart(F/(Ans+2
     Goes to:
:While Ans{^2}≤F and min(remainder(F,{Ans,Ans+2
There are a few more, too, but here is what I ended up with:
Code: [Select]
:DelVar EAns-5→N
:While 1
:E+1→E
:1+int(log(E→B
:If 1<gcd(10,int(E10^(1-Ans
:End
:10E→F
:E→D
:While iPart(D
:.1iPart(D→D
:10(F+fPart(Ans→F
:End
:For(H,0,9
:If remainder(F,3
:Then
:√(F→D
:7
:While Ans≤D and min(remainder(F,{Ans,Ans+4
:Ans+6
:End
:N-(Ans>D→N
:If not(Ans
:Return
:End
:End
:F+10^(B→F
:End
:End
Now it takes about 17 seconds to compute the 42nd prime palindrome and it is 24 bytes smaller :)
Hah, nice optimisations!  It's always fun when you still can make such a big difference by little code changes :)

Quote
I have been trying to tweak it to get it even faster and I know that there must be a few optimisations that I am not seeing. It is 77 bytes smaller than mine and almost as fast, so that is really awesome.

...

After adjusting the prime checker thing even more, I made it much faster, and it is now faster than mine, at the cost of some bytes (still 59 bytes smaller than mine). For comparison, the version above takes 17 seconds to find palprime 42 and 86 seconds for palprime 100. This version takes 13 and 52 seconds, respectively.
Code: [Select]
:DelVar EAns-5→N
:While 1
:E+1→E
:1+int(log(E→B
:If 1<gcd(10,int(E10^(1-Ans
:End
:10E→F
:E→D
:While iPart(D
:.1iPart(D→D
:10(F+fPart(Ans→F
:End
:For(H,0,9
:If min(remainder(F,{3,7,11
:Then
:√(F→D
:13
:While Ans≤D and min(remainder(F,Ans+{0,4,6,10,16,18,24,28
:Ans+30
:End
:N-(Ans>D→N
:If not(Ans
:Return
:End
:End
:F+10^(B→F
:End
:End
Hopefully everything is typed properly.
EDIT: Made it even faster. Now 12 and 49 seconds respectively, using the same prime checking routine as my program.

Hah, cool! I actually changed my Nspire version to use 30 but reverted the change because it became slower for larger numbers (although faster for smaller numbers). But didn't try it in my z80 version.

Anyway thanks Xeda for looking into my code!
« Last Edit: May 14, 2013, 03:10:07 pm by Jim Bauwens »
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: My z80 basic palprime algorithm
« Reply #5 on: May 14, 2013, 03:19:29 pm »
It is because of the OS version. On 2.43, it takes about 16 seconds, on OS 2.55MP it takes 21 seconds.
Logged
Pages: [1]   Go Up
« previous next »