« previous next »
Pages: [1]   Go Down

Author Topic: Optmising BASIC code for A^K mod P  (Read 5003 times)

0 Members and 1 Guest are viewing this topic.

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
Optmising BASIC code for A^K mod P
« on: January 07, 2013, 11:00:40 am »
I made this code to compute AK mod P and I was wondering if it could be optmised and still preserve the speediness (or make it faster).
Code: [Select]
:1→M
:While int(K
:.5K→K
:If int(2fPart(Ans
:AM-Pint(AM/P→M
:A²-Pint(A²/P→A
:End
I feel like it could be optimised in BASIC. And maybe use only three variables (base, exponent, mod).
EDIT: Optimised with suggestions from calc84maniac and Jacobly
EDIT2: Figured out that .5K is faster than K/2
« Last Edit: January 07, 2013, 12:51:19 pm by Xeda112358 »
Logged

Offline jacobly

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 205
  • Rating: +161/-1
    • View Profile
Re: Optmising BASIC code for A^K mod P
« Reply #1 on: January 07, 2013, 12:24:58 pm »
I have no idea if this is faster, but it doesn't use M.

Code: [Select]
{.5K,A,1
While int(2Ans(1
Ans{.5,Ans(2),1+(Ans(2)-1)int(2fPart(Ans(1
Ans-Pint({0,1,1}Ans/P
End
Ans(3
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: Optmising BASIC code for A^K mod P
« Reply #2 on: January 07, 2013, 12:31:07 pm »
Wow, it isn't faster, but it is still pretty fast and only a few byte bigger than the code I had (excluding the first and last line). That is an awesome use of lists!
Logged

Offline Deep Toaster

  • So much to do, so much time, so little motivation
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 8217
  • Rating: +758/-15
    • View Profile
    • ClrHome
Re: Optmising BASIC code for A^K mod P
« Reply #3 on: January 07, 2013, 02:05:09 pm »
Optimizing your original code:
Quote from: TI-BASIC
1→M
While iPart(K
.5K→K
If int(2fPart(Ans
PfPart(AM/P→M
PfPart(A2/P→A
End
Slower time but half the size:
Quote from: TI-BASIC
1
For(I,1,K
PfPart(AAns/P
End
round(Ans,0

EDIT: Corrected by Runer112—second one can be significantly slower because it's on a different time complexity.
« Last Edit: January 07, 2013, 11:47:52 pm by Deep Thought »
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: Optmising BASIC code for A^K mod P
« Reply #4 on: January 07, 2013, 11:52:42 pm »
The problem with that is that it is quite a lot slower for larger values of K. The algorithm I posted takes ceiling(log2K) number of iterations compared to K iterations. For example, K=999 takes 10 iterations versus 999. At K=999999999, my code takes about 2 seconds, yours would take one or two years, if my estimations are correct o.o

In fact, that is very similar to the code I was trying to speed up (somebody posted an encryption program on TI|BD, and I knew the more efficient algorithm).
EDIT: Never mind, I thought you were quoting my code, I see now. The issue with the first optimisation is a rather bothersome one. I used to use the fPart( method, but that will cause rounding errors that mess up the mod() formula, especially with numbers with certain prime factors.
« Last Edit: January 08, 2013, 12:06:15 am by Xeda112358 »
Logged
Pages: [1]   Go Up
« previous next »